• 操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。
    • 栈的特点是后进先出，即最后被压入（push）栈的元素会第一个被弹出（pop）。
    • 队列的特点是先进先出，即第一个进入队列的元素将会第一个出来。
    • 栈和队列虽然是特点针锋相对的两个数据结构，但有意思的是它们却相互联系。

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

    1. template <typename T> class CQueue
    2. {
    3. public:
    4.     CQueue(void);
    5.     ~CQueue(void);
    7.     void appendTail(const T& node);        // 追加在末尾
    8.     T deleteHead();                        // 删除头
    9. private:
    10.     stack<T> stack1;
    11.     stack<T> stack2;
    12. }

    实现

    1. template<typename T> void CQueue<T>::appendTail(const T& element)
    2. {
    3.     stack1.push(element);        // 数据都压栈到stack1
    4. }
    6. template<typename T> T CQueue<T>::deleteHead()
    7. {
    8.     if(stack2.size() <= 0)
    9.     {
    10.         while(stack1.size() > 0){
    11.             T& data = stack1.top();
    12.             stack1.pop();                //对stack1的数据进行出栈
    13.             stack2.push(data);            //将数据压栈到stack2中
    14.         }
    15.     }
    17.     if(stack2.size() == 0)
    18.         throw new exception("queue is empty");
    20.     T head = stack2.top();
    21.     stack2.pop();
    23.     return head;
    24. }

    用两个队列实现栈

    image.png