一：物理结构和逻辑结构
除了数组和链表之外，常用过的数据结构还有很多，但大对数
* 都以数组或链表作为存储方式。数组和链表可以被看作数据存储
* 地‘物理结构“
*
* 什么是数据存储的物理结构呢？
* 如果把数据结构比作活生生的人，那么物理结构就是人的血肉
* 和骨骼，看得见，摸得着，实实在在。例如我们刚刚学过的数组和链表，都是内存中实实在在
* 存储结构
* 而在物质人体之上，还存在着人的思想和精神，它们看不见，摸不着。
* 看过电影《阿凡达》的：男主角的思想意识从认识一个瘦弱残疾的人类身上被移植
* 到一个高大威猛的蓝皮肤外星人身上，虽然承载着思想意识的肉身改变了，但是人格确实唯一的。
* 如果把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是
* 数据存储的逻辑结构。逻辑结构实是抽象的概念，它依赖于物理结构存在。
* 逻辑结构 线性结构：举例(顺序表、栈、队列)
* 非线性结构 举例(数、图)
*
* 物理结构 顺序存储结构 举例(数组)
* 链式存储结构 举例(链表)
二：栈和队列
什么是栈？
* 假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口，往圆筒里面放入兵乓球，先放入
* 的靠近圆筒底部，后放入的靠近圆筒入口。
* 那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出
* 后放入的，再取出先放入的，而不能把最里面最先放入的乒乓球优先取出
* 。
* 栈：是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆通容器，栈中的元素只能
* 先入后出(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();
循环队列不但可以充分利用数组的空间，还避免了数组元素整体移动的麻烦 ， 至于入队和出队的时间复杂度，也同样是O(1)
三：栈和队列的应用
栈和队列的应用
* 1.栈的应用
* 栈的输出顺序和输入顺序相反，所以栈通常用于
*对”历史“的回溯，也就是逆流而上追溯”历史“
*例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法调用链
*
*栈还有一个著名的应用场景是面包屑导航，使用护在浏览界面时可以轻松追溯到上一级或更上一级
*页面。
*
* 2.队列的应用
* 队列的输出顺序和输入顺序相同，所以队列通常用于对”历史的回放“也就是按照”历史“的顺序把
* ”历史“重演一遍。
* 例如：在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列
* 中的次序的。
* 再如网络爬虫实现网站爬取时，也是把待抓取的网站的URL队列当中，
* 再按照存入队列的顺序来依次抓取和解析的。
*
*
* 3.双端队列：
* 双端数列这种数据结构，可以说是综合了栈和队列的优点，对双端队列来说，从队头
* 一端可以入队或者出队，从队尾一端也可以入队或者出队。
*
*
* 4.优先队列
* 还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。
*
* 优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况后面再说
*
*
* */