2.数据结构——栈与队列

栈的定义

先进后出就是栈

在生活中，像浏览器的后退，以及各类软件的撤销操作，都是可以用栈的方式来实现。

栈是限定仅在表尾进行插入和删除操作的线性表

允许插入和删除的一端称为栈顶（top）

另一端称为栈底（boottom）

不含任何数据元素的栈称为空栈

栈又称为后进先出（Last In First Our）的线性表，简称LIFO结构

栈的抽象数据类型

ADT 栈(stack)
Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后堆关系。
Operation
	InitStack ( *S )：初始化操作.建立一个空栈S。
	DestroyStack ( *S )：若栈存在，則销毁它。
	ClearStack (*S)：将栈清空。
	StackEmpty ( S ):若栈为空，返回true,否則返回 false。
	GetTop (S,*e)：若栈存在且非空，用e返回S的栈顶元素。
	Push (*S,e)：若栈S存在，插入新元素e到栈S中并成为栈頂元素。
	Pop (*S,*e)：删除栈S中栈顶元素，并用e返回其值。
	StackLength (S)：返回回栈S的元素个数。
endADT

栈的顺序存储结构及实现

进栈及出栈的时间复杂度都是O(1)

两栈共享空间

其实栈的顺序存储还是挺方便的，因为它只准栈顶进出元素，所以不存在线性表在插入和删除时需要移动元素的问题。不过他有一个很大的缺陷，就是必须实现确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数据的容量，非常麻烦。
这里考虑的是两个栈共享空间。

使用这样的数据结构时，比较适用于此消彼长的情况，比如买卖股票，有买入，有卖出，这样使用两栈共享空间才有比较大的意义。否则两个栈都在不停增长，那么很快就会栈溢出了。

栈的链式存储结构及实现

简称链栈

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。

对比顺序栈和链栈，它们的时间复杂度的都是O(1)。

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，使用顺序栈会好一些。

栈的应用——递归

栈的应用——四则运算表达式

逆波兰

1. 转为后缀表达式
2. 从左到右遍历表达式
3. 遇到数字进栈，遇到符号，就将栈顶的两个数字出栈进行运算，再将结果进栈

中缀表达式转为后缀表达式

我们平时使用的标准四则运算表达式叫做中缀表达式

转换规则：

1. 从左到右遍历中缀表达式的每个数字和符号
2. 数字输出，符号则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

队列的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的抽象数据类型

ADT 队列(Queue)

Data
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。

Operation
	InitQueue(*Q)：初始化操作，建立一个空队列Q。
	DestroyQueue(*Q)：若队列Q存在，則销毀它。
	ClearQueue(*Q)：将队列 Q 清空。
	QueueEmpty(Q)：若队列Q为空，送回true,否則退回false。
	GetHead(Q, *e)：若队列Q存在且非空，用e返因队列Q的队头元素。
	EnQueue(*Q,e)：若队列Q存在，插入新元素e到队列Q中并成为队尾元素。 
	DeQueue(*Q, *e)：刪除队列Q中队头元素，并用e返回其值。	
	QueueLength(Q)：送回队列Q的元素个教。
endADT

循环队列

队列的头尾相接的顺序存储结构称为循环队列

队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

在可以确定队列长度最大值的情况下，建议使用循环队列，如果无法预估队列的长度，则使用链队列。

总结及回顾

栈和队列都可以使用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化的利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化，解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1).