1.4.1 栈及其基本运算
　　1.4.2 队列及其基本运算

　　1.4.1 栈及其基本运算　
　   1. 什么是栈
　  栈实际上也是线性表，之不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型的线性表的插入与删除运算是不需要移动表中的其他数据元素的这种线性表称为栈。
　  栈 stack 是限定在一端进行插入与删除的线性表。
　  在栈中，允许插入与删除的一端为栈顶，而不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。即栈事实按照“先进后出” (FILO-First In Last Out) 或“后进先出” (LIFO-Last In First Out) 的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。
　  通常用指针 top 来指示栈顶的位置，用指针 bottom 指向栈底。
　  往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。栈顶指针 top 动态反映了栈中运算的变化情况。
　  图 1.9 是栈的示意图。
　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图1.9　栈示意图
　  栈这种数据结构在日常生活中也是常见的。例如，子弹夹是一种栈的结构，最后压入的子弹总是最先被弹出，而最先压入的子弹最后才能被弹出。又如，在用一端为封闭另一端为开口的容器装物品时，也是遵循 “先进后出”或“后进先出”原则的。
　  2. 栈的顺序存储及其运算
　  与一般的线性表一样，在程序设计语言中，用一维数组 S(1:m) 作为栈的顺序存储空间，其中为栈的最大容量。通常，栈底指针指向栈的空间的低地址一端（即数组的起始地址这一端）。图 1.10 （ a ）是容量为 10 的栈顺序存储空间，栈中已有 6 个元素；图 1.10 （ b ）与图 1.10 （ c ）分别为入栈与退栈后的状态。
　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　图1.10 栈在顺序存储结构下的运算

　  在栈的顺序存储空间 S(1:m) 中，通常为栈底元素（在栈非空的情况下）， S(top) 为栈顶元素。 Top=0 表示栈空； Top=m 表示栈满。
　  栈的基本运算有三种：入栈、退栈与读栈顶元素。下面分别介绍在顺序存储结构下栈的这三种运算。
　  （ 1 ）入栈运算
　  入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一（即 top 加 1 ），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢“错误。
　  （ 2 ）退栈运算
　  退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的运算）赋给一个指定的变量，然后将栈顶指针退一（即 top 减 1 ）。
　  （ 3 ）读栈顶元素
 　 读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。
　  当栈顶指针为 0 时，说明栈空，读不到栈顶元素。

1.4.2 队列及其基本运算

　　1. 什么是队列
　  在计算机系统中，如果一次只能执行一个用户程序，则在多哥用户程序需要执行时，这些用户程序必须先按照到来的顺序进行排队等待。这通常是由计算机操作系统来进行管理的。
　  在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是：
　  · 初始时线性表为空；
　  · 当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待；
    · 当计算机系统执行完当前的用户程序后，就从线性比扫的头部取出一个用户程序执行。
　  由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。
　  队列 (queue) 是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端为队尾通常用一个称为尾指针 (rear) 的指针向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为排头（也称为队头），通常也用一个排头指针 (front) 指向排头元素的前一位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后能被删除。因此，它体现了“先进后出” (FILO-First In Last Out) 或“后进先出” (LIFO-Last In First Out) 的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针 rear 与排头指针 front 共同反映了队列中元素动态变化的情况。图 1.11 是具有 6 个元素的队列示意图。
　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　图1.11　具有六个元素的队列的示意图
　　往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。
　  图 1.12 是在队列中进行插入与删除的示意图。由图 1.12 可以看出，在队列的末尾插入一个元素（入队运算）只涉及队尾指针 rear 的变化，而要删除队列中的排头元素（退队运算）只涉及指针 front 的变化。
　  与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。
　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　图1.12 队列运算示意图
　　2. 循环队列及其运算
　  在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
　  所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图 1.13 所示。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。
　  在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置，因此，从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的位置之间所有的元素均为队列的元素。
　  循环队列的初始状态为空，即 rear ＝ front ＝ m ，如图 1.13 所示。
　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　图1.13　循环队列存储示意图
　　循环队列主要有两种基本运算：入队运算与退队运算。
　  每进行一次入队运算，队尾指针就进一。当队尾指针 rear=m+1 时，则置 rear= 1 。
　  每进行一次退队运算，排头指针就进一。当排头指针 front=m+1 时，则置 front= 1 。
　  图 1.14 （ a ）是一个容量为 8 的循环队列存储空间，且其中已有 6 个元素。图 1.14 （ b ）是在图 1.14 （ a ）的循环队列中又加入了 2 个元素后的状态。图 1.14 （ c ）是在图 1.14 （ b ）的循环队列中退出了 1 个元素后的状态。
　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　图1.14　循环队列示意图
　　由图 1.14 中循环队列动态变化的过程可以看出，当循环队列满时有 front=rear, 而当循环队列空时也有 front=rear 。即在循环队列中，当 front=rear 时，不能确定是队列满还是队列空。在实际使用循队列时，为了能区分队列满还是队列空，通常还需要增加一个标志 s ， s 值的定义如下：
　　Ｓ＝0 表示队列空
　  Ｓ＝1  表示队列非空
　　由此可以得出队列空与队列满的条件如下：
　  队列空的条件为 s=0 ；
　  队列满的条件为 s=1 且 front=rear 。
　  下面具体介绍循环队列入队与退队的运算。
　  假设循环队列的初始状态为空，即： s=0 ，且 front=rear=m 。
　  · 入队运算
　  入队运算是指在循环队列的队尾加入一个新元素。这个新元素有两个基本操作：首先将队尾指针进一（即 rear=rear+1 ），并当 rear=m+1 时置 rear=1 ；然后将新元素插入到队尾指针指向的位置。当循环队列非空（ s=1 ）且队尾指针等于排头指针时，说明循环队列已满，不能进行入 队运算，这种情况称为“上溢”。
　  · 退队运算
　   退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将排头指针进一（front=front+1 ） , 并当 front=m+1 时置 front=1 ；然后将排头指针指向的元素赋给指定的变量。当循环队列为空（ s=0 ）时，不能进行退队运算，这种情况称为“下溢”。