第3部分栈和队列

《第3部分栈和队列》由会员分享，可在线阅读，更多相关《第3部分栈和队列（54页珍藏版）》请在金锄头文库上搜索。

1、第3部分栈和队列Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望3.1 3.1 栈栈3.2 3.2 队列队列3.1 3.1 栈栈3.1.1 3.1.1 栈的定义栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入和栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所删除数据元素的操作只能在线性表的一端进行。如下所示：示： 进行插入和删除的一端是浮动端，通常被称为进行插入和删除的一端是浮动端，通常被称为栈顶栈顶，并用一个并用一个“栈顶指针栈顶指针

2、”指示；而另一端是固定端，通常指示；而另一端是固定端，通常被称为被称为栈底栈底。我们经常将栈用下图。我们经常将栈用下图3-1的形式描述：的形式描述：a1, a2, a3, ., an 插入和删除端插入和删除端图图 3-1 结论：结论：后进先出后进先出（Last In First Out），简称为），简称为LIFO线性表。线性表。 举例举例1：家里吃饭的碗，通常在洗干净后一个一个地：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。拿走最上面的那只碗，而最后拿出最下面

3、的那只碗。 举例举例2：在建筑工地上，使用的砖块从底往上一层一：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。层地码放，在使用时，将从最上面一层一层地拿取。 下面我们先给出栈结构的基本操作：下面我们先给出栈结构的基本操作： （1）初始化栈）初始化栈 InitStack(S) （2）入栈）入栈 Push(S,item) （3）出栈）出栈 Pop(S,item) （4）获取栈顶元素内容）获取栈顶元素内容 GetTop(S,item) （5）判断栈是否为空）判断栈是否为空 StackEmpty(S) 3.1.2 3.1.2 栈的顺序存储栈的顺序存储 栈的顺序存储

4、结构是用一组连续的存储单元依次栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。存放栈中的每个数据元素，并用起始端作为栈底。 类型定义如下所示：类型定义如下所示： #define MAX_STACK 10 /栈的最大数据元素数目栈的最大数据元素数目 typedef struct stack StackEntry itemMAX_STACK; /存放栈中数据元素的存储单元存放栈中数据元素的存储单元 int top; /栈顶指针栈顶指针 STACK;基本操作算法：基本操作算法：1. 初始化栈初始化栈S void InItStack(STACK *S) s-top

5、=-1; 2. 入栈入栈 void Push(STACK *S,StackEntry item) if (S-top=MAX_STACK-1) exit(“Stack is full”); else S-item+S-top=item;图图 3-23. 出栈出栈 void Pop(STACK *S,StackEntry *item)if (StackEmpty(*S) exit(“Stack is empty”); else *item=S-itemS-top-;4. 获取栈顶元素内容获取栈顶元素内容 void GetTop(STACK S,StackEntry *item)if (Stack

6、Empty(S) exit(“Stack is empty”); else *item=S.itemS.top; 5. 判断栈判断栈S是否为空是否为空 int StackEmpty(STACK S) if (S.top=-1) return TRUE; else FALSE; 结论：由于栈的插入和删除操作具有它的特殊性，结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。就没有摆脱。3.1.3 3.1.3 栈

7、的链式存储栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作式存储结构表示的栈称作“链栈链栈”。链栈通常用一个。链栈通常用一个无头结点的单链表表示。如图无头结点的单链表表示。如图3-3所示。所示。 由于栈的插入删除操作只能在一端进行，而对于由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即易一些，所以，

8、我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。将单链表的头指针作为栈顶指针。 top图 3-3栈的链式存储结构在栈的链式存储结构在C语言中可用下列类型定义实现：语言中可用下列类型定义实现：type struct node /链栈的结点结构链栈的结点结构 StackEntry item; /栈的数据元素类型栈的数据元素类型 struct node *next; /指向后继结点的指针指向后继结点的指针NODE; typedef struct stack NODE *top;STACK; 下面我们将给出链栈各项基本操作的算法。下面我们将给出链栈各项基本操作的算法。1. 初始化栈初始化

9、栈S void InitStack(STACK *S) S-top=NULL;2. 入栈入栈 void Push(STACK *S,StackEntry item) p=(NODE*)malloc(sizeof(NODE); if (!p) exit(OVERFLOW); else p-item=item; p-next=S-top; S-top=p; 3. 出栈出栈void Pop(STACK*S, StackEntry *item)if (StackEmpty(*S) exit(“Stack is empty”);else *item=S-top-item; p=S-top; S-top=

10、p-next; free(p); 4. 获取栈顶元素内容获取栈顶元素内容 void GetTop(STACK S,StackEntry *item) if (StackEmpty(S) exit(“Stack is empty”); else *item=S.top-item;5. 判断栈判断栈S是否空是否空 int StackEmpty(STACK S) if (S.top=NULL) return TRUE; else FALSE;3.1.4 3.1.4 栈的应用举例栈的应用举例 【举例举例1 1】将从键盘输入的字符序列逆置输出将从键盘输入的字符序列逆置输出 比如，从键盘上输入：比如，从键

11、盘上输入：tset a si sihT；算法将输出：；算法将输出：This is a test 下面我们给出解决这个问题的完整算法。下面我们给出解决这个问题的完整算法。 typedef char StackEntry; void ReverseRead( ) STACK S; /定义一个栈结构定义一个栈结构S char ch; InitStack(&S); /初始化栈初始化栈while (ch=getchar()!=n) /从键盘输入字符，直到输入换行符为止从键盘输入字符，直到输入换行符为止 Push(&S ,ch); /将输入的每个字符入栈将输入的每个字符入栈while (!StackEmp

12、ty(S) /依次退栈并输出退出的字符依次退栈并输出退出的字符 Pop(&S,&ch); putchar(ch);putchar(n);【举例举例2 2】十进制数值转换成二进制十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以数值。即用该十进制数值除以2，并保留其余数；重复，并保留其余数；重复此操作，直到该十进制数值为此操作，直到该十进制数值为0为止。最后将所有的余为止。最后将所有的余数反向输出就是所对应的二进制数值。数反向输出就是所对应的二进制数值。 比如：比如：(692)10 = (1010110100)2

13、，其展转相除的过，其展转相除的过程如图程如图3-4所示：所示：图图 3-4下面给出解决这个问题的完整算法。下面给出解决这个问题的完整算法。void Decimal _ Binary ( )STACK S; /定义栈结构定义栈结构SInitStack(&S); /初始化栈初始化栈Sscanf(“%d”,data); /输入十进制正整数输入十进制正整数while (data) Push(&S,data%2); /余数入栈余数入栈 data/=2; /被除数被除数data整除整除2，得到新的被除数，得到新的被除数while (!StackEmpty(S) /依次从栈中弹出每一个余数，并输出之依次从栈

14、中弹出每一个余数，并输出之 Pop(&S,&data); printf(“%d”,data);【举例举例3 3】检验表达式中的括号匹配情况检验表达式中的括号匹配情况 假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“”和“”和花括号“”和“”，并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。 算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配

15、情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 （1）当遇到某一个右括号时，栈已空，说明到目）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；前为止，右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。下面是解决这个问题的完整算法。 typedef char

16、StackEntry; int Check( ) STACK S; /定义栈结构定义栈结构S char ch;InitStack(&S); /初始化栈初始化栈Swhile (ch=getchar()!=n) /以字符序列的形式输入表达式以字符序列的形式输入表达式 switch (ch) case (ch=(|ch= |ch= ): Push(&S,ch);break; /遇左括号入栈遇左括号入栈 /在遇到右括号时，分别检测匹配情况在遇到右括号时，分别检测匹配情况case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch); if (

17、ch!= () return FALSE; break;case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch);if (ch!= ) return FALSE; break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch); if (ch!= ) return FALSE; break; default:break; if (StackEmpty(S) return TRUE; else return FALSE;3.2 3.2 队列队列3.2.1 3

18、.2.1 队列的定义队列的定义 队列特殊性在于限定插入在线性表的一端进行，队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如图删除在线性表的另外一端进行。如图3-5所示：所示：图图 3-5 插入端和删除端都是浮动的。通常我们将插入端称为插入端和删除端都是浮动的。通常我们将插入端称为队尾队尾，用一个，用一个“队尾指针队尾指针”指示；而删除端被称为指示；而删除端被称为队头队头，用一个用一个“队头指针队头指针”指示。指示。 结论：结论：先进先出先进先出（First In First Out），简称为），简称为FIFO线性表。线性表。 举例举例1：到医院看病，首先需要到挂号处挂号

19、，然后，：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。按号码顺序救诊。 举例举例2：乘坐公共汽车，应该在车站排队，车来后，：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。按顺序上车。 举例举例3：在：在Windows这类多任务的操作系统环境中，这类多任务的操作系统环境中，每个应用程序响应一系列的每个应用程序响应一系列的“消息消息”，像用户点击鼠标；，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息

20、，应用程序的处理过程就是不断该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。地从队列中读取消息，并依次给予响应。下面我们给出队列结构的基本操作：下面我们给出队列结构的基本操作：（1）初始化队列）初始化队列 InitQueue(Q) （2）入队）入队 EnQueue(Q,item) （3）出队）出队 DeQueue(Q,item) （4）获取队头元素内容）获取队头元素内容 GetFront(Q,item) （5）判断队列是否为空）判断队列是否为空 QueueEmpty(Q) 3.2.2 3.2.2 队列的顺序存储队列的顺序存储 队列的顺序存储结构如下图队列的顺

21、序存储结构如下图3-6所示：所示：图图 3-6 问题问题1：当队空时，队头和队尾指针都为：当队空时，队头和队尾指针都为-1，队列，队列将处于下图将处于下图3-7所示的状态：所示的状态：图图 3-7 此时若进行入队操作，就需要让队头和队尾指针此时若进行入队操作，就需要让队头和队尾指针都增都增1，再将新数据元素放入该位置。也就是说，这样，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。与非空队状态所需要执行的操作不完全一样。 解决方法：在算法中，需要对这两种情况加以区分，解决

22、方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图一个位置，如下图3-8所示。所示。图图 3-8 问题问题2：由于顺序存储结构的存储空间属于静态分：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。下元的情况。对于队列来说，这一点又有它的特殊性。下面我们讨论一下下图面我们讨论一下

23、下图3-9所示的队列。所示的队列。图图 3-9 “假溢出假溢出”现象。现象。 解决方法：将存储队列元素的一维数组首尾相接，解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。如图形成一个环状。如图3-10所示。我们将这种形式表示所示。我们将这种形式表示的队列称之为的队列称之为循环队列循环队列。a8a7a6a576543210rearfront图图 3-10 假设为队列开辟的数组单元数目为假设为队列开辟的数组单元数目为MAX_QUEUE，在，在C语言中，它的下标在语言中，它的下标在0MAX_QUEUE-1之间，之间，若增加队头或队尾指针，可以利用取模运算（一个整若增加队头或队尾指针，可以利

24、用取模运算（一个整数数值整除另一个整数数值的余数）实现。如下所示：数数值整除另一个整数数值的余数）实现。如下所示： front=(front+1)%MAX_QUEUE； rear=(rear+1)%MAX_QUEUE； 当当front或或rear为为MAXQUEUE-1时，上述两个公式时，上述两个公式计算的结果就为计算的结果就为0。这样，就使得指针自动由后面转到。这样，就使得指针自动由后面转到前面，形成循环的效果。前面，形成循环的效果。 队空和队满的标志问题：队空和队满的标志问题： 队列变为空，队头和队尾指针相等。队列变为空，队头和队尾指针相等。a7 a876543210rearfront76

25、543210rearfront(a)(b)图图 3-11队列变为满，队头和队尾指针也相等。队列变为满，队头和队尾指针也相等。rearfronta6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210rearfront(a)(b)图图 3-12 解决方法：一是为队列另设一个标志，用来区分解决方法：一是为队列另设一个标志，用来区分队列是队列是“空空”还是还是“满满”；二是当数组只剩下一个单；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头元时就认为队满，此时，队尾指针只差一步追上队头指针，即：指针，即：(rear+1)%MAX_QUEUE=fro

26、nt。 类型定义：类型定义： #define MAX_QUEUE 10 /队列的最大数据元素数目队列的最大数据元素数目 typedef struct queue /假设当数组只剩下一个单元时认为队满假设当数组只剩下一个单元时认为队满 QueueEntry itemMAX_QUEUE; /存放队列中数据元素的存储单元存放队列中数据元素的存储单元 int front,rear; /队头指针、队尾指针队头指针、队尾指针 QUEUE;各项基本操作算法。各项基本操作算法。（1）初始化队列）初始化队列Q void InitQueue(QUEUE *Q) Q-front=-1; Q-rear=-1;（2）入

27、队）入队 void EnQueue(QUEUE *Q,QueueEntry item) if (Q-rear+1)%MAX_QUEUE=Q-front) exit(OVERFLOW); else Q-rear=(Q-rear+1)%MAX_QUEUE; Q-itemQ-rear=item; （3）出队）出队 void DeQueue(QUEUE*Q,QueueEntry *item) if (QueueEmpty(*Q) exit(“Queue is empty.”); else Q-front=(Q-front+1)%MAX_QUEUE; *item=Q-itemQ-front; （4）获取

28、队头元素内容）获取队头元素内容 void GetFront(QUEUE Q,QueueEntry *item) if (QueueEmpty(Q) exit(“Queue is empty.”); else *item=Q.item(Q.front+1)%MAX_QUEUE;（5）判断队列）判断队列Q是否为空是否为空 int QueueEmpty(Queue Q) if (Q.front=Q.rear) return TRUE; else return FALSE;3.2.3 3.2.3 队列的链式存储队列的链式存储 在用链式存储结构表示队列时，需要设置队头指在用链式存储结构表示队列时，需要设

29、置队头指针和队尾指针，以便指示队头结点和队尾结点。针和队尾指针，以便指示队头结点和队尾结点。frontrear图图 3-13入队需要执行下面三条语句：入队需要执行下面三条语句：s-next=NULL; rear-next=s;rear=s;下面是在下面是在C语言中，实现队列链式存储结构的类型定义：语言中，实现队列链式存储结构的类型定义：type struct node /链式队列的结点结构链式队列的结点结构 QueueEntry Entry; /队列的数据元素类型队列的数据元素类型 struct node *next; /指向后继结点的指针指向后继结点的指针NODE;typedef struc

30、t queue /链式队列链式队列 NODE *front; /队头指针队头指针 NODE *rear; /队尾指针队尾指针QUEUE; 下面我们给出链式队列的基本操作算法。下面我们给出链式队列的基本操作算法。（1）初始化队列）初始化队列Q void InitQueue(QUEUE *Q) Q-front=(NODE*)malloc(sizeof(NODE); if (Q-front=NULL) exit(ERROR); Q-rear= Q-front;（2）入队）入队 void EnQueue(QUEUE *Q,QueueEntry item) s=(NODE*)malloc(sizeof(

31、NODE); if (!s) exit(ERROR); s-item=item; s-next=NULL; Q-rear-next=s; Q-rear=s; （3）出队）出队 void DeQueue(QUEUE *Q,QueueEntry *item) if (QueueEmpty(*Q) exit(ERROR); else *item=Q-front-next-item; s=Q-front-next; Q-front-next=s-next; free(s); （4）获取队头元素内容）获取队头元素内容 void GetFront(QUEUE Q,QueueEntry *item) if

32、(QueueEmpty(Q) exit(ERROR); else *item=Q-front-next-item;（5）判断队列）判断队列Q是否为空是否为空 int QueueEmpty(QUEUE Q) if (Q-front=Q-rear) return TRUE； else return FALSE; 4 4队列的应用举例队列的应用举例【举例举例1 1】汽车加油站。汽车加油站。 随着城市里汽车数量的急速增长，汽车加油站也随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干

33、条。每辆车口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加加油车道数加2个队列。个队列。【举例举例2 2】模拟打印机缓冲区。模拟打印机缓冲区。 在主机将数据输出到打印机时，会出现主机速度在主机将数据输出到打印机时，会出现主

34、机速度与打印机的打印速度不匹配的问题。这时主机就要停与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性

35、，又提高并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。就是一个队列结构。【举例举例3 3】CPU分时系统分时系统 在一个带有多个终端的计算机系统中，同时有多在一个带有多个终端的计算机系统中，同时有多个用户需要使用个用户需要使用CPU运行各自的应用程序，它们分别运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用通过各自的终端向操作系统提出使用CPU的请求，操的请求，操作系统通常按照每个请求在时间上的先后顺序，将它作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把们排成一个队列，每次把CPU分配给当前队首的请求分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将行完毕或用完规定的时间片后，操作系统再将CPU分分配给新的队首请求用户，这样即可以满足每个用户的配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使请求，又可以使CPU正常工作。正常工作。