【剑指offer】面试题七：用两个栈实现队列

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

队列的声明如下：

template<typename T> class Queue
{
public:
    Queue();
    ~Queue();

    void appendTail(const T&);
    T deleteHead();
    bool empty()const;

private:  
    stack<T> stack1;
    stack<T> stack2;
};

性质：

栈：在一端进行进栈弹栈操作，遵循后进先出原则；
队列：在一端进行进队操作，而在另一端进行出队操作，遵循先进先出原则。

　从上述队列的声明中可以看出，一个队列包含了两个栈 stack1 和 stack2，因此要求我们操作这两个“先进后出”的栈实现一个“先进先出”的队列。

　我们通过一个例子来分析往该队列Queue插入和删除元素的过程，假设待办操作为 push a、push b、push c、pop（a）、push d、pop（b）。

1、首先先插入一个元素 a，先将 a 插入到 stack1，此时 stack1 中的元素有{a}，stack2 为空。再压入两个元素 b 和 c，还是插入到 stack1 中，此时 stack1 中的元素有{a，b，c}，其中 c 位于栈顶，而 stack2 仍然是空的。

2、这时我们试着从队列 Queue 中删除一个元素。按照队列先进先出的规则。由于 a 比 b、c 先插入到队列中，最先被删除（pop）的元素应该是 a。但是元素 a 存储在 stack1 的底部，因此不能直接进行删除。注意到 stack2 还没有使用过，因此我们可以借助 stack2 实现删除（pop）操作。

3、现在将 stack1 中的元素逐个弹出并压入 stack2，元素在 stack2 中的顺序恰好和原来在 stack1 中的顺序相反。因此经过 3 次弹出 stack1 和压入 stack2 操作之后，stack1 为空，而 stack2 中的元素为 {c，b，a}，这个时候就可以弹出 stack2 的栈顶元素 a 了。

4、如果还要继续删除队列的头部，因为 b 先于 c 进队列，而 stack2 中的元素为{b，c}，b 位于栈顶，因此只要 stack2 非空，我们就可以一直做删除操作。

5、如果此时要进行进队操作（push d），我们只需将 d 直接压入 stack1 即可。

总结上面的分析可以得出：

1、删除元素时：
    当 stack2 中不为空时，在 stack2 中的栈顶元素是最先进入队列的元素，可以直接弹出。
    当 stack2 为空，stack1 不为空时，我们把 stack1 中的元素逐个弹出并压入 stack2 中，由于先进入队列的元素被压到 stack1 的底部，经过弹出和压入之后就处于 stack2 的顶端了，此时，也可以直接弹出

2、增加元素时：
    直接压入 stack1 即可。

具体代码如下：

.hpp 文件

 1 // Queue.hpp
 2 #ifndef QUEUE_HPP
 3 #define QUEUE_HPP
 4 
 5 #include <stack>
 6 #include <stdexcept>
 7 
 8 template <typename T>
 9 class Queue
10 {
11 public:
12     Queue()
13     { }
14     ~Queue()
15     { }
16 
17     bool empty()const;
18     void appendTail(const T &);
19     T deleteHead();
20 
21 private:
22     std::stack<T> st1;
23     std::stack<T> st2;
24 };
25 
26 template <typename T>
27 bool Queue<T>::empty()const
28 {
29     return (st1.empty() && st2.empty());
30 }
31 
32 template <typename T>
33 void Queue<T>::appendTail(const T &value)
34 {
35     st1.push(value); // 压入st1中
36 }
37 
38 template <typename T>
39 T Queue<T>::deleteHead()
40 {
41     if(empty())
42         throw std::out_of_range("out of range.");
43 
44     if(st2.empty()) // 如果st2为空，则需要先进行将st1中的元素逐个压入st2栈中
45     {
46         while(!st1.empty())
47         {
48             st2.push(st1.top());
49             st1.pop();
50         }
51     }
52 
53     T val = st2.top();
54     st2.pop();
55 
56     return val;
57 }
58 
59 #endif/*QUEUE_HPP*/

View Code

【剑指offer】面试题七：用两个栈实现队列

相关推荐