[TOC]
说明：以下文字来源《大话数据结构》 作者：程杰。
栈
栈是限定仅在表尾进行插入和删除操作的线性表。
很多软件，比如Word，Photoshop等文档或者图像编辑软件中，都有撤销的操作，也是用栈这种方式来实现的，当然不同的软件具体实现代码会有很大差异，不过原理其实都是一样的。
我们把允许插入和删除的一端称为栈顶，另一端称为栈低，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
栈的顺序存储结构及实现
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的。
栈的链式存储结构及实现
栈的链式存储结构，简称为链栈。
想想看，栈只是栈顶来做插入和删除的操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一了，所以比较好的办法是栈顶放在单链表的头部。另外，都已经有了栈顶头部了，单链表中比较常见的头结点也就失去意义了，通常对于链栈来说，是不需要头部结点的。
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机奔溃的情况，而不是这个链栈是否溢出的问题。
对比
他们的时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈要求每个元素都有指针域，这同时增加了一些内存开销，但对于栈的长度是无限制。所以他们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果他的变化在可控范围内，建议使用顺序栈会更好一些。
队列
队列是只允许在一端进行操作，而在另一端进行删除操作的线性表。操作系统也是用这个数据结构来实现排队功能的。
同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。
队列的顺序存储结构
循环队列
线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。我们先来看队列的顺序存储结构。
定义
所以加加假溢出的办法就是后面满了，就在从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
问题
单是顺序存储，若不是循环队列，算法的时间性能不高的，但是循环队列又面临着数组可能会溢出的问题，所以我们还是需要研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过他只能尾进头出而已，我们把它简称为链队列。
对比总结
在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，就用链队列。
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
