《剑指 Offer》中栈和队列的基础部分

数据结构

引言

数据结构一直是面试的重点，大多数会围绕着数组、字符串、链表、树、栈、队列等几种常见的数据结构展开，因此我们需要熟练掌握这几种数据结构。
数组和字符串是两种最为基础的数据结构，它们利用连续的内存存放数字和字符。而链表和树则是面试频率相对较高的数据结构。由于操作链表和树时需要操作相当数量的指针，因此在解决相关问题时，要特别重视相应的鲁棒性，否则容易出现程序崩溃的问题。栈与递归密切相关，而队列也和 BFS（广度优先遍历算法）密切相关，深刻理解这几种数据结构可以帮助我们解决很多问题。

数组

参照《剑指 offer》笔记一

字符串和链表

参照《剑指 offer》笔记二

树

参照《剑指 offer》笔记三

栈和队列

基础概念

栈是一个非常常见的数据结构，它在计算机领域被广泛应用，比如操作系统会给每个线程创建一个栈来存储函数调用时各个函数的参数、返回地址以及临时变量等。它的特点是先进后出（FILO, First In Last Out）。基于此，我们可以利用栈实现树的深度优先遍历。通常栈不需要考虑排序，我们需要在$O(n)$时间内才能找到最大/最小的元素。如果想在$O(1)$时间内完成，则需要特殊的设计。
队列是另一种重要的数据结构。和栈不同的是，它是先进先出（FIFO, First In First Out）的。我们可以利用队列来进行树的广度优先遍历。

题目分析

题目一

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

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;
};

解题思路

由上述队列声明可以看出，一个队列包含了两个栈stack1和stack2，因此我们需要利用这两个队列进行操作。
我们不妨利用实例进行分析：首先插入元素a，不妨插入stack1，再压入b和c，此时stack1中元素为a,b,c，且c位于栈顶，stack2为空。如图（a）所示
这时候我们试着从队列中删除一个元素。按照队列先进先出规则，由于a比b和c先插入队列中，因此最先删除的应该是a。但是a在栈底，并不能直接删除，而注意到stack2从未使用过，因此我们是时候使用它了。将stack1的内容全部出栈并压入stack2，则顺序恰好与进栈stack1顺序相反。这个时候便可以从stack2中弹出a了。如果我们还想删除队列头，继续从stack2弹出即可。
从上面的分析中我们可以总结出来删除元素的步骤：stack2不为空时，stack2的栈顶元素即为最先进入的元素，可以弹出。stack2为空时，将stack1依次出栈并入栈stack2。由于先入的元素被压到stack1底端，弹出压入后就处于stack2顶端之后就可以直接弹出。
接下来，我们考虑插入新元素，如果再插入一个元素d可以吗？还是压入stack1，如图（d）所示。但发现还是符合我们上述的条件，因此不会有任何问题。

用两个栈实现队列图示

示例代码

template<typename T>
void CQueue<T>::appendTail(const T &node) {
    stack1.push(node);
}

template<typename T>
T CQueue<T>::deleteHead() {
    if (stack2.size() <= 0) {
        while (stack1.size() > 0) {
            T &data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }
    if (stack2.size() == 0) {
        throw std::runtime_error("Queue is Empty");
    }
    T head = stack2.top();
    stack2.pop();
    return head;
}

课后习题

题目：用两个队列实现一个栈
相关定义如下：

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {

    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {

    }
    
    /** Get the top element. */
    int top() {

    }
    
    /** Returns whether the stack is empty. */
    bool empty() {

    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

解题思路

与例题类似，这里不再赘述，给出图示。

用队列实现栈图示

示例代码

class MyStack {
    public:
        queue<int> queue1;
        queue<int> queue2;

        /** Initialize your data structure here. */
        MyStack() {

        }

        /** Push element x onto stack. */
        void push(int x) {
            queue2.push(x);
            while (!queue1.empty()) {
                queue2.push(queue1.front());
                queue1.pop();
            }
            swap(queue1, queue2);
        }
        
        /** Removes the element on top of the stack and returns that element. */
        int pop() {
            int r = queue1.front();
            queue1.pop();
            return r;
        }
        
        /** Get the top element. */
        int top() {
            int r = queue1.front();
            return r;
        }
        
        /** Returns whether the stack is empty. */
        bool empty() {
            return queue1.empty();
        }
};