前言

第三期的数据结构与算法学习开始了，本期要学习的内容为栈和队列，平时在写代码或者是阅读源码的时候都能看到这两种数据结构的影子，尤其是队列用的居多，那么本期的学习目标就是了解一下栈和队列这两种数据结构的定义以及它们的一些基本操作，话不多说，开干!

一、栈

栈(Stack)是限定仅在表尾进行插入和删除的线性表，是一种后进先出(Last In First Out) 的数据结构。
就拿我们经常使用的淘宝APP来举例子好了，你淘宝APP打开后进入首页，这时你会去进行购物，你在首页看到了你喜欢的衣服的封面，你点了进去，这时跳转到了这个商品的详情页，然后你点击了购买，选择好尺寸点击确定后，跳转到了支付页面，这时候你想购买其他商品时，你会连续按下Back键然后回到最初的首页，这整个过程就相当于一个栈的操作过程。
stack_tb
栈允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈的插入操作称为入栈(push)，删除操作称为出栈(pop)，如下图所示：
在这里插入图片描述

1.1 栈的顺序存储结构

栈是一种特殊的线性表，那么对于栈来说，顺序存储和链式存储也是可以用到栈上面的，只不过操作上受限。其中栈的顺序存储结构可以称作顺序栈，顺序栈是用一段地址连续的存储空间来存储栈中的数据元素，它底层依旧是用的数组实现，下面我用代码来简单地实现一下顺序栈的出栈与入栈等操作。

/**
 * 顺序栈
 */
class SequenceStack {
    private Object[] stack;         //用于存放数据的数组
    private int stackCapacity;      //栈的容量
    private int top;                //栈顶指针(永远指向栈顶元素)

    /**
     * 默认构造一个容量为10的栈
     */
    public SequenceStack() {
        this(10);
    }

    /**
     * 构造一个指定容量的栈
     *
     * @param capacity 容量
     */
    public SequenceStack(int capacity) {
        stack = new Object[capacity];
        stackCapacity = capacity;
        top = -1;
    }

    /**
     * 判断是否为一个空栈
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 数据进栈
     *
     * @param element 数据元素
     * @throws Exception 如果栈满了,数据还进栈则会抛出异常!
     */
    public void push(Object element) throws Exception {
        if (top == stackCapacity - 1) {
            throw new Exception("Stack is Full!");
        }
        top++;                  //栈顶指针指向新的元素
        stack[top] = element;   //向栈中添加新元素
    }

    /**
     * 数据出栈
     *
     * @return 出栈的数据元素
     */
    public Object pop() throws Exception {
        if (isEmpty()) {
            throw new Exception("Stack is Empty!");
        }
        Object element = stack[top];
        top--;
        return element;
    }

    /**
     * 获取栈中元素个数
     */
    public int size() {
        return top + 1;
    }

    /**
     * 获取栈中的指定位置的元素
     */
    public Object get(int index) throws Exception {
        if (index > top) {
            throw new Exception("Index out of bounds!");
        }

        if (index < 0) {
            throw new IllegalArgumentException("Illegal Parameter!");
        }

        return stack[index];
    }
}

1.2 栈的链式存储结构

栈的链式存储结构称作链栈，定义和链表都是一样的，包含一个数据域和一个指针域，数据域用来存储数据，指针域存储下一结点的地址。但是千万得记得，栈的操作受限于出栈和入栈都是从栈顶开始的。

/**
 * 链栈实现
 */
class LinkStack {
    /**
     * 结点类
     */
    private class Node {
        Object data;        //存储元素的数据域
        Node next;          //存储下一节点的指针域

        public Node() {
            this(null, null);
        }

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node topNode;       //栈顶指针
    private int elementSize;    //栈中元素个数

    public LinkStack() {
        elementSize = 0;
    }

    /**
     * 入栈操作
     *
     * @param element 需要入栈的元素
     */
    public void push(Object element) {
        if (elementSize == 0) {
            topNode = new Node(element, null);
        } else {
            Node newNode = new Node();
            newNode.data = element;
            newNode.next = topNode;		//入栈的新结点的指针域指向栈顶结点
            topNode = newNode;			//把栈顶指针指向入栈的新结点
        }
        elementSize++;					//栈的元素个数+1
    }

    /**
     * 出栈操作
     *
     * @return 出栈的元素
     */
    public Object pop() throws Exception {
        if (elementSize == 0) {
            throw new Exception("Stack is Null");
        }

        Node tempNode;                      //这个结点表示它是需要出栈的结点
        Object resultData = topNode.data;   //获取到当前栈顶结点的数据元素
        tempNode = topNode;                 //将栈顶指针指向的结点转存入等待被出栈的结点
        topNode = tempNode.next;            //将栈顶指针指向下一结点
        tempNode = null;                    //原来的栈顶结点出栈
        elementSize--;                      //栈的元素个数-1
        return resultData;                  //返回出栈的结点数据
    }
}

二、两栈共享空间

两栈共享空间即两个栈使用同一个数组来实现出栈与入栈操作，这样可以更好的利用数组空间。为了更好的理解两栈共享空间，我逐一画图演示：
shared_stack
如上图所示，创建了两个相同类型的栈，栈1与栈2，栈容量都为5，它们底层有着各自的数组来管理出入栈的数据，栈1 push了5个数据元素进栈，此时栈1已满，栈2 push了2个数据元素进栈，此时栈1再进行push操作，则会发生异常，而栈2还有剩余的空间，数组空间利用率低，所以下面来看看如何两个栈共用同一个数组。
shared_stack1
这下就从两个数组变成了一个数组，栈同样的还是两个栈，让栈1的栈底成为此数组的始端(索引为0的位置)，栈2的栈底成为此数组的末端(数组长度 - 1的位置)，top1则为栈1栈顶指针，top2为栈2栈顶指针，可以结合图联想到当(top1 + 1) == top2时则为栈满，下面就来看看如何使用代码来实现。

/**
 * 两栈共享空间
 * 时间复杂度均为O(1)
 */
class SharedStack {
    private Object[] stack;         //用于存放数据的数组
    private int stackCapacity;      //栈的容量
    private int top1;               //栈1的栈顶指针
    private int top2;               //栈2的栈顶指针

    public SharedStack() {
        this(10);
    }

    public SharedStack(int capacity) {
        stack = new Object[capacity];
        stackCapacity = capacity;
        top1 = -1;
        top2 = stackCapacity;
    }

    /**
     * 将元素插入指定的栈中
     *
     * @param stackNumber 栈号
     * @param element     需要插入的元素
     */
    public void push(int stackNumber, Object element) throws Exception {
        if (top1 + 1 == top2) {
            throw new Exception("Stack is Full");
        }

        if (stackNumber < 1 || stackNumber > 2) {
            throw new IllegalArgumentException("Stack Number Not Found!");
        }

        if (stackNumber == 1) {
            stack[++top1] = element;
        } else {
            stack[--top2] = element;
        }
    }

    /**
     * 指定的栈进行弹栈操作
     *
     * @param stackNumber 栈号
     * @return 指定栈弹出的元素
     */
    public Object pop(int stackNumber) throws Exception {
        if (stackNumber == 1) {
            if (top1 == -1) {
                throw new Exception("Stack1 is Null!");
            }
            Object element = stack[top1];
            top1--;
            return element;
        } else if (stackNumber == 2) {
            if (top2 == stackCapacity) {
                throw new Exception("Stack2 is Null!");
            }
            Object element = stack[top2];
            top2++;
            return element;
        } else {
            throw new IllegalArgumentException("Stack Number Not Found!");
        }
    }

    /**
     * 返回指定栈的元素个数
     *
     * @param stackNumber 栈号
     * @return 指定栈的元素个数
     */
    public int size(int stackNumber) {
        if (stackNumber == 1 && top1 != -1) {
            return top1 + 1;
        } else if (stackNumber == 2 && top2 != stackCapacity) {
            return stackCapacity - top2;
        } else {
            return 0;
        }
    }

    /**
     * 返回指定栈的某个索引的元素
     */
    public Object get(int stackNumber, int index) throws Exception {
        if (stackNumber == 1 && index != -1 && index <= top1) {
            return stack[index];
        } else if (stackNumber == 2 && index != -1 && index < (stackCapacity - top2)) {
            return stack[(stackCapacity - 1) - index];
        } else {
            throw new Exception("Stack Error!");
        }
    }
}

三、递归 - 裴波那契数列

我相信大多数程序员在学习编程基础的过程中，就已经接触到了递归，那么在这里作为学习者的你我，再一次的来把递归的定义刻入DNA中。
通常，我们把一个直接或间接调用自己的函数称作为递归函数，但是使用递归你得有一个终止递归的条件，
不然就java.lang.StackOverflowError，所以每一个递归函数必须要有一个能结束递归的条件。下面就来看看一道非常经典的算法题 - 裴波那契数列，这里我准备使用递归来实现。

public static int fibonacciSequenceMethod(int num) {
    if (num < 2) {
        return num == 0 ? 0 : 1;
    }
    return fibonacciSequenceMethod(num - 1) + fibonacciSequenceMethod(num - 2);
}

这个算法非常好理解，它有一个非常明显的特点，那就是前两项的和加起来就是第三项。
fib

四、队列

队列(queue)，是只允许在一端进行插入，而在另一端进行删除的特殊线性表，是一种先进先出(First In First Out)的数据结构。
举一个生活中的例子，在火车站买票时，大家都是排队进行买票，先来的先买，买完之后就从这个买票队伍走出去了，而后面进来买票的人必须排在这个队伍的末尾，这个整个过程就像是队列的操作。
队列中，允许插入的一端称为队尾，删除的一端称为队头，不含任何数据的队列称为空队列。队列的插入操作称为入队(enqueue)，删除的操作称为出队(dequeue)，如下图所示：
queue_demo

4.1 队列的顺序存储结构

和栈一样，队列也是一种特殊的线性表，所以也有顺序存储和链式存储这两种存储方式，分别称作顺序队列和链式队列，下面实现了顺序队列的入队和出队操作：

/**
 * 顺序队列的实现
 */
class SequenceQueue {
    private Object[] elements;  //存储数据的数组
    private int queueCapacity;  //这个队列的容量

    private int head;           //表示队头指针
    private int rear;           //表示队尾指针

    /**
     * 初始化一个容量默认为10的队列
     */
    public SequenceQueue() {
        this(10);
    }

    /**
     * 初始化一个指定容量的队列
     *
     * @param capacity 传入一个int类型的变量,来指定此队列的容量。
     */
    public SequenceQueue(int capacity) {
        elements = new Object[capacity];
        queueCapacity = capacity;
        head = 0;
        rear = 0;
    }

    /**
     * 时间复杂度O(1)
     * 往队列中添加一个元素(入队)
     *
     * @param element 传入Object类型的变量,代表需要添加的元素。
     */
    public void enqueue(Object element) throws Exception {
        if (rear == queueCapacity) {
            throw new Exception("Queue is Full,Can Not Enqueue");
        }
        elements[rear] = element;
        rear++;
    }
    
    /**
     * 时间复杂度O(1)
     * 往队列中移除一个元素(出队)
     *
     * @return 返回出队的元素
     */
    public Object dequeue() throws Exception {
        if (head == rear) {
            throw new Exception("Queue Already Null,Can Not Dequeue");
        }
        return elements[head++];
    }

    /**
     * 获取队列中的元素个数
     *
     * @return 元素个数
     */
    public int size() {
        if (head == rear) {
            return 0;
        }
        return rear - head;
    }
}

可以看到顺序队列的底层也是用数组实现的，它还多了两个分别指向队头和队尾的指针，细心的你肯定发现了上面代码有问题，那就是随着不断的进行入队与出队操作，出现了下面这种情况：
false_overflow
这种现象就称作假溢出，它存储数据的数组都还没装满，但是队列已经出现溢出的情况了，与此同时出队操作还造成了数组中的数据不连续，所以采用数组数据迁移来解决假溢出这种现象。
resolve_false_overflow
这样就解决了假溢出的现象，但是由于涉及到数组数据迁移的操作，所以时间复杂度由原来的O(1) 变成了 O(n)，思路是：出队时不用迁移数据，如果队尾指针已经到了队列的最右边，但是队列还有空闲的空间，我们只需要在入队时，做一次数据的整体迁移操作就可以了。

/**
 * 最好时间复杂度O(1)
 * 最坏时间复杂度O(n),即只有在队尾指针移到了队列最右边时，才要触发数据迁移
 * 往队列中添加一个元素(入队)
 *
 * @param element 传入Object类型的变量,代表需要添加的元素。
 */
public void enqueue(Object element) throws Exception {
    if (rear == queueCapacity) {
        if (head == 0) throw new Exception("Queue is Full,Can Not Enqueue");
        //队尾指针已经到了队列最右边，但是队列中还有空闲空间，那么需要进行数据的整体迁移
        for (int i = head; i < rear; i++) {
            elements[i - head] = elements[i];
        }
        //重新定位指针的指向
        rear -= head;
        head = 0;
    }
    elements[rear] = element;
    rear++;
}

4.2 队列的链式存储结构

链式队列的底层是由链表实现的，和顺序队列一样也有两个指针，分别指向链表的第一个结点和最后一个结点。具体实现看如下代码：

/**
 * 链式队列
 */
class LinkedQueue {
    /**
     * 结点类
     */
    class Node {
        Object data;
        Node next;

        public Node() {
            this(null, null);
        }

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private int size;   //队列中的元素个数
    private Node head;  //队头指针
    private Node rear;  //队尾指针

    public LinkedQueue() {
        head = new Node();
        rear = new Node();
        size = 0;
    }

    /**
     * 入队操作
     *
     * @param data 需要入队的元素
     */
    public void enqueue(Object data) {
        Node newNode = new Node(data, null);
        if (size == 0) {
            head.next = newNode;
            head = head.next;
        }
        rear.next = newNode;
        rear = rear.next;
        size++;
    }

    /**
     * 出队操作
     *
     * @return 返回出队的元素
     * @throws Exception 如果队列没有元素,还继续执行出队操作,则会出现异常
     */
    public Object dequeue() throws Exception {
        if (size == 0) {
            throw new Exception("LinkedQueue Already Null,Can Not Dequeue");
        }
        Object data = head.data;
        head = head.next;
        size--;
        return data;
    }

    /**
     * 获取队列中的元素个数
     *
     * @return 队列中的元素个数
     */
    public int getSize() {
        return size;
    }
}

五、循环队列

上面我们实现了顺序队列，借用了数组数据搬移的方法来防止"假溢出"这种现象，这个方法可行是可行，但是当队尾指针移到队列最右边时，它就会触发数据搬移，这时候时间复杂度就提升到O(n)了，那么下面就来学习一下循环队列，看看循环队列是如何保持在时间复杂度为O(1)的情况下还不会出现假溢出的现象。
如果出现了"假溢出"这种现象，那么我们就从头开始，把rear指针移到索引为0的位置上，当有元素入队时，将元素置入索引为0的位置，然后rear指针后移一位，我们把队列这种头尾相接的顺序存储结构就称作循环队列。
loop_queue
这样就不需要进行数组数据迁移了，只需要改变一下指针的指向即可，这样入队时间复杂度始终为O(1)。上面我们在实现顺序队列的时候，判断队列满的条件是rear == queueCapacity，队列为空的条件是head == rear，那么循环队列如何进行判断呢？
同样的循环队列判断队列为空时，依旧是head == rear，如果是循环队列满，我们只能另寻判断条件，当循环队列满时，我们修改一下队满的条件，保留一个存储元素的空间，即循环队列满时，数组中还有一个空闲单元。
loop_queue_full
所以判断队满的条件就是：(rear + 1) % queueCapacity = head，这时你会有一个疑问：为什么循环队列要空出一个位置？ 那么仔细想想，如果不空出一个位置那就造成了判断队满和队空的条件都是head == rear，无法区分。那么解决的办法就是引入其他变量来判断当前到底是队空还是队满，那么接下来看看使用Java来实现循环队列。

/**
 * 循环队列
 */
class LoopQueue {
    private Object[] data;      //存储元素的数组
    private int queueCapacity;  //队列容量

    private int head;   //队头指针
    private int rear;   //队尾指针

    /**
     * 构造一个容量默认为10的循环队列
     */
    public LoopQueue() {
        this(10);
    }

    /**
     * 构造一个指定容量的循环队列
     *
     * @param capacity int 容量
     */
    public LoopQueue(int capacity) {
        data = new Object[capacity];
        queueCapacity = capacity;
        head = 0;
        rear = 0;
    }

    /**
     * 循环队列入队操作
     *
     * @param data 数据
     */
    public void enqueue(Object data) throws Exception {
        if ((rear + 1) % queueCapacity == head) {
            throw new Exception("Queue is Full,Can Not Enqueue");
        }
        this.data[rear] = data;
        rear = (rear + 1) % queueCapacity;          //rear指针后移一位,如果指针移到了最后面,则转到开头索引为0的位置
    }

    /**
     * 循环队列出队操作
     *
     * @throws Exception
     */
    public Object dequeue() throws Exception {
        if (head == rear) {
            throw new Exception("Queue Already Null,Can Not Dequeue");
        }
        Object element = this.data[head];
        head = (head + 1) % queueCapacity;          //head指针同样往后移动
        return element;
    }
}

六、参考

《大话数据结构》 - 程杰

数据结构与算法之美 - 王争

七、源码下载

github
码云

八、结语

第三期#数据结构与算法到此也就结束了，本期学习了栈和队列这两种数据结构，栈是后进先出的一种数据结构，队列是先进先出的数据结构，实现了最基本也是最简单的一些操作，这次的学习也收获了不少知识，但是这些只是最基础的知识，毕竟知识是无穷无尽的，在日后的学习中慢慢挖掘那些既有深度又有意思的知识。至此，感谢你和我共同学习到了最后，这里是小空，一个正在慢慢努力成长的新人程序员，那么我们下期再见!