c++ - 使用堆栈的队列

Question

我无法理解一个问题。问题首先要求编写一个 C++ 类来表示整数堆栈，然后就完成了。这是我的原型(prototype):

class Stack{
private:
    int top;
    int item[100];
public:
    Stack() {top = -1;}
    ~Stack();
    void push(int x) {item[++top] = x;}
    int pop() {return item[top--];}
    int empty(int top);
};

问题的第二部分说“将堆栈用于存储目的，编写一个 C++ 类来表示整数队列”。我的队列如下:

class Queue{
private:
    int * data;
    int beginning, end, itemCount;
public:
    Queue(int maxSize = 100);
    Queue(Queue &OtherQueue);
    ~Queue();
    void enqueue(int x);
    void dequeue();
    int amount();
};

我不明白我是如何将堆栈用于队列的存储目的。

Answer 1

取两个堆栈，in 和 out。

• 要入队一个元素，将其压入堆栈。
• dequeue 一个元素，
  如果 out 不为空，则
  1. pop 从堆栈 out 中取出一个元素；否则，
  2. pop 和push 所有元素从in 到out，然后服务于 的顶部元素出。

请务必仅在必要时执行第 2 步。请注意，enqueue 的复杂度为 O(1)，dequeue 的复杂度为 amortized复杂性 O(1)，前提是您对 pop 和 push 的实现是 O(1)。