数据结构之栈和队列

什么是栈？
 * 假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口，往圆筒里面放入兵乓球，先放入
 * 的靠近圆筒底部，后放入的靠近圆筒入口。
 * 那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出
 * 后放入的，再取出先放入的，而不能把最里面最先放入的乒乓球优先取出
 * 。
 * 栈：是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆通容器，栈中的元素只能
 * 先入后出(First Last Out，简称FILO)。最早进入的元素存放在位置叫做栈底，最后进入的元素存放在
 * 的位置叫作栈顶。
 *   栈这种数据结构既可以用数组来实现，也可以用链表来实现。
 *    栈底                栈顶
 *    3    5   1   4   9   6   null  null
 *
 *    栈的基本操作：
 *    1. 入栈
 *    入栈操作(push)就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素
 *    的位置将会成为新的栈顶。
 *
 *    2. 出栈操作
 *     出栈操作(pop)就是把元素从栈中弹出，只有栈顶元素才允许出栈
 *     ，出栈元素的前一个元素将会成为新的栈顶。
 *     由于栈操作的代码实现比较简单，这里就不在展示代码了。
 *     入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动
 *     所以无论是以数组还是以链表实现，入栈、出栈的时间复杂度都是O(1)
 *
 * */


/**
 *   什么是队列
 *   要弄明白什么是队列？举一个例子来说明
 *   假如公路上有一条单行隧道，所有通过隧道的车辆
 *   只允许隧道入口驶入，从隧道出口驶出，不允许逆行。
 *
 *   因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序，先驶入的车辆先驶出
 *   后驶入的车辆后驶出，任何车辆都无法跳过前面的车辆提前驶出的
 *
 *   队列是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出
 *   队列中的元素只能先入先服务器托管网出(First In First Out，简称FIFO)。队列的出口端叫做队头
 *   队列的入口端叫作队尾(rear)
 *   与栈类似，队列这种数据结构既可以用做数组来实现，也可以用链表来实现
 *    用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置
 *    队列的数组实现如下：
 *    队头                  服务器托管网       队尾
 *    3    5    1   4   9    6    null     null
 *
 *
 *    队列的基本操作：
 *    对于链表实现方式，队列的入队、出队操作和栈是大同小异的，对于实现来说，队列
 *    的入队和出队操作有了一些变化。
 *
 *    1. 入队
 *      入队(enqueue)就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素
 *      的下一个位置将会成为新的的队尾。
 *
 *   2 出队
 *      出队操作(dequeue)就是把元素移出队列，只允许在队头一侧移出元素，出队元素
 *      的最后一个元素将会成为新的队头
 *    思考： 如果像这样不断的出队，队头左边的空间失去了作用
 *   那队列的容量岂不是越来越小了。
 *
 *    用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定
 *
 *    循环队列：举例
 *    假设一个队列经过反复的入队和出队操作，还剩下两个元素，在“物理”
 *    上分布于数组末尾位置。这时又有一个新元素将要入队。
 *
 *    在数组不断做扩容的前提下，如何让元素入队并确定新的队尾位置呢？
 *    我们可以利用已出队的元素留下的空间，让队尾指针重新指回
 *    数组的首位。
 *    这样一来，整个队列的元素就“循环“起来了，在物理存储上，队尾的位置也可以
 *    在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可
 *
 *    一直到(队尾下标+1) % 数组长度 = 队头下标时，代表队列真的已经满了。需要注意的是，
 *    队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。
 *
 * */

// 循环队列的实现

private int[] array;
private int front;
private int rear;


public MyQueue(int capacity) {
    this.array = new int[capacity];
}



/**
 *
 * 入队
 * @param element 放入元素
 *
 *
 **/
public void enQueue(int element) throws Exception {
    if((rear + 1) % array.length == front) {
        throw new Exception("队列已满！");
    }
    array[rear] = element;
    rear =(rear + 1) % array.length;
}


/**
 * 出队
 *
 *
 * */

public int deQueue() throws Exception {
    if(rear == front) {
        throw new Exception("队列已空！");
    }
    int deQueueElement = array[front];
    front = (front + 1) % array.length;
    return deQueueElement;

}




/**
 *
 *
 * 输出队列
 *
 * */

public void output() {
    for(int i = front; i != rear; i = (i + 1) % array.length) {
        System.out.println(array[i]);
    }
}


public static void main(String[] args)  throws Exception{
    MyQueue myQueue = new MyQueue(6);
    myQueue.enQueue(3);
    myQueue.enQueue(5);
    myQueue.enQueue(6);
    myQueue.enQueue(8);
    myQueue.enQueue(1);
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.deQueue();
    myQueue.enQueue(2);
    myQueue.enQueue(4);
    myQueue.enQueue(9);
    myQueue.output();

栈和队列的应用
* 1.栈的应用
* 栈的输出顺序和输入顺序相反，所以栈通常用于
*对”历史“的回溯，也就是逆流而上追溯”历史“
*例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法调用链
*
*栈还有一个著名的应用场景是面包屑导航，使用护在浏览界面时可以轻松追溯到上一级或更上一级
*页面。
*
* 2.队列的应用
*  队列的输出顺序和输入顺序相同，所以队列通常用于对”历史的回放“也就是按照”历史“的顺序把
*  ”历史“重演一遍。
*  例如：在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列
*  中的次序的。
*  再如网络爬虫实现网站爬取时，也是把待抓取的网站的URL队列当中，
*  再按照存入队列的顺序来依次抓取和解析的。
*
*
*  3.双端队列：
*  双端数列这种数据结构，可以说是综合了栈和队列的优点，对双端队列来说，从队头
*  一端可以入队或者出队，从队尾一端也可以入队或者出队。
*
*
*  4.优先队列
*  还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。
*
* 优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况后面再说
*
*
* */