数据结构与算法 课件 第3章 栈和队列

3.1栈

3.2队列3.1栈3.1.1栈的定义及基本运算栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。插入、删除的一端称为栈顶(Top)，另一端称为栈底(Bottom)。不含任何元素的空表称为空栈。对于非空栈S = (a1,a2,…,an)，a1是栈底元素，an是栈顶元素。如图3.1所示，进栈的顺序是a1,a2,…,an，出栈的顺序正好相反。因此，栈是一种后进先出的(LastInFirstOut)的线性表。栈的常用基本运算有以下六种：(1) InitStack(&S)栈初始化：操作结果是构造一个空栈S。(2) SetNull(S)置空栈：栈S已存在，将栈S清为空栈。(3) Empty(S)判断栈空：若栈S为空则返回“真”值；否则返回“假”值。(4) Push(S,x)进栈：若栈S不满，将数据元素x插入栈顶，并返回入栈是否成功的状态信息。入栈操作会改变栈的内容。(5) Pop(S,&x)出栈：若栈S非空，删除栈顶数据元素，通过参数x带回栈顶元素，并返回出栈是否成功的状态信息。出栈操作会使栈的内容发生变化。(6) GetTop(S,&x)取栈顶元素：若栈S非空，通过参数x带回栈顶元素，并返回取栈顶元素是否成功的状态信息。该操作完成后，栈的内容不变。3.1.2栈的顺序存储结构和基本运算的实现1．栈的顺序存储结构——顺序栈栈的顺序存储结构简称顺序栈(SequentialStack)。顺序栈采用一维数组来存储，并且用一个整型量Top指示当前栈顶的位置，我们不妨把Top称为栈顶指针。顺序栈的类型定义如下：其中，maxsize是数组空间的长度；datatype是栈中元素的类型。设S是指向SeqStack结构体类型数据的指针。顺序栈本质上是顺序表的简化，我们需要确定用数组的哪一端作为栈底。通常把数组中下标为0的一端作为栈底，那么S->data[0]是栈底元素，S->data[S->Top]是栈顶元素。当S->Top = -1时为空栈，满栈时S->Top=maxsize-1。对于顺序栈，入栈时要先判断栈是否已满，栈满简称为“上溢”；出栈时需判断栈是否为空，栈空简称为“下溢”。入栈操作S->Top加1，出栈操作S->Top减1。图3.2说明了栈中元素和栈顶指针之间的关系。2．顺序栈基本运算的实现1)栈初始化算法3.1建立空顺序栈。2)置空栈算法3.2顺序栈置空。3)判断栈空算法3.3判顺序栈S是否为空栈。4)入栈算法3.4顺序栈入栈。5)出栈算法3.5顺序栈栈顶元素出栈。6)取栈顶元素算法3.6取顺序栈的栈顶元素。3．多个顺序栈共享连续空间在同时使用两个或多个顺序栈时，为了避免某个栈发生上溢，而其余栈还有很多未用空间的情况出现，可让这些栈共享同一个一维数组空间，相互之间调剂余缺，既节约了存储空间，又降低了发生上溢的概率。下面以两个顺序栈共享同一个数组空间的情况进行讨论。两个栈共享一个数组空间的结构类型定义如下：将两个栈的栈底分别固定在一维数组空间的两端，栈顶向中间延伸，空闲区域在数组的中部，如图3.3所示。只有当两个栈占满整个数组空间时(S->Top1+1等于S->Top2)，才会发生上溢。设i表示整型数值，它只取1或者2，分别表示对1号栈或者2号栈进行操作。这里我们只给出两个栈共享空间的入栈和出栈操作。进栈操作的算法如下所示：当存储栈的数组中没有空闲单元时为栈满。此时1号栈的栈顶与2号栈的栈顶处于相邻的位置，即Top1+1 = Top2(或Top1 = Top2-1)。另外，对于2号栈的入栈，Top2应当是减1而不是加1。出栈操作的算法如下所示：当Top1=-1时，1号栈为空；当Top2=maxsize时，2号栈为空。另外，对于2号栈的出栈，Top2应当是加1而不是减1。3.1.3栈的链式存储结构和基本运算的实现1.栈的链接存储结构——链栈栈的链接存储结构简称链栈(LinkedStack)，通常用单链表表示。链栈的结点结构类型定义如下：由于链栈是动态分配元素存储空间的，因此在对栈进行操作时不存在上溢的问题。我们将单链表的表头定义为栈顶。由于只能在栈顶进行入栈和出栈操作，因此只能在表头插入和删除，可以说链栈是操作受限的单链表。既然只能在表头进行操作，所以也就没有必要设置头结点了。如图3.5所示，S是LinkStack类型的指针，指向链栈，可以看作是栈的接口。Top是栈顶指针，指向栈顶结点。当Top等于NULL时为空栈。2．链栈基本运算的实现链栈基本运算的实现实质上是单链表基本运算的简化。由于对栈的操作都是在栈顶(单链表的表头)进行的，因此算法的时间复杂度均为O(1)。1)栈初始化算法3.7建立空链栈。2)置空栈算法3.8链栈置空。3)入栈算法3.9链栈入栈。4)出栈算法3.10链栈栈顶元素出栈。5)取栈顶元素算法3.11取链栈的栈顶元素。3.1.4顺序栈和链栈的比较从时间特性方面来看，实现顺序栈和链栈的所有基本运算的算法，其时间复杂度都是O(1)，因此唯一可以比较的是空间特性。栈初始化时，顺序栈必须确定一个固定的长度作为栈的容量，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现不能入栈的情况，但是每个元素都需要一个指针域，从而又产生了结构性的开销。所以当栈的使用过程中元素个数变化较大时，用链栈是适宜的；反之，应该采用顺序栈。3.2队列3.2.1队列的定义及基本运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，该端称为队尾(Rear)；在表的另一端进行删除，该端称为队头(Front)。当队列中没有元素时称为空队列。队列亦称作先进先出(FirstInFirstOut)的线性表，简称为FIFO表。设队列中的元素为a1,a2,…,an，a1是队头元素，an是队尾元素。队列中的元素都是按照a1,a2,…,an的顺序依次入队和出队的。图3.6是队列的示意图。队列的主要基本运算如下：(1) InitQueue(&Q)队列初始化：构造一个空队列Q。(2) SetNull(Q)置空队：将队列Q清空。(3) Length(Q)求队列长度：返回队列中元素的个数。(4) Empty(Q)判空队：若队列Q为空队列，返回“真”值；否则返回“假”值。(5) EnQueue(Q,x)入队：若队列Q非满，将元素x插入Q的队尾。(6) DeQueue(Q)出队：若队列Q非空，删除队头元素，返回Q的队头元素。(7) GetFront(Q)取队头元素：若队列Q非空，返回Q的队头元素；Q中元素保持不变。3.2.2队列的顺序存储结构和基本运算的实现1．队列的顺序存储结构——顺序队列队列的顺序存储结构称为顺序队列，采用数组存储队列中的元素。本书约定，在非空队列中队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置。如果是空队，队头、队尾指针相等。队尾指针减去队头指针就是队列的长度。当然也可以约定队头指针front指向队头元素的位置，队尾指针rear指向队尾元素的后一个位置。顺序队列的结构类型定义如下：顺序队列中出队、入队操作的情况如图3.7所示。顺序队列中可能出现“上溢”和“下溢”现象，并且还存在“假上溢”现象。也就是说，尽管队列的数组空间虽然未被占满，但尾指针已达到数组的上界而不能进行入队操作。例如在图3.7(c)或(d)的情况下，再进行入队操作，则会出现“假上溢”。采用循环队列(CircularQueue)的方法可以较好地解决“假上溢”问题，即将数组看作一个首尾相接的圆环，如图3.8所示。在循环队中通过取模运算修改队尾指针和队头指针，具体描述为：在循环队列中，入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针。由图3.9可以看出，在队空和队满时都有sq->front等于sq->rear，无法区分空队和满队。通常采用少用一个元素空间的方法来解决这个问题，如图3.10所示。判断空队和满队的条件分别是：2．循环队列基本运算的实现我们用前面所述方法来实现循环队列上的基本运算。1)队列初始化算法3.12生成空循环队列。对于循环队列来说，只要队头和队尾指针相等即为空队，所以这里置为0～maxsize-1之间的任何一个值都可以，但一般置为0。2)置空队算法3.13循环队列置空。3)求队列长度算法3.14求循环队列长度。4)入队算法3.15循环队列入队。5)出队算法3.16循环队列出队。6)取队头元素算法3.17取循环队列的队头元素。3.2.3队列的链式存储结构和基本运算的实现1．队列的链式存储结构——链队列队列的链式存储结构简称链队列，它是仅限在表头删除和表尾插入的单链表。为了便于在表尾做插入操作，需要增加一个尾指针，指向单链表中的最后一个结点。我们将链队列的头指针和尾指针封装在一起作为一个结构体。下面是其类型定义：为了运算方便，链队列中通常也带有头结点。图3.11给出了链队列的示意图，图中q为L