栈和队列

0x00 基本概念

栈（Stack）是一个抽象数据类型（ADT），对一个集合的元素定义了两个基本操作，入栈（push）以及出栈（pop），栈遵循后进先出原则（LIFO, last in, first out），就像手枪的弹夹一样，最后放入的那颗子弹往往最先打出去。

此处说这是一个ADT抽象数据类型是因为其既可以用链表实现也可以用数组实现，实现的方法不唯一，其并不是一个存储（物理）结构，而是一个抽象数据类型，对于抽象数据类型准确的定义是指一个数学模型以及定义在该模型上的一组操作。

队列（Queue）也是一种抽象数据类型，其同样定义了两个基本操作，入队（enqueue）以及出队（dequeue），其遵循先进先出原则（FIFO, first in, first out），就像我们去买火车票排的那个队列一样，遵循先来后到，先来的先买，买完后出队（从队头删除），后来的自动站在队尾（在队尾添加）。

对于队列还有一种一般化（generalized）的形式就是双端队列（double-ended queue, 一般简写为deque），双端队列两头都可以进行插入（入队）和删除（出队）操作。

栈和队列均为抽象数据类型，两者均可以由两种不同的存储结构实现，即顺序存储结构以及链式存储结构。

0x01 栈（Stack）

0x00 顺序存储结构实现

以下是一个基于向量实现的栈，当数组空间不足时，可自动扩容：

class Stack {
    int *data;
    int t;
    int capacity;
public:
    Stack() {
        capacity = 50;
        data = new int[capacity];
        t = -1;
    }

    void expand()
    {
        int *ndata = new int[capacity << 1];
        for (int i = 0; i < capacity; ++i)
        {
            ndata[i] = data[i];
        }
        delete[] data;
        data = ndata;
        capacity <<= 1;
    }

    void push(int x) {
        if (t + 1 == capacity)
        {
            expand();
        }
        data[++t] = x;
    }

    void pop() {
        --t;
    }

    int top() {
        return data[t];
    }
};

上述为一个基于向量（vector）实现的栈，不存在栈满上溢的情况，当栈满了之后，会调用expand函数进行自动扩容，但是大部分基于顺序表实现的栈是存在栈满上溢的，需注意这一点。

0x01 链式存储结构实现

以下是使用双向链表实现的栈：

class Stack {

    struct ListNode
    {
        int data;
        ListNode *prev;
        ListNode *next;
        ListNode(int val) : data(val), prev(nullptr),
                            next(nullptr) {}
    };

    ListNode *head;
    ListNode *tail;

public:
    Stack() : head(new ListNode(0)), tail(new ListNode(0))
    {
        head->next = tail;
        tail->prev = head;
    }

    void push(int x)
    {
        tail->data = x;
        ListNode *dummy = new ListNode(0);
        dummy->prev = tail;
        tail->next = dummy;
        tail = dummy;
    }

    void pop()
    {
        ListNode *deleted = tail->prev;
        deleted->prev->next = tail;
        tail->prev = deleted->prev;
        delete deleted;
    }

    int top()
    {
        return tail->prev->data;
    }
};

栈的链式存储结构是不存在栈满上溢的，上述代码为使用双向链表实现的栈，且配有头尾两个哨兵结点，所以我们可以轻易地在$O(1)$的复杂度内实现栈的push和pop操作，如果使用单链表实现栈则栈顶指针即为单链表的头指针，栈的push操作即为在单链表的头部依次添加元素，就像为手枪弹夹依次压入子弹一样。

0x02 使用栈进行括号匹配

这道题目可以通过LeetCode来练习，题目地址：20. Valid Parentheses，此题给定()[]{}三种括号形式，左括号（open brackets）必需匹配相同类型的右括号（closed brackets），例如(应当匹配)而不是]或}，要求你确定数组字符串中的括号匹配是否合法：

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> stk;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                stk.push(s[i]);
            }
            else if (
                s[i] == ')' && !stk.empty() && stk.top() == '(' ||
                s[i] == ']' && !stk.empty() && stk.top() == '[' ||
                s[i] == '}' && !stk.empty() && stk.top() == '{'
            )
            {
                stk.pop();
            }
            else
            {
                return false;
            }
        }
        return stk.empty();
    }
};

还是这个用栈进行括号匹配，现在引入一种新的情况，通配符*，*做通配符既可以代表(也可以代表)也可以代表空字符（即不对括号匹配起任何作用），此为LeetCode题目678. Valid Parenthesis String。可以用双栈实现，代码如下：

class Solution {
public:
    bool checkValidString(std::string s) {
        std::stack<int> left, star;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '(')
            {
                left.push(i);
            }
            else if (s[i] == ')')
            {
                if (left.empty() && star.empty())
                {
                    return false;
                }
                if (!left.empty())
                {
                    left.pop();
                }
                else if (!star.empty())
                {
                    star.pop();
                }
            }
            else
            {
                star.push(i);
            }
        }
        while (!left.empty() && !star.empty())
        {
            if (left.top() > star.top())
            {
                return false;
            }
            left.pop();
            star.pop();
        }
        return left.empty();
    }
};

时间复杂度为$O(N)​$，空间复杂度在最坏情况下为$2N​$，例如在输入字符串均由(以及*组成时。上述算法较为容易理解，设置两个栈，第一个栈left用于存放左括号(的所在位置，第二个栈star用于存放通配符*所在的位置。从左向右遍历字符串中的每一个字符，如果为(或者*就将其下标压入其对应的栈中，如果为)就开始弹栈，先从left栈开始，如果left空了，那就弹star栈。因为括号匹配是依次的，当循环完成后，如果left栈以及star栈不为空的话，那就依次弹出两者中的元素以检查是否有星号无法通配，比如当输入数据为*(时，前面的*是无法与其后面的(完成通配，所以我们只需依次检查这两个栈，如果发现star栈的栈顶元素在left栈前面（下标小于），那就返回false匹配是吧。

0x03 两个队列实现一个栈

这是一道经典的面试算法题，在LeetCode上也有练习，225. Implement Stack using Queues，我一开始写的代码如下：

class MyStack {

    std::queue<int> q[2];

    int top(bool pop_last)
    {
        int from = q[0].empty() ? 1 : 0;
        int to = 1 - from;
        int size = q[from].size();
        for (int i = 0; i < size - 1; ++i)
        {
            q[to].push(q[from].front());
            q[from].pop();
        }
        int ret = q[from].front();
        if (!pop_last)
        {
            q[to].push(ret);
        }
        q[from].pop();
        return ret;
    }
public:
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x)
    {
        (q[0].empty() ? q[1] : q[0]).push(x);
    }

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

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

    /** Returns whether the stack is empty. */
    bool empty() {
        return q[0].empty() && q[1].empty();
    }
};

这种算法应当是低效的，因为在pop或者top的过程中需要在两个队列之间大量的移动数据。但是在测试中运行效率依旧超过100%的人。在这种情况下push操作的复杂度为$O(1)$，pop和top操作的复杂度为$O(N)$，其官方给出了三种解决方案，其中两种解决方案的pop的复杂度为$O(N)$而push的复杂度为$O(1)$，还有一种解决方案push的复杂度为$O(N)$，而pop的复杂度为$O(1)$，两种方案的选择可取决于此栈是需要进行频繁的读还是频繁的写操作，如果需要进行频繁的读操作（top或pop）可使用pop复杂度为$O(1)$的方案，如需进行频繁的写操作（push）可使用push复杂度为$O(1)$的解决方案，可自行查看。

0x04 N个不同元素依次进栈可得到的出栈序列个数

这个是个公式，卡特兰数（Catalan number），公式如下：

$$S=\frac{1}{n+1}C_{2n}^{n}$$

其中n为n个不同元素依次入栈，S为可得到的不同的出栈序列的个数。

这个公式可以用数学归纳法证明，证明过程过于复杂，在此不做赘述。

0x02 队列（Queue）

0x00 顺序存储结构实现循环队列

从一道LeetCode题目说起，622. Design Circular Queue，这道题所要求设的class中，在构造函数里将会传入一个队列的最大的大小，这样我们就可以使用数组来实现，而无需担心其会溢出，代码如下：

class MyCircularQueue {
    int *a;
    int front, rear, size, capacity;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) : a(new int[k]), front(0), rear(-1), size(0), capacity(k)
    {
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull())
        {
            return false;
        }
        ++size;
        a[rear = (rear + 1) % capacity] = value;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty())
        {
            return false;
        }
        --size;
        front = (front + 1) % capacity;
        return true;
    }

    /** Get the front item from the queue. */
    int Front() {
        return isEmpty() ? -1 : a[front];
    }

    /** Get the last item from the queue. */
    int Rear() {
        return isEmpty() ? -1 : a[rear];
    }

    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return size == 0;
    }

    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return size == capacity;
    }
};

此处需注意的是，虽然我们使用数组来实现队列，但是入队和出队操作我们均不用删除和移动元素，所以入队和出队操作的时间复杂度均为$O(1)$。

0x01 顺序存储结构实现双端循环队列

同样是一道LeetCode题目，641. Design Circular Deque，双端队列指的是队列两端都可以进行入队和出队操作的队列，一般来说，普通的队列是双端队列的一种特例形式。同样此题的构造函数中会为我们传入队列的最大大小，所以我们尽可以放心地去使用数组而无需担心数组溢出。

class MyCircularDeque {
    int *a;
    int front, rear, size, capacity;
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k) : a(new int[k]), front(0), rear(-1),
                             size(0), capacity(k) 
    {
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if (isFull())
        {
            return false;
        }
        ++size;
        if (front - 1 < 0)
        {
            a[front = capacity - 1] = value;
        }
        else
        {
            a[--front] = value;
        }
        rear = (front + size - 1) % capacity;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if (isFull())
        {
            return false;
        }
        ++size;
        a[rear = (rear + 1) % capacity] = value;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if (isEmpty())
        {
            return false;
        }
        --size;
        front = (front + 1) % capacity;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if (isEmpty())
        {
            return false;
        }
        --size;
        if (rear - 1 < 0)
        {
            rear = capacity - 1;
        }
        else
        {
            --rear;
        }
        return true;
    }

    /** Get the front item from the deque. */
    int getFront() {
        return isEmpty() ? -1 : a[front];
    }

    /** Get the last item from the deque. */
    int getRear() {
        return isEmpty() ? -1 : a[rear];
    }

    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return size == 0;
    }

    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return size == capacity;
    }
};

0x02 两个栈实现一个队列

这跟上面的那个两个队列实现一个栈一样，都可以算是一道经典的面试题，这道题在LeetCode上有练习，参见题目232. Implement Queue using Stacks，我一开始的代码如下：

static int ____ = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();

class MyQueue {
    std::stack<int> stk1, stk2;
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        while (!stk1.empty())
        {
            stk2.push(stk1.top());
            stk1.pop();
        }
        stk2.push(x);
        while (!stk2.empty())
        {
            stk1.push(stk2.top());
            stk2.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int t = stk1.top();
        stk1.pop();
        return t;
    }

    /** Get the front element. */
    int peek() {
        return stk1.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stk1.empty();
    }
};

插入操作（push）需要$O(N)$的复杂度，pop和top操作仅需要$O(1)$的复杂度，这道题同样有官方的solution，check out一下，官方同样给出了两种方法，第一种方法和我的一样，push在$O(N)$的复杂度，以及$O(1)$的pop和top操作。