2.3.1 物理结构和逻辑结构
什么是数据存储的物理结构呢？
如果把数据结构比作活生生的人，那么物理结构就是人的血肉和骨骼，看得见，摸得着，实实在在。例如我们刚刚学过的数组和链表，都是内存中实实在在的存储结构。
而在物质的人体之上，还存在着人的思想和精神，它们看不见、摸不着。看过电影《阿凡达》 吗？男主角的思想意识从一个瘦弱残疾的人类身上被移植到一个高大威猛的蓝皮肤外星人身上，虽然承载思想意识的肉身改变了，但是人格却是唯一的。
如果把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是数据存储的逻辑结构 。逻辑结构是抽象的概念，它依赖于物理结构而存在。
下面我们来讲解两个常用数据结构：栈和队列。这两者都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。
在后面的章节中，我们会学习到二叉树，这也是一种逻辑结构。同样地，二叉树也可以依托于物理上的数组或链表来实现。
2.3.2 什么是栈
要弄明白什么是栈，我们需要先举一个生活中的例子。
假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口。往圆筒里放入乒乓球，先放入的靠近圆筒底部，后放入的靠近圆筒入口。
那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球优先取出。
栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆筒容器，栈中的元素只能先入后出 （First In Last Out，简称FILO ）。最早进入的元素存放的位置叫作栈底 （bottom），最后进入的元素存放的位置叫作栈顶 （top）。
栈这种数据结构既可以用数组来实现，也可以用链表来实现。
栈的数组实现如下。
栈的链表实现如下。
那么，栈可以进行哪些操作呢？
栈的最基本操作是入栈和出栈，下面让我们来看一看。
2.3.3 栈的基本操作
1. 入栈
入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
这里我们以数组实现为例。
2. 出栈
出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
这里我们以数组实现为例。
由于栈操作的代码实现比较简单，这里就不再展示代码了，有兴趣的读者可以自己写写看。
小灰，你说说，入栈和出栈操作，时间复杂度分别是多少？
入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是以数组还是以链表实现，入栈、出栈的时间复杂度都是O(1) 。
2.3.4 什么是队列
要弄明白什么是队列，我们同样可以用一个生活中的例子来说明。
假如公路上有一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从隧道出口驶出，不允许逆行。
因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序，先驶入的车辆先驶出，后驶入的车辆后驶出，任何车辆都无法跳过它前面的车辆提前驶出。
队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出 （First In First Out，简称FIFO ）。队列的出口端叫作队头 （front），队列的入口端叫作队尾 （rear）。
与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。
用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置 。
队列的数组实现如下。
队列的链表实现如下。
那么，队列可以进行哪些操作呢？
和栈操作相对应，队列的最基本操作是入队和出队。
2.3.5 队列的基本操作
对于链表实现方式，队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说，队列的入队和出队操作有了一些有趣的变化。怎么有趣呢？我们后面会看到。
1. 入队
入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。
2. 出队
出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。
如果像这样不断出队，队头左边的空间失去作用，那队列的容量岂不是越来越小了？例如像下面这样。
问得很好，这正是我后面要讲的。用数组实现的队列可以采用循环队列 的方式来维持队列容量的恒定。
循环队列是什么意思呢？让我们看看下面的例子。
假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队。
在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。
这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。
一直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。
这就是所谓的循环队列，下面让我们来看一看它的代码实现。
1. private int[] array;
2. private int front;
3. private int rear;
4.
5. public MyQueue(int capacity){
6. this.array = new int[capacity];
7. }
8.
9. /**
10. * 入队
11. * @param element 入队的元素
12. */
13. public void enQueue(int element) throws Exception {
14. if((rear+1)%array.length == front){
15. throw new Exception(" 队列已满！");
16. }
17. array[rear] = element;
18. rear =(rear+1)%array.length;
19. }
20.
21. /**
22. * 出队
23. */
24. public int deQueue() throws Exception {
25. if(rear == front){
26. throw new Exception(" 队列已空！");
27. }
28. int deQueueElement = array[front];
29. front =(front+1)%array.length;
30. return deQueueElement;
31. }
32.
33. /**
34. * 输出队列
35. */
36. public void output(){
37. for(int i=front; i!=rear; i=(i+1)%array.length){
38. System.out.println(array[i]);
39. }
40. }
41.
42. public static void main(String[] args) throws Exception {
43. MyQueue myQueue = new MyQueue(6);
44. myQueue.enQueue(3);
45. myQueue.enQueue(5);
46. myQueue.enQueue(6);
47. myQueue.enQueue(8);
48. myQueue.enQueue(1);
49. myQueue.deQueue();
50. myQueue.deQueue();
51. myQueue.deQueue();
52. myQueue.enQueue(2);
53. myQueue.enQueue(4);
54. myQueue.enQueue(9);
55. myQueue.output();
56. }
循环队列不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，还真是有点意思呢！至于入队和出队的时间复杂度，也同样是O(1) 吧？
说得完全正确！下面我们来看一看栈和队列都可以应用在哪些地方。
2.3.6 栈和队列的应用
1. 栈的应用
栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。
例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。
栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。
2. 队列的应用
队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。
例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。
3. 双端队列
那么，有没有办法把栈和队列的特点结合起来，既可以先入先出，也可以先入后出呢？
还真有，这种数据结构叫作双端队列 （deque）。
双端队列这种数据结构，可以说综合了栈和队列的优点，对双端队列来说，从队头一端可以入队或出队，从队尾一端也可以入队或出队。
有关双端队列的细节，感兴趣的读者可以查阅资料做更多的了解。
4. 优先队列
还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。
这种队列叫作优先队列 。
优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况，我们会在下一章进行详细介绍。
好了，关于栈和队列的知识我们就介绍到这里，下一节再见！