第三章 栈和队列

　　栈 (stack) ：是限定仅在表尾进行插入或删除操作的线性表。 因此， 对栈来说， 表尾端有其特殊含义， 称为栈顶 (top), 相应地， 表头端称为栈底 (bottom)。 不含元素的空表称为空栈。假设栈 S = (a1, a2, …，an)， 则称 a1为栈底元素， an为栈顶元素。栈中元素按 a1, a2, ···, an的次序进栈， 退栈的第一个元素应为栈顶元素。 换句话说， 栈的修改是按后进先出的原则进行的， 如图 3.1 (a)所示。 因此， 栈又称为后进先出 (Last In First Out, LIFO)的线性表， 它的这个特点可用图 3.1(b) 所示的铁路调度站形象地表示。

在程序设计中，如果需要按照保存数据时相反的顺序来使用数据， 则可以利用栈来实现。 

　　和栈相反，队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾(rear), 允许删除的一端则称为队头(front)。假设队列为q =(a1, a2, …，an), 那么， a,就是队头元素， an则是队尾元素。队列中的元素是按a1,a2,…，an的顺序进入的，退出队列也只按照这个次序依次退出，也就是说，只有在 a1,a2, …，an -I都离开队列之后， an才能退出队列。图3.2所示为队列的示意图。

　　队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出做输出操作。凡是申请输出的作业都从队尾进入队列。