使用堆栈的推送和弹出操作实现队列

Question

在互联网上搜索时，我发现了许多的答案，如何使用2个堆栈实现队列?
但是我怎么能实现一个队列只使用栈的push和pop操作。栈的push操作与队列的enqueue操作类似，都是在栈的末尾添加数据。但是问题在于实现deque操作，因为队列以FIFO方式工作，而堆栈以LIFO方式工作。
我知道在某些地方，我们将不得不使用递归，因为在反转堆栈的情况下，只使用堆栈的push和pop操作。我正在编写的伪代码用于使用push()，pop() &isEmptyStack()函数的堆栈是

void reverseStack(Stack s){
if(isEmptyStack(s))
return
temp=pop(s)
reverseStack(s)
push(s,temp)
}

Answer 1

不需要递归也可以。

1)让我们维护两个堆栈s1和s2(初始都是空的)。

2)enqueue: push to stack s1.

3)deque:如果s2为空，而s1不为空，则从s1中取出元素并将其压入s2。返回流行(s2) .

此解决方案具有O(n)时间复杂度(对于n个查询)，因为每个元素只被推入两次(到s1和s2)并且只弹出两次。

Answer 2

我们不必使用递归。实际上，使用两个堆栈实现队列并不难。

但是这里我们只能使用栈的标准操作——这意味着只有push to back、peek/pop from front、size和is empty操作是有效的。

需要两个堆栈:我们可以将它们分别命名为输入和输出。
输入用于将每个元素推入模拟队列(您的目标)。
当您希望从模拟队列中弹出元素，或获取队列的前端时。您应该检查输出堆栈是否为空，如果输出为空，则应该将输入堆栈中的所有元素弹出到输出中。然后输入中的前一个元素现在位于输出堆栈的顶部。

c++代码如下:s1表示输入栈，s2表示输出栈

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        s1.push(x);
    }
    // Removes the element from in front of queue.
    void pop(void) {
        assert(!s1.empty()||!s2.empty());
        if(!s2.empty()) s2.pop();
        else {
            while(!s1.empty()){
                int t=s1.top();
                s1.pop();
                s2.push(t);
            }
            s2.pop();
        }
    }
    // Get the front element.
    int peek(void) {
        assert(!s1.empty()||!s2.empty());
         if(!s2.empty()) {
             return s2.top();
         }
        else {
            while(!s1.empty()){
                int t=s1.top();
                s1.pop();
                s2.push(t);
            }
             return s2.top();
        }
    }
    // Return whether the queue is empty.
    bool empty(void) {
        return s1.empty()&&s2.empty();
    }
private:
    stack<int> s1;
    stack<int> s2;
};`

另外，根据你的语言，你可以使用list或deque来模拟堆栈