深入理解栈和队列算法

专注于编程、互联网动态。最终将总结的技术、心得、经验（数据结构与算法、源码分析等）分享给大家，这里不只限于技术！还有职场心得、生活感悟、以及面经。点击上方 "程序员小乐" ，选择“置顶公众号”，第一时间送达！

每日英文
When you cannot get something, it seems to be very important. And when you can get it easily, it seems trivial.
当你得不到，它似乎就变得相当重要。当你轻易得到了，那它就无足轻重了。

乐乐有话说
时间就在我们耿耿于怀地说别人变了的时候，悄悄地将我们自己也改变了。

来自：我没有三颗心脏

链接：cnblogs.com/wmyskxz/p/9272295.html

图片来自网络

前序系列文章

栈

 什么是栈？

栈是一种用于存储数据的简单数据结构（与链表类似）。数据入栈的次序是栈的关键。可以把一桶桶装的薯片看作是一个栈的例子，当薯片做好之后，它们会依次被添加到桶里，每一片都会是当前的最上面一片，而每次我们取的时候也是取的最上面的那一片，规定你不能破坏桶也不能把底部捅穿，所以第一个放入桶的薯片只能最后一个从桶里取出；

定义：栈（Stack）是一个有序线性表，只能在表的一端（称为栈顶，top）执行插入和删除操作。最后插入的元素将第一个被删除，所以栈也称为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out）线性表；

两个改变栈的操作都有专用名称。一个称为入栈（push），表示在栈中插入一个元素；另一个称为出栈（pop），表示从栈中删除一个元素。试图对一个空栈执行栈操作称为下溢（underflow）；试图对一个满栈执行栈操作称为溢出（overflow）。通常，溢出和下溢均认为是异常；

 栈的应用

• 无处不在的Undo操作（撤销）；

• 程序调用的系统栈；

• 括号/符号匹配；

• 等等等等….

 栈抽象数据类型

下面给出栈抽象数据类型中的操作，为了简单起见，假设数据类型为整型；

 栈的主要操作

• void push(int data)：将data（数据）插入栈；

• int pop()：删除并返回最后一个插入栈的元素；

 栈的辅助操作

• int top()：返回最后一个插入栈的元素，但不删除；

• int size()：返回存储在栈中元素的个数；

• int isEmpty()：判断栈中是否有元素；

• int isStackFull()：判断栈中是否存满元素；

 动态数组简单实现栈结构

我们结合之前创建的Array类，我们能够很好的创建属于我们自己的动态数组实现的栈结构，对于用户来说，我们只需要完成我们的相关操作，并且知道我能够不断地往里添加元素而不出错就行了，所以我们先来定义一个通用的栈接口：

public interface Stack<E> {
    int getSize();
    boolean isEmepty();
    void push(E e);
    E pop();
    E top();
}

然后我们往之前的动态数组中添加两个用户友好的方法：

public E getLast() {
    return get(size - 1);
}

public E getFirst() {
    return get(0);
}

然后实现自己的动态数组为底层的栈结构就轻松多了：

public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmepty() {
        return array.isEmpty();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E top() {
        return array.getLast();
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }
}

 简单复杂度分析

从代码中可以看出，几乎所有的时间复杂度都为O(1)级别，比较特别的是push()和pop()操作可能涉及到底层数组的扩容或缩容的操作，所以是均摊下来的复杂度；

队列

 什么是队列？

队列是一种用于存储数据的数据结构（与链表和栈类似），数据到达的次序是队列的关键；在日常生活中队列是指从序列的开始按照顺序等待服务的一队人或物；

定义：队列是一种只能在一端插入（队尾），在另一端删除（队首）的有序线性表。队列中第一个插入的元素也是第一个被删除的元素，所以队列是一种先进先出（FIFO,First In First Out）或后进后出（LiLO,Last In Last Out）线性表；

与栈类似，两个改变队列的操作各有专用名称；在队列中插入一个元素，称为入队（EnQueue），从队列中删除一个元素，称为出队（DeQueue）；试图对一个空队列执行出队操作称为下溢（underflow），试图对一个满队列执行入队操作称为溢出（overflow）；通常认为溢出和下溢是异常。

 队列的一些应用举例

• 操作系统根据（具有相同优先级的）任务到达的顺序调度任务（例如打印队列）；

• 模拟现实世界中的队列，如售票柜台前的队伍，或者任何需要先来先服务的场景；

• 多道程序设计；

• 异步数据传输（文件输入输出、管道、套接字）；

• 等等等等…

 动态数组简单实现队列结构

我们仍然定义一个Queue接口来说明我们队列中常用的一些方法：

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

借由我们之前自己实现的动态数组，那么我们的队列就很简单了：

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

 简单的复杂度分析

• void enquque(E)：O(1)（均摊）

• E dequeue()：O(n)

• E front()：O(1)

• int getSize()：O(1)

• boolean isEmpty()：O(1)

 实现自己的循环队列

循环队列的实现其实就是维护了一个front和一个tail分别指向头和尾，然后需要特别注意的呢是判定队满和队空的条件：

• 队空：front == tail，这没啥好说的；

• 队满：tail + 1 == front，这里其实是有意浪费了一个空间，不然就判定不了到底是队空还是队满了，因为条件都一样…

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public boolean isEmpty(){
        return front == tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public void enqueue(E e){

        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    @Override
    public E dequeue(){

        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

 简单复杂度分析

• void enquque(E)：O(1)（均摊）

• E dequeue()：O(1)（均摊）

• E front()：O(1)

• int getSize()：O(1)

• boolean isEmpty()：O(1)

 简单数组队列和循环队列的简单比较

我们来简单对比一下两个队列的性能吧，这里直接上代码：

// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue<Integer> q, int opCount){

    long startTime = System.nanoTime();

    Random random = new Random();
    for(int i = 0 ; i < opCount ; i ++)
        q.enqueue(random.nextInt(Integer.MAX_VALUE));
    for(int i = 0 ; i < opCount ; i ++)
        q.dequeue();

    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

    int opCount = 100000;

    ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
    double time1 = testQueue(arrayQueue, opCount);
    System.out.println("ArrayQueue, time: " + time1 + " s");

    LoopQueue<Integer> loopQueue = new LoopQueue<>();
    double time2 = testQueue(loopQueue, opCount);
    System.out.println("LoopQueue, time: " + time2 + " s");
}

我这里的测试结果是这样的，大家也就可见一斑啦：

其实ArrayQueue慢主要是因为出栈时每次都需要把整个结构往前挪一下

LeetCode相关题目整理

20.有效的括号

我的答案：（10ms）

public boolean isValid(String s) {

    // 正确性判断
    if (null == s || s.length() == 1) {
        return false;
    }

    Stack<Character> stack = new Stack<>();
    // 遍历输入的字符
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 如果为左括号则push进栈
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }

            char topChar = stack.pop();
            if (c == ')' && topChar != '(') {
                return false;
            }
            if (c == ']' && topChar != '[') {
                return false;
            }
            if (c == '}' && topChar != '{') {
                return false;
            }
        }
    }

    // 最后栈为空才能返回true
    return stack.isEmpty();
}

参考答案：（8ms）

public boolean isValid(String s) {

    // 正确性判断
    if (0 == s.length()) {
        return true;
    }
    if (s.length() % 2 == 1) {
        return false;
    }

    Stack<Character> stack = new Stack();
    char[] cs = s.toCharArray();
    for (int i = 0; i < cs.length; i++) {
        if (cs[i] == '(' || cs[i] == '[' || cs[i] == '{') {
            stack.push(cs[i]);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char c = stack.pop();
            if ((cs[i] == ')' && c == '(') || (cs[i] == '}' && c == '{') || (cs[i] == ']' && c == '[')) {
            } else {
                return false;
            }
        }
    }

    return stack.isEmpty();
}

155. 最小栈（剑指Offer面试题30）

参考答案（107ms）

class MinStack {

    // 数据栈，用于存放插入的数据
    private Stack<Integer> dataStack;
    // 最小数位置栈，存放数据栈中最小的数的位置
    private Stack<Integer> minStack;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    /**
     * 元素入栈
     *
     * @param x 入栈的元素
     */
    public void push(int x) {

        dataStack.push(x);

        // 如果最小栈是空的，只要将元素入栈
        if (minStack.isEmpty()) {
            minStack.push(x);
        }
        // 如果最小栈中有数据
        else {
            minStack.push(Math.min(x, minStack.peek()));
        }
    }

    /**
     * 出栈方法
     */
    public void pop() {
        // 如果栈已经为空，则返回（LeetCode不能抛异常...）
        if (dataStack.isEmpty()) {
            return;
        }

        // 如果有数据，最小数位置栈和数据栈必定是有相同的元素个数，
        // 两个栈同时出栈
        minStack.pop();
        dataStack.pop();
    }

    /**
     * 返回栈顶元素
     *
     * @return 栈顶元素
     */
    public int top() {
        return dataStack.peek();
    }

    /**
     * 获取栈中的最小元素
     *
     * @return 栈中的最小元素
     */
    public int getMin() {
        // 如果最小数公位置栈已经为空（数据栈中已经没有数据了），则抛出异常
        if (minStack.isEmpty()) {
            return 0;
        }

        // 获取数据占中的最小元素，并且返回结果
        return minStack.peek();
    }
}

改进答案：

上面求解方法的主要问题在于，每次push操作时，minStack也执行了一次push操作（新元素或当前的最小元素），也就是说，重复执行了最小值的入栈操作，所以现在我们来修改算法降低空间复杂度。仍然需要设置一个minStack，但是只有当从dataStack中出栈的元素等于minStack栈顶元素时，才对minStack执行出栈的操作；也只有当dataStack入栈的元素小于或等于当前最小值时，才对minStack执行入栈操作，下面就简单写一下了主要看一下出栈和入栈实现的逻辑就好了：

class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MinStack() {
        this.dataStack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int x) {
        dataStack.push(x);
        if (minStack.isEmpty() || minStack.peek() >= (Integer) x) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (dataStack.isEmpty()) {
            return;
        }
        Integer minTop = minStack.peek();
        Integer dataTop = dataStack.peek();
        if (minTop.intValue() == dataTop.intValue()) {
            minStack.pop();
        }
        dataStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

225. 用队列实现栈

我的答案：（118ms）

class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        if (queue1.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        int size;
        if (!queue1.isEmpty()) {
            size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        } else {
            size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    /**
     * Get the top element.
     */
    public int top() {
        int size;
        if (!queue1.isEmpty()) {
            size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            int result = queue1.peek();
            queue2.offer(queue1.poll());
            return result;
        } else {
            size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            int result = queue2.peek();
            queue1.offer(queue2.poll());
            return result;
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

参考答案：（121ms）

class MyStack {
    Queue<Integer> q;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        this.q = new LinkedList<Integer>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        q.add(x);
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.add(q.remove());
        }
        return q.remove();
    }

    /**
     * Get the top element.
     */
    public int top() {
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.add(q.remove());
        }
        int ret = q.remove();
        q.add(ret);
        return ret;
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return q.isEmpty();
    }
}

确实写得简洁啊，这样一来我就使用一个队列和两个队列都掌握啦，开心~

232.用栈实现队列（剑指Offer面试题9）

参考答案：（72ms）

class MyQueue {
    Stack<Integer> pushstack;
    Stack<Integer> popstack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        this.pushstack = new Stack();
        this.popstack = new Stack();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        pushstack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (popstack.isEmpty()) {
            while (!pushstack.isEmpty()) {
                popstack.push(pushstack.pop());
            }
        }
        return popstack.pop();
    }


    /**
     * Get the front element.
     */
    public int peek() {
        if (popstack.isEmpty()) {
            while (!pushstack.isEmpty()) {
                popstack.push(pushstack.pop());
            }
        }
        return popstack.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return pushstack.isEmpty() && popstack.isEmpty();
    }
}

其他题目整理

剑指Offer面试题31：栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列{1,2,3,4,5}是某栈的压栈序列，序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列，但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。

参考答案：（原文链接：
https://blog.csdn.net/derrantcm/article/details/46691083）

总结

栈和队列的应用远不止上面学习到的那些，实现方式也有很多种，现在也只是暂时学到这里，通过刷LeetCode也加深了我对于这两种数据结构的认识，不过自己还需要去熟悉了解一下计算机系统关于栈的应用这方面的知识，因为栈这种结构本身就很适合用来保存CPU现场之类的工作，还是抓紧时间吧，过两天还考试，这两天就先复习啦…

如果您觉得不错，请别忘了转发、分享、点赞让更多的人去学习， 您的举手之劳，就是对小乐最好的支持，非常感谢！

如何您想进技术群交流，关注公众号在后台回复 “加群”，或者 “学习” 即可

推荐阅读

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，提升技能