使用堆栈的队列

Question

我无法理解一个问题.问题首先要求编写一个C++类来表示一个整数堆栈,并且完成了很多工作.这是我的原型:

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

以两重叠,在与出.

• 对于enqueue一个元素,push它在堆栈中.
• 对于dequeue一个元素,
  1. pop如果out不为空,则从堆栈中输出一个元素; 除此以外,
  2. pop并push从所有元素在给出,然后服务的顶部元件出来.

只在必要时执行步骤2非常重要.需要注意的是enqueue具有复杂性O(1) ,和dequeue已摊销复杂度为O(1) ,提供您的实现pop,并push为O(1) .