小结

本章介绍了两种特殊的线性表：栈和队列。栈是插入和删除操作限制在表尾一端进行，无论是在栈中插入数据元素还是删除栈中数据元素，都只能固定在线性表的表尾进行。通常将进行插入和删除操作的这一端称为“栈顶”，而另一端称为“栈底”。它是一种具有“后进先出”或“先进后出”特性的线性表。队列是插入操作只限制在表尾进行，而删除操作只限制在表头进行。通常将允许进行插入操作的一端称为“队尾”，而将允许进行删除操作的另一端称为“队首”。它是一种具有“先进先出”或“后进后出”的线性表。

栈的基本操作主要包括判栈是否为空、出栈、入栈和取栈顶元素等。队列的基本操作主要包括判队列是否为空、出队、入队和取队首元素等。这些操作的时间复杂度都是O（1）。

栈与队列都可用顺序和链式两种存储方式加以实现，为此有顺序栈和链栈、顺序队列和链队列之分。其中：顺序栈和顺序队列用数组实现；链栈和链队列则用单链表进行存储。读者要注意的是，链栈结点中指针的指向是从栈顶开始依次向后链接的，也就是说链栈中结点的指针不像单链表那样是指向它在线性表中的后继，而是指向其在线性表中的前驱。链队列结点的链接方向与单链表相同，但为了便于实现插入和删除操作，链队列除了引进一个队首指针外，还引进了队尾指针来指向队尾元素，并将两者组合形成一个队列结构类型。

顺序栈比链栈的使用更为广泛。在顺序栈中，注意掌握入栈和出栈操作，特别是在入栈操作前要进行的判满条件和在出栈操作前要进行的判空条件。在链栈中的操作与单链表操作类似，而且由于入栈与出栈操作都是固定在链栈的栈顶位置进行，所以实现起来比单链表相应操作更为简单。

循环队列比非循环队列使用更为广泛。在顺序存储方式下，也要注意掌握队列的入队和出队操作、队列判空与判满的条件，以及队列“假溢出”的处理方法。循环顺序队列就是为了避免“假溢出”现象而提出的一种队列。它是一个假想的环，是通过取模运算来使其首尾相连。特别要注意的是，在循环顺序队列中的入队和出队操作实现与在非循环顺序队列中的入队和出队操作实现的不同点在于，队首和队尾指针的变化不再是简单的加1或减1，而需加1或减1后再做取模运算。在循环顺序队列中为了区分队列的判空和判满条件，特别提出了三种解决方法：第一种是少用一个存储单元；第二种是设置一个标志变量；第三种是设置一个计数变量。链队列中的操作也与单链表中的操作类似，而且由于入队操作总是固定在链队列的队尾进行，而出队操作总是固定在链队列的队首进行，所以链队列的入队和出队操作实现起来非常简单。

栈与队列是两种十分重要的，并且应用非常广泛的数据结构。常见的栈的应用包括分隔符匹配问题的求解，表达式的转换和求值，函数调用和递归实现和深度优先搜索遍历等。凡是遇到对数据元素的读取顺序与处理顺序相反，都可考虑使用栈将读取到而又未处理的数据元素保存在栈中。常见的队列的应用包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。凡是遇到对数据元素的读取顺序与处理顺序相同，都可考虑使用队列来保存读取到而未处理的数据元素。

优先级队列是带有优先级的队列。优先级队列中的每一个数据元素都有一个优先权。优先权可以比较大小，它既可以在数据元素被插入优先级队列时被人为赋予，也可以是数据元素本身所具有的某一属性。优先权的大小决定着该对象接受服务的先后顺序，所以也将其称为优先级。优先级队列不同于一般的队列，它是按照数据元素优先级的高低来决定出队的次序，而不是按照数据元素进入队列的次序来决定的。一般队列也可以被看作是一种特殊的优先级队列。在一般队列中，数据元素的优先级由其进入队列的时间确定，时间越长，优先级越高。优先级队列的实现方法可以采用有序、无序线性表或堆来实现。本章只介绍了在有序线性表上实现的优先级队列。在这种情况下，入队操作是进行数据元素的有序插入，即将待插入的数据元素插入队列中的适当位置，并使插入后的队列仍按照优先级从大到小的顺序排放，入队操作的时间复杂度为O（n）。出队操作只要将队首元素（即优先级最高的元素）从队列中删除即可，其时间复杂度为O（1）。在一些实际应用中，若需要采用一种数据结构来存储数据元素，对这种数据结构的要求是：数据元素加入的次序是无关紧要的，但每次取出的数据元素应是具有最高优先级的数据元素，这时就可以采用优先级队列来解决问题。

其实利用栈和队列的思想还可以设计出其他一些变种的栈和队列结构。例如双端队列，双端栈等，这些都是根据插入与删除操作位置受限的不相同而得名的。双端队列是指插入和删除操作限制在线性表的两端进行；双端栈是指两个底部相连的栈，它是一种添加限制的双端队列，并且规定从一端插入的数据元素只能从这一端删除。这些变种的栈和队列在某些特定情况下具有很好的应用价值。