剑指offer - 用两个栈实现队列

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

#include <iostream>
#include <stack>
#include <exception>
using namespace std;

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

    void appendTail(const T& node);
    T deleteHead();

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

分析

一个列队中包含两个栈stack1和stack2，要求我们操作这两个“先进后出”的栈实现一个“先进先出”的队列

用一个具体的例子来分析该队列插入和删除元素的过程

20130513210500569.png

首先插入元素a，不妨先插入stack1，此时stack1中的元素有{a}，stack2为空。再压入两个元素b，c，此时stack1中的元素有{a,b,c}，其中c位于栈顶，而stack2仍然为空。

这时候我们从队列中删除一个元素，按照先进先出的原则，由于a比b、c先插入队列，所以最先被删除的元素应该是a。元素a在stack1中但并未位于栈顶，因此不能直接删除。

而我们的stack2还没有开始使用，是时候干点啥了。试想想如果我们把stack1中的元素逐个弹出并压入stack2，则元素在stack2中的顺序正好和原来在stack1中的顺序相反。

因此进过3次弹出stack1和压入stack2的操作之后，stack1为空，而stack2中的元素是{c,b,a}，当前元素的顺序就是我们最初入栈的顺序，这时候就可以弹出stack2的栈顶元素a了，并且此时stack1为空，而stack2的元素为{c,b}，其中b在栈顶

如果我们还想继续删除队列的头部应该怎么办？剩下的两个元素是b和c，b比c早进入队列，因此b应该先删除，而此时b恰好又在stack2的栈顶，因此直接弹出stack2的栈顶元素即可。在这次弹出操作之后，stack1仍然为空，而stack2中的元素为{c}

从上面可以总结删除元素的一个步骤：当stack2不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。当stack2为空时，可以把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端，又可以直接弹出

如果想再插入一个元素d，我们还是把它压入stack1，即新元素直接插入stack1

总结

删除操作

stack2中元素弹出顺序刚好是stack1中元素进入顺序。故在删除元素时：先判断stack2是否为空，若其不为空，则从中弹出元素；若为空，则将stack1中元素依次弹出并存入stack2中

插入操作

插入操作比较简单，直接插入stack1即可

C++

// 成员函数定义
template <typename T> CQueue<T>::CQueue(void)
{
}

template <typename T> CQueue<T>::~CQueue(void)
{
}

// 向队列插入元素
template<typename T> void CQueue<T>::appendTail(const T& node)
{
    stack1.push(node);
}

// 从队列中删除元素
template<typename T> T CQueue<T>::deleteHead()
{
    if(stack2.size()<= 0) // 先判断stack2是否为空
    {
        while(stack1.size()>0) // 当stack2为空时，将stack1中所有元素存入stack2中.
        {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }

    if(stack2.size() == 0) { // 为空抛出异常，画不能出队列
        logic_error ex("queue is empty");
        throw exception(ex);
    }

    T head = stack2.top(); // //当stack2不为空，获取栈顶元素
    stack2.pop(); // 弹出栈顶元素

    return head;
}

测试部分

void Test(char actual, char expected)
{
    if(actual == expected)
        printf("Test passed.\n");
    else
        printf("Test failed.\n");
}


int main(int argc, const char * argv[]) {

    CQueue<char> queue;

    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');

    char head = queue.deleteHead();
    Test(head, 'a');

    head = queue.deleteHead();
    Test(head, 'b');

    queue.appendTail('d');
    head = queue.deleteHead();
    Test(head, 'c');

    queue.appendTail('e');
    head = queue.deleteHead();
    Test(head, 'd');

    head = queue.deleteHead();
    Test(head, 'e');

    return 0;
}

运行输出

Test passed.
Test passed.
Test passed.
Test passed.
Test passed.