如何在C++中使用单个堆栈实现队列

Question

在此 C++ 代码中，我使用单个 stack 实例实现 Queue。我在 GeeksForGeeks 中找到了这段代码。 Url Here

#include <bits/stdc++.h>
using namespace std;
class Queue
{
private:
    stack<int> s;

public:
    void enque(int x)
    {
        s.push(x);
    }
    int deque()
    {
        if (s.empty())
        {
            cout << "Q is empty" << endl;
            return -1;
        }
        int x = s.top();
        s.pop();
        if (s.empty())
        {
            return x;
        }
        // I'm not able to understand these 3 lines after this comment
        int item = deque();
        s.push(x);
        return item;
    }
};
int main()
{
    Queue q;
    q.enque(1);
    q.enque(2);
    q.enque(3);
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    return 0;
}

但是我看不懂这3行

int item = deque();
s.push(x);
return item;

Problem

在递归调用 deque() 之后，编译器如何到达下一行以再次将 x 压入堆栈。以及它如何在递归函数调用后保留 x 的值。

Answer 1

该代码并没有真正使用单个堆栈，而是通过对 deque 的递归调用将内置堆栈用作第二个堆栈。代码相当于：

#include <iostream>
#include <stack>

class Queue
{
private:
    std::stack<int> s;

public:
    void enque(int x)
    {
        s.push(x);
    }
    int deque()
    {
        if (s.empty())
        {
            std::cout << "Q is empty\n";
            return -1;
        }
        std::stack<int> temp;
        while (s.size() != 1)
        {
            temp.push(s.top());
            s.pop();
        }
        int result = s.top();
        s.pop();
        while (!temp.empty())
        {
            s.push(temp.top());
            temp.pop();
        }
        return result;
    }
};
int main()
{
    Queue q;
    q.enque(1);
    q.enque(2);
    q.enque(3);
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    return 0;
}

我想不出你以这种方式实现队列的原因，随着队列大小的增长 deque 变得越来越昂贵，使用你最终会得到的原始代码堆栈溢出。如果您需要队列，请使用 std::queue or std::deque（默认情况下 std::queue 只是一个包装轮 std::deque，它隐藏了 push_front/pop_back 方法）

如何在C++中使用单个堆栈实现队列

How to implement queue with a single stack in C++

c++

recursion

queue

stack