【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[148]篇文章，欢迎阅读收藏】
1 基本概念
栈 (Stack) 是一种后进先出 (last in first off ， LIFO) 的数据结构，而队列 (Queue) 则是一种先进先出 (fisrt in first out ， FIFO) 的结构。
2 术语解释
对于栈而言，允许进行插入，删除操作的一端被称为 栈顶（ top ） , 另一端则被称为 栈底（ bottom ） 。
如果一个栈不包含任何元素，那么这个栈就被称为 空栈 。
从栈顶插入一个元素被称为 入栈（ push ） ，将一个元素从栈顶删除被称为 出栈（ pop ）
对于队列而言，只允许在表的 前端 (front) 进行删除操作，只允许在表的 后端（ rear ） 进行插入操作，进行插入操作的端称为 队尾 ，进行删除的端称为
对头 。如果队列中不包含任何元素，该队列就被称为 空队列 。
对于一个队列来说，每个元素总是从队列的 rear 端进入队列，然后等待该与元素之前的所有元素出对之后，当前元素才能出对。
3 详细说明
3.1 栈的顺序存储结构及实现
顺序存储结构的栈简称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变，它的栈顶可以直接通过顺序栈底层数组的数组元素 arr[size-1] 来访问。
顺序栈中数据元素的物理关系和逻辑关系是一致的，先进栈的元素位于栈底，栈底元素的存储位置相对也比较小。
进栈
对于顺序栈的进栈操作而言，只需将新的数据元素存入栈内，然后让记录栈内元素个数的变量加 1 ，程序即可再次通过 arr[size-1] 重新访问新的栈顶元素。进栈操作示意图如下：
由于顺序栈底层通常会采用数组来保存数据元素，因此可能出现的情况是：当程序试图让一个数据元素进栈时，底层数据已满，那么就必须扩充底层数组的长度来容纳新进栈的数据元素。
出栈
对于顺序栈的出栈操作而言，需要将栈顶元素弹出栈，程序要做两件事。
让记录栈内元素个数的变量减 1.
释放数组对栈顶元素的引用。
出栈操作示意图如下图 :
对于删除操作来说，只要让记录栈内元素个数的 size 减 1 ，程序即可通过 arr[size-1] 访问到新的栈顶元素。但不要忘记释放原来栈顶的数组引用，否则会引起内存泄漏。
栈比普通线性表的功能更弱，栈时一种被限制过的线性表，只能从栈顶插入，删除数据元素。
3.2 栈的链式存储结构及实现
程序可以采用单链表来保存栈中所有元素，这种链式结构的栈也被称为栈链。对于栈链而言，栈顶元素不断地改变，程序只要使用一个 top 引用来记录当前的栈顶元素即可。 top 引用变量永远引用栈顶元素，再使用一个 size 变量记录当前栈中包含多少个元素即可。
3.3 队列的顺序存储结构及实现
系统采用一组地址连续的存储单元依次存放队列从 rear 端到 front 端的所有数据元素，程序只需 (front 和 rear 两个整型变量来记录队列 front 端的元素索引、 rear 端的元素索引。
3.4 队列的链式存储结构及实现
使用链式结构保存线性表，也可以采用链式结构来存储队列的各元素，采用链式存储结构的队列也被称为链队列。
对于链队列而言，由于程序需要从 rear 端添加元素，然后从 front 端移除元素，因此考虑对链队列增加 front,rear 两个引用变量，使他们分别执行链队列的头，尾两个节点。
閱讀更多 情報通 的文章
