代码随想录算法训练营第十天 | 232.用栈实现队列、225. 用队列实现栈

232.用栈实现队列

题目链接：232.用栈实现队列

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

实现 MyQueue 类：

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

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

思路

设置两个栈，分别为stack1，stack2。

当采用push操作时，将元素推到stack1中去。

当采用pop或者peek操作时，如果是第一次请求或此时stack2为空，将stack1中所有元素全部pop出来，推入stack2中，

此时stack2的栈顶就是所实现队列的队列头。而如果此时stack2中还有元素，则只需要pop出stack2当前栈顶元素即可。

判断是否为空，只需要判断当前两个栈stack1和stack2是否都为空即可。

C++实现

class MyQueue {
private:
    stack<int> stack1;
    stack<int> stack2;

public:
    MyQueue() {

    }
    
    void push(int x) {
        stack1.push(x);
    }
    
    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int value = stack2.top();
        stack2.pop();
        return value;
    }
    
    int peek() {
        if(stack2.empty()){
            while(!stack1.empty()){
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int value = stack2.top();
        return value;
    }
    
    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

225. 用队列实现栈

题目链接：225. 用队列实现栈

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

实现 MyStack 类：

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

文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

思路

可以仅采用一个队列来实现。

定义一个队列queue1，实现push操作，只需要将元素置入队尾即可。

实现pop操作时，可以先记录当前队列的长度length，然后不断地将元素从队首排出，再推入队列尾部，这个循环持续length - 1次。

此时队列首部的元素正是构建的栈的栈顶，将该元素从队首排出即可。

对于top操作来说，前面的循环过程于pop类似，只是当获得该元素的值后，再将该元素从队首排出，推入队列尾部。

判断实现的栈是否为空，只需要判断队列是否为空即可。

C++实现

class MyStack {
private:
    queue<int> queue1;

public:
    MyStack() {

    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        int length = queue1.size();
        for(int i = 0;i<length-1;i++){
            int tmp = queue1.front();
            queue1.pop();
            queue1.push(tmp);
        }
        int value = queue1.front();
        queue1.pop();
        return value;
    }
    
    int top() {
        int length = queue1.size();
        for(int i = 0;i<length-1;i++){
            int tmp = queue1.front();
            queue1.pop();
            queue1.push(tmp);
        }
        int value = queue1.front();
        queue1.pop();
        queue1.push(value);
        return value;
    }
    
    bool empty() {
        return queue1.empty();
    }
};