1. 栈
栈是一种特殊的线性表,栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为
栈顶,另一端为栈底。称栈的结点插入为进栈,结点删除为出栈。因为最后进栈的结点必定最先出
栈,所以栈具有后进先出的特征。
1.1 顺序存储
可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个地
址变量 top指出栈顶结点在数组中的下标。
1.2 链接存储栈
栈也可以用链表实现,用链表实现的栈称为链接栈。链表的第一个结点为顶结点,链表的首结
点就是栈顶指针top,top为NULL的链表是空栈。
2. 队列
队列也是一种特殊的线性表,只允许在一端进行插入,另一端进行删除运算。允许删除运算的那一端称为队首,允许插入运算的一端称为队尾。称队列的结点插入为进队,结点删除为出队。因最先进入队列的结点将最先出队,所以队列具有先进先出的特征。
2.1 顺序存储
可以用顺序存储线性表来表示队列,为了指明当前执行出队运算的队首位置,需要一个指针变量head(称为头指针),为了指明当前执行进队运算的队尾位置,也需要一个指针变量tail(称为尾指针)。
若用有N个元素的数组表示队列,随着一系列进队和出队运算,队列的结点移向存放队列的数组的尾端,会出现数组的前端空着,而队列空间已用完的情况。一种可行的解决办法是当发生这样的情况时,把队列中的结点移到数组的前端,修改头指针和尾指针。另一种更好的解决办法是采用循环队列。
循环队列就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N–1]连接起来。队空的初态为 head=tail=0.在循环队列中,当tail 赶上head时,队列满。反之,当head赶上tail时,队列变为空。这样队空和队满的条件都同为head=tail,这会给程序判别队空或队满带来不便。因此,可采用当队列只剩下一个空闲结点的空间时,就认为队列已满的简单办法,以区别队空和队满。即队空的判别条件是head=tail,队满的判别条件是head=tail+1。
2.2 链接存储
队列也可以用链接存储线性表实现,用链表实现的队列称为链接队列。链表的第一个结点是队
列首结点,链表的末尾结点是队列的队尾结点,队尾结点的链接指针值为NULL.队列的头指针head
指向链表的首结点,队列的尾指针tail指向链表的尾结点。当队列的头指针head值为NULL时,队列
为空。