由两个栈组成的队列

题目

编写一个类,用两个栈实现队列,支持队列的基本操作 push、pop。

难度

尉 ★★☆☆

解答

栈的特点是先进后出,而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。

具体实现时是一个栈作为压入栈,在压入数据时只往这个栈中压入,记为 stackPush;另一个栈只作为弹出栈,在弹出数据时只从这个栈弹出,记为 stackPop。

因为数据压入栈的时候,顺序是先进后出的。那么只要把 stackPush 的数据再压入 stackPop 中,顺序就变回来了。

例如,将 1 ~ 5 依次压入 stackPush,那么从 stackPush 的栈顶到栈底为 5 ~ 1,此时依次再将 5 ~ 1 倒入 stackPop,那么从 stackPop 的栈顶到栈底就变成了 1 ~ 5。再从 stackPop 弹出时,顺序就像队列一样,如下图所示。

听起来虽然简单,实际上必须要做到以下两点:

  1. 如果 stackPush 要往 stackPop 中压入数据,那么必须一次性把 stackPush 中的数据全部压入。
  2. 如果 stackPop 不为空,stackPush 绝对不能向 stackPop 中压入数据。

违反了以上的任一点都会发生错误。上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢?

这个选择的时机可以有很多,调用 push、pop 任何一种时发生“压”数据的行为的都是可以的。只要满足如上提到的两点,就不会出错。具体实现请参考下面的 TwoStacksQueue 类:

class TwoStacksQueue
{
private:
    stack<int> stackPush;
    stack<int> stackPop;
    
    // push 栈向 pop 栈倒入数据
    void pushToPop()
    {
        if (this->stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.top());
                stackPush.pop();
            }
        }
    }
public:
    void push(int newNum)
    {
        this->stackPush.push(newNum);
        this->pushToPop();
    }
    
    int pop()
    {
        if (stackPush.empty() && stackPop.empty()) {
            throw "Queue is empty!";
        }
        this->pushToPop();
        int value = this->stackPop.top();
        this->stackPop.pop();
        return value;
    }
};

测试

int main(int argc, const char * argv[]) {
    TwoStacksQueue *queue = new TwoStacksQueue();
    
    int arr[] = {3, 4, 5, 1, 2, 1};
    for (auto num: arr) {
        queue->push(num);
    }
    for (int i = 0; i < 6; i ++) {
        cout << "弹出:" << queue->pop() << endl;
    }
    return 0;
}

运行结果

弹出:3
弹出:4
弹出:5
弹出:1
弹出:2
弹出:1
Program ended with exit code: 0
Last modification:February 3rd, 2020 at 12:51 am
如果觉得我的文章对你有用,请随意赞赏