算法练习-day9

栈和队列

232. 用栈实现队列

题意：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

实现 MyQueue 类：

1. void push(int x) ：将元素 x 推到队列的末尾
2. int pop() ：从队列的开头移除并返回元素
3. int peek() ：返回队列开头的元素
4. boolean empty()： 如果队列为空，返回 true ；否则，返回 false

示例：

       思路：我们需要使用两个栈来模拟队列，arr和tmp；其中arr表示入队列的元素，tmp表示出队列的元素，当需要取出元素时，我们就将元素全部转移到tmp中，这样就可以使原本倒叙的元素再次变为正序，并且当我们再次取出元素时，只需要判断tmp是否为空，若不为空，直接在tmp中读取数据即可

C++代码：

class MyQueue {
public:
    MyQueue() {
    }
    
    void push(int x) {
        arr.push(x);
    }
    
    int pop() {
        if(tmp.empty())//当tmp为空时，才会为出队列栈添加元素
        {
            while(!arr.empty())
            {
                tmp.push(arr.top());
                arr.pop();
            }
        }
        int sum=tmp.top();//取出队列的首元素
        tmp.pop();
        return sum;
    }
    
    int peek() {
        if(tmp.empty())
        {
            while(!arr.empty())
            {
                tmp.push(arr.top());
                arr.pop();
            }
        }
        return tmp.top();//只需要返回队列的首元素
    }
    
    bool empty() {
        return arr.empty()&&tmp.empty();//两个栈都代表队列中的元素，因此需要判断是否为空
    }
private:
    stack<int> arr;//入队列栈
    stack<int> tmp;//出队列栈
};

225. 用队列实现栈

题意：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

实现 MyStack 类：

1. void push(int x)：将元素 x 压入栈顶。
2. int pop()：移除并返回栈顶元素。
3. int top()：返回栈顶元素。
4. boolean：empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例：

       思路：本题定义了两个队列：arr和tmp，arr是入栈的队列，就是简单的元素入栈，而tmp主要起到临时队列的作用，我们将arr中存在的元素转移到tmp中，当tmp中元素为最后一个时，无需转移，直接移除，并保存值，然后再让tmp中元素原路返回arr中，最后返回，而实现top和empty就更简单了，由于我们规定的是arr为栈的存储队列，因此只需要调用arr的back和empty就可以得到我们想要的答案了

C++代码：

class MyStack {
public:
    MyStack() {
    }
    
    void push(int x) {
        arr.push(x);
    }
    
    int pop() {
        int sum=0;
        while(!arr.empty())//这里我们固定arr为入栈队列，因此，在最后我们要将临时队列的全部元素再放回arr中
        {
            sum=arr.front();
            arr.pop();
            if(!arr.empty())//当取出最后一个元素arr为空时，就说明这个元素就相当于栈顶元素，无需放入tmp中存储，已经被移除
            {
                tmp.push(sum);
            }
        }
        while(!tmp.empty())
        {
            arr.push(tmp.front());
            tmp.pop();
        }
        return sum;
    }
    
    int top() {
        return arr.back();
    }
    
    bool empty() {
        return arr.empty();
    }
private:
    queue<int> arr;//入栈队列
    queue<int> tmp;//临时队列
};