栈和队列

1.1 栈的应用场景

栈是一种先进后出的数据结构，具体实现的底层可以用数组。

在各类编辑软件中都有应用：撤销操作。
在系统中的应用：系统栈。
在算法中具体的应用题目：括号匹配，回文链表，树结构的层序遍历。

1.2 队列

队列是一种先进先出的数据结构。底层实现也可以用数据来实现。但是数组实现会有一个局限性，出队操作存在元素左移，所以导致时间复杂度为O(n)级别。

1.2.1 数组队列局限性

如下图所示，数组队列移除元素时，后排所有元素均得向前移动一位。

image.png

解决这个局限性的办法就是循环队列。

1.2.2 循环队列

一般数组只是维护一个尾指针，即size。我们为了移除元素后不需再进行元素移动操作，这时就得维护一个头指针front，用以来标记第一个元素所在的位置。此时front所指位置为队首，tail所指位置为队尾。

队列为空时：

image.png

队列中插入一个元素：

image.png

队列中插入5个元素，并且移除了2个元素。tail指针已经经过了一轮累加，也就是当tail=4时，此时插入一个元素，tail = （tail + 1）% capacity = 0；

image.png

再插入一个元素，如下图：

image.png

此时，不能再进行元素的插入了，因为再插入一个元素，那么会导致 tail == front，由于我们已经定义了tail == front时是表示数组为空，所以会产生冲突。

所以在这里，我们有意识的浪费了一个空间，多维护了一个tail指针，构成了循环队列。

1.3 循环队列和普通数组队列的比较

如下图结论可以看出来，循环队列带来的性能优势非常巨大，这里还只是针对50万数据。

    private static double testQueue(Queue<Integer> queue, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();

        for (int i = 0; i < opCount; i++) {
            queue.enqueue(random.nextInt(Integer.MAX_VALUE));
        }

        for (int i = 0; i < opCount; i++) {
            queue.dequeue();
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / (1000.0 * 1000 * 1000);
    }

    public static void main(String[] args) {
        int count = 500000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        LoopQueue<Integer> loopQueue = new LoopQueue<>();

        System.out.println("array: " + testQueue(arrayQueue, count));
        System.out.println("loop: " + testQueue(loopQueue, count));

    }

结论
array: 28.889796413
loop: 0.044339989

一些题外话，随着不断加深数据结构的学习，我领悟到任何数据结构拥有一方面优势时，必将导致另外一个方面的不足。引申到我们的生活，这个世界是公平的，人和事都没有所谓的完美之说，少追求完美主义，多接受自身的不足点，看到自身闪光点，也许才是快乐生活的源泉。