1. 栈（stack）
栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。它是后进先出（LIFO）的。对栈的基本操作只有 push（进栈）和 pop（出栈）两种，前者相当于插入，后者相当于删除最后的元素。
1）顺序存储栈：顺序存储结构
2）链栈：链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
3）两个栈共用静态存储空间,对头使用也存在空间溢出问题。栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是top[1]+1=top[2]。
4）基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
5）对于n各元素的入栈问题，可能的出栈顺序有C(2n,n)/(n+1)个。
6）堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的
2. 队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
2.1 循环队列
当用线性表表示队列时，为了避免队列元素的大量移动（队头删除元素时），一般引入两个指针，front指向队头元素，rear指向队尾元素的下一个位置，这样，拆入始终在rear指针处进行，删除始终在front指针处进行；当front等于rear时，此队列为空队列。但是这样会产生另外一个问题，列队经过一些拆入和删除操作之后，rear指针可能发生数值越界，但数值的另一端还有空闲，这种现象叫做假溢出。
解决假溢出的办法就是后面满了，再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。如下图所示
此时会产生另外一个问题，当rear=front时，有可能表示队满，也可能表示队空，为了区分这种情况有两种解决方案
多设置一个flag变量，当rear=front，且flag=0时，表示队列空。当rear=front，且flag=1时表示队满，让队列始终保留一个空元素，也就是，当rear=front时，队列空。当队列仅剩一个空闲元素时，队列慢，所以以下两种情况都表示队列满
2.2 队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出，我们把它简称连队列
当front和rear都指向头结点时，表示连队列为空。
网友评论