算法随想Day9【栈与队列】| LC232-用栈实现队列 、LC225-用队列实现栈

LC232. 用栈实现队列

之前看过相关的实现方法，但在想具体实现上，还是略显冗余。

• 我的思路是，用一个标志位method记录当前是push或pop/top操作，如果有操作的更换，都进行一次栈元素转移，实则是多余操作。
• Carl讲解，分别定义一个StaIn和StaOut，StaOut因为是用于pop/top操作的，所以无需每次从存->取的操作更换时都需要将StaIn的全部元素转移到StaOut中，只需等到StaOut.size() == 0时再进行该操作。相当于一个队列分两部分管理

////自己的版本
class MyQueue
{
private:
    int method;  //0:用于存，1:用于取和Top()
    stack<int> st1;
    stack<int> st2;
    stack<int>* pst;
public:
    MyQueue()
    {   
        this->method = 0;
        pst = &st1;
    }

    void changeStack()
    {
        if (pst == &st1)
        {
            while (pst->size() > 0)
            {
                int temp = pst->top();
                pst->pop();
                st2.push(temp);
            }
            pst = &st2;
        }
        else
        {
            while (pst->size() > 0)
            {
                int temp = pst->top();
                pst->pop();
                st1.push(temp);
            }
            pst = &st1;
        }
    }
    
    void push(int x)
    {
        if (method == 0)
        {
            pst->push(x);
        }
        else
        {
            changeStack();
            pst->push(x);
        }
        method = 0;
    }
    
    int pop()
    {
        int temp = 0;
        if (method == 1)
        {
            temp = pst->top();
            pst->pop();
        }
        else
        {
            changeStack();
            temp = pst->top();
            pst->pop();
        }
        method = 1;
        return temp;
    }
    
    int peek()
    {
        int temp = 0;
        if (method == 1)
        {
            temp = pst->top();
        }
        else
        {
            changeStack();
            temp = pst->top();
        }
        method = 1;
        return temp;
    }
    
    bool empty()
    {
        if (st1.size() == 0 && st2.size() == 0)
        {
            return true;
        }
        return false;
    }
};

////Carl版本
class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

LC225. 用队列实现栈

我的思路：用两个队列模拟栈，ptr_que指向当前队列，只有pop操作时，转移n-1个队列中的元素到另一队列中，并弹出最后一个元素。push操作只需在当前队列尾部添加，top操作返回队列的back()尾值可获得。

class MyStack {
private:
    queue<int> que1;
    queue<int> que2;
    queue<int>* prt_que;
public:
    MyStack()
    {
        prt_que = &que1;
    }
    

    void push(int x)
    {
        prt_que->push(x);
    }
    
    int pop()
    {
        int temp = 0;
        if (prt_que == &que1)
        {
            while (prt_que->size() > 1)
            {
                temp = prt_que->front();
                prt_que->pop();
                que2.push(temp);
            }
            temp = prt_que->front();
            prt_que->pop();
            prt_que = &que2;
        }
        else
        {
            while (prt_que->size() > 1)
            {
                temp = prt_que->front();
                prt_que->pop();
                que1.push(temp);
            }
            temp = prt_que->front();
            prt_que->pop();
            prt_que = &que1;
        }
        return temp;
    }
    
    int top()
    {
        return prt_que->back();
    }
    
    bool empty()
    {
        if (que1.size() == 0 && que2.size() == 0)
        {
            return true;
        }
        return false;
    }
};

优化

其实这道题目就是用一个队列就够了。一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

void push(int x) {
    que.push(x);
}

int pop() {
    int size = que.size();
    size--;
    while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
        que.push(que.front());
        que.pop();
    }
    int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
    que.pop();
    return result;
}

int top() {
    return que.back();
}