1.概述

　　　　我们知道，程序就是用来处理数据的。对于每一件现实中的问题，我们也是将其抽象成数据+对数据的操作。所以数据的格式决定着我们操作他们的形式。

　　　　我们可以想象在超市中排队结账的情景，很多人排成一条长队，而新来的人要排在队的后面，结账的人一定是在队列最前面的人。（不考虑没有素质的行为）

　　　　我们还可以想象在我们将一件件衣服叠好，放在衣柜或者箱子里面的过程，最上面的一件，一定是最后放进去的，最下面的一定是第一件放进去的。。

　　　　同理，在进算计中也有模拟这些情况的数据结构，我们称之为队列和栈。

2.基本概念

　　　　2.1 栈 

　　　　　　　　栈是一种先进后出的数据结构，他要求只能对一端进行操作，每次只能操作处于逻辑最前面的元素。

　　　　　　　　例如我们使用数组的时候，栈要求我们只能操作最后一个进入数组的元素（元素按顺序摆放，没有空隙）。

　　　　2.2 队列

　　　　　　　　队列是一种先进先出的数据结构，他要求同时对两端进行操作，但是要求逻辑头只能进行元素出队列（删除）操作；逻辑尾只能进行入队列（元素添加）操作，就好比排队一样。

　　　　2.3 栈与队列的区别

　　　　　　　　首先，栈与队列都是线性结构（使用数组或者顺序表实现），栈的特点是先进入的元素后出来，利用这种结构可以记录层级关系，例如函数调用关系，嵌套的层级关系，表达式的计算等。

　　　　　　　　队列的特点是先进先出，利用这种结构可以记录顺序，例如消息的排序，记录操作的先后顺序等。

3.栈的实现

　　　　3.1 数组实现

　　　　　　　　栈的数组实现非常简单，首先声明一个数组，然后再定义一个变量P用来保存当前操作位置，每次元素入栈就在P指定的位置入该元素，然后向前移动P的位置；每次出栈将当前P指向的元素删除，然后再向后移动

　　　　　　　　P的位置。这样就保证了只对数组的一端进行操作，形成了栈结构。

　　　　3.2 链表实现

　　　　　　　　　与数组类似，每次有新元素加入，就给链表的尾部加入一个新的节点；每次有元素出栈，就删除链表最后一个节点。

4.队列的实现

　　　　4.1 链表实现

　　　　　　　　　　链表实现的队列比较简单，每次有新的元素加入，就在链表的尾部加入一个新节点；每次有元素出队列，就删除链表的第一个节点。

　　　　4.2 数组实现

　　　　　　　　　　队列的数组实现比较麻烦，他要求有两个变量 p、q分别表示当前队列的头和尾，每次有新元素，就放入队尾指针的位置，然后队尾指针向后移动；

　　　　　　　　　　每次要出队列的时候就将队头指针的数据删除，然后队头指针向后移动。 可以发现，当进行一定次数的操作之后，由于队头指针向后移动，将导致整个数组资源浪费（即队头指针跑到了队尾），为了

　　　　　　　　　　解决这个问题，循环队列就产生了

　　　　4.3 循环队列

　　　　　　　　　　循环队列就是逻辑上将数组头尾相接，形成一个圈，当队尾到达数组尾部的时候，由于之前出队列导致数组的头部并没有元素，这是我们可以将队尾元素存在这里，形成一个环，避免了资源浪费。

　　　　　　　　

5. 推荐阅读：