《剑指Offer》第2章笔记 栈和队列

栈：先进后出，队列：先进先出。

栈是一个非常常见的数据结构，在计算机领域被广泛应用，比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址以及临时变量等。栈的特点是后进先出。

在栈中通常需要O(n)时间才能找到栈最大或者最小的元素，如果想O(1)时间内找到则需要做特殊的设计。

队列是另一种很重要的数据结构，队列的特点是先进先出。

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

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

一个典型的队列定义：

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

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

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

至于这道题的解法，基于一个简单的原理，将一组数先进行依次进栈、再依次出栈入栈到另一个栈里，再全部进行出栈，就完成了一个简单的队列先进先出。但如果只是单纯的依赖这样的过程，无法极大程度地利用栈的空间（例如用于出栈deleteHead的栈满时，用于进栈appendTail其实还可以继续利用起来）。

定义stack1为入队栈，stack2为出队栈。

• 入队操作：
  • 当stack1不满时，直接入栈；
  • 当stack1满时：
    • 如果stack2为空，将stack1中的元素依次出栈入栈stack2；
    • 如果stack2中有元素，则无法入队；
• 出队操作：
  • 当stack2中有元素是，直接出栈；
  • 当stack2为空时：
    • 如果stack1不为空，将stack1所有元素依次出栈入栈stack2，再出栈栈顶元素；
    • 如果stack1为空，则队列为空，无法出队；

完整实现代码：

#include <iostream>
#include <stack>
#include <exception>

template<typename T> class CQueue {
    public:
        // CQueue(void);
        // ~CQueue(void);
        void appendTail(const T& node);
        T deleteHead();

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

template<typename T> void CQueue<T>::appendTail(const T& element) {
    // 不限制栈容量时，直接入栈
    stack1.push(element);
}

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size() <= 0) {
        while(stack1.size() > 0) {
            T& data = stack1.top(); // Why use T&
            stack1.pop();
            stack2.push(data);
        }
    }
    if(stack2.size() == 0) {
        // Throw Empty Error
        std::logic_error ex("queue is empty");
        throw std::exception(ex);
    }
    T head = stack2.top();
    stack2.pop();

    return head;
}

int main() {
    CQueue<int> cqueue;
    for(int i = 0; i < 5; i++) {
        cqueue.appendTail(i);
    }
    for(int i = 0; i < 3; i++) {
        std::cout << cqueue.deleteHead() << " ";
    }
    for(int i = 5; i < 10; i++) {
        cqueue.appendTail(i);
    }
    for(int i = 0; i < 7; i++) {
        std::cout << cqueue.deleteHead() << " ";
    }
    return 0;
}

相关题目：用两个队列实现一个栈。

简单分析一下思路，模仿入栈操作时，只能用使用入队操作，当需要出栈时，元素在队列尾部，只能将前面所有元素进行出队才能获取到，而出队剩下的元素就继续进入到第二个队列中。