1.5.2 栈与队列
栈与队列是另外两种重要的线性结构，它们可以使用上面所讲的顺序表或者链表的结构来最终实现。
1．栈
栈可看成一种“特殊”的线性表，该线性表限定仅在表尾进行插入和删除操作。栈主要应用于表达式的计算、子程序嵌套调用、递归调用等。
栈具有下述特殊的性质：
（1）通常称插入、删除的这一端为栈顶（Top）；另一端称为栈底（Bottom）。
（2）当表中没有元素时称为空栈。
（3）栈的修改是按“后进先出”的原则进行，因此栈简称为LIFO（Last In First Out）表。每次删除（退栈）的总是当前栈中“最新”的元素，即最后插入（进栈）的元素，而最先插入的元素是被放在栈的底部，要到最后才能删除。
栈的示意图如图1-5所示。
图1-5 栈的示意图
和线性表类似，栈也有两种存储表示方法，即顺序栈和链栈。顺序栈指的是栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。设置栈顶指针为top，它指示栈顶元素在顺序栈中的位置；栈底指针为base，它始终指向栈底的位置。初始时，top指向栈底，每当插入一个元素时，top++；删除栈顶元素时，top--，因此，非空栈中的top始终在栈顶元素的下一个位置。
链栈的定义和操作与链表类似，易于实现，不再赘述。
2．队列
和栈相反，队列是一种先进先出（First In First Out，FIFO）的线性表，它只允许在表的一端进行插入元素，而在另一端删除元素。
队列有下述特殊性质：
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列的结构特点是先进队的元素先出队。假设有队列Q=（a1，a2，…，an），则队列Q中的元素是按a1，a2，…，an的次序进队，而第一个出队的应该是a1，第二个出队的应该是a2，只有在ai-1出队后，ai才可以出队（1≤i≤n）。
（5）队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许“加塞”），每次离开的成员总是队头元素，即当前“最老的”成员，而不允许中途离队。
队列的示意图如图1-6所示。
图1-6 队列的示意图
和线性表类似，队列也有两种存储结构，即顺序存储结构（循环队列）和链式存储结构（链队列）。
和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，尚需设置两个指针front和rear，它们分别指示队列的头元素和尾元素。初始时，令front=rear=0，每当插入1个新的元素，rear增加1；每当删除1个新的元素，front增加1；当front=rear时，队列为空。这种操作方式会导致一个新的情况：如果插入和删除的元素越来越多，rear的值将一直增加，最终达到所分配存储单元的最大值，当要继续插入新的元素时，队尾已没有空间了。但如果front>0，此时第0个单元至第front-1个单元的存储空间并未占用。那么，该如何利用这部分可用空间呢？一个较为巧妙的办法是将顺序队列构造为一个环状的空间，称为循环队列。这样，空间就可以循环利用了。
在一个链队列中，需要两个分别指示队头和队尾的指针才能唯一确定，其操作即为线性链表的插入和删除操作的特殊情况，只是尚需修改队尾指针或队头指针。