面试题 9：用两个栈实现队列

Posted on

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

1
2
3
4
5
6
7
8
9
10
11
template<typename T> class CQueue 
{
    public:
        CQueue(void);
        ~CQueue(void);
        void appendTail(const T& node);
        T deleteHead();
    private:
        stack<T> stack1;
        stack<T> stack2;
};
  • 操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址、临时变量等。
  • 需要 O(n) 时间，才能找到栈中最大或者最小的元素。
  • 考查应聘者写与模板相关的代码的能力。

用两个栈模拟一个队列的操作：

用两个队列模拟一个栈的操作：

Source Code