数据结构C语言版(栈和队列)课件

1、数据结构C语言版(栈和队列) 本章主要介绍以下内容：本章主要介绍以下内容：l 栈的概念、存储结构及其基本操作栈的概念、存储结构及其基本操作l 队列的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作l 栈与队列的应用举例栈与队列的应用举例数据结构C语言版(栈和队列)3.1 栈栈3.2 队列队列数据结构C语言版(栈和队列) 3.1.1 3.1.1 栈的定义栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如和删除数据元素的操作只能在线性表的一端进行。如下所示：下所示： 进行插入和删除的一端是浮动端，通

2、常被称为进行插入和删除的一端是浮动端，通常被称为栈栈顶顶，并用一个，并用一个“栈顶指针栈顶指针”指示；而另一端是固定端，指示；而另一端是固定端，通常被称为通常被称为栈底栈底。我们经常将栈用下图。我们经常将栈用下图3-1的形式描述：的形式描述：a1, a2, a3, ., an 插入和删除端插入和删除端数据结构C语言版(栈和队列)an.a2a1栈顶 top图图 3-1数据结构C语言版(栈和队列) 结论：结论：后进先出后进先出（Last In First Out），简称为），简称为LIFO线性表。线性表。 举例举例1：家里吃饭的碗，通常在洗干净后一个一个：家里吃饭的碗，通常在洗干净后一个一个地落在

3、一起存放，在使用时，若一个一个地拿，一定地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只最先拿走最上面的那只碗，而最后拿出最下面的那只碗。碗。 举例举例2：在建筑工地上，使用的砖块从底往上一层：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。一层地码放，在使用时，将从最上面一层一层地拿取。 下面我们先给出栈结构的基本操作：下面我们先给出栈结构的基本操作： （1）初始化栈）初始化栈 InitStack(S) （2）入栈）入栈 Push(S,item) （3）出栈）出栈 Pop(S,item) （4）获取栈顶元素内容）

4、获取栈顶元素内容 GetTop(S,item) （5）判断栈是否为空）判断栈是否为空 StackEmpty(S) 数据结构C语言版(栈和队列) 3.1.2 3.1.2 栈的顺序存储栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。存放栈中的每个数据元素，并用起始端作为栈底。 类型定义如下所示：类型定义如下所示： #define MAX_STACK 10 /栈的最大数据元素数目栈的最大数据元素数目 typedef struct stack StackEntry itemMAX_STACK; /存放栈中数据

5、元素的存储单元存放栈中数据元素的存储单元 int top; /栈顶指针栈顶指针 STACK;数据结构C语言版(栈和队列)基本操作算法：基本操作算法：1. 初始化栈初始化栈S void InItStack(STACK *S) s-top=-1; 2. 入栈入栈 void Push(STACK *S,StackEntry item) if (S-top=MAX_STACK-1) exit(“Stack is full”); else S-item+S-top=item;数据结构C语言版(栈和队列)图图 3-2MAX_STACK-1.10top= -1数据结构C语言版(栈和队列)3. 出栈出栈 vo

6、id 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 (StackEmpty(S) exit(“Stack is empty”); else *item=S.itemS.top;数据结构C语言版(栈和队列) 5. 判断栈判断栈S是否为空是否为空 int StackEmpty(STACK S) if (S.top=-1) return

7、 TRUE; else FALSE; 结论：由于栈的插入和删除操作具有它的特殊性，结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。就没有摆脱。数据结构C语言版(栈和队列) 3.1.3 3.1.3 栈的链式存储栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链的数目，就应该考虑使用链式存储结构。人们将用链式存储

8、结构表示的栈称作式存储结构表示的栈称作“链栈链栈”。链栈通常用一个。链栈通常用一个无头结点的单链表表示。如图无头结点的单链表表示。如图3-3所示。所示。 由于栈的插入删除操作只能在一端进行，而对于由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。将单链表的头指针作为栈顶指针。数据结构C语言版(栈和队列) top图 3-3数据结构C语言版(栈和队列)栈的链式存储结构在栈的链式存储结构在C语言中

9、可用下列类型定义实现：语言中可用下列类型定义实现：type struct node /链栈的结点结构链栈的结点结构 StackEntry item; /栈的数据元素类型栈的数据元素类型 struct node *next; /指向后继结点的指针指向后继结点的指针NODE; typedef struct stack NODE *top;STACK; 数据结构C语言版(栈和队列)下面我们将给出链栈各项基本操作的算法。下面我们将给出链栈各项基本操作的算法。1. 初始化栈初始化栈S void InitStack(STACK *S) S-top=NULL;数据结构C语言版(栈和队列)2. 入栈入栈 vo

10、id 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; 数据结构C语言版(栈和队列)3. 出栈出栈void Pop(STACK*S, StackEntry *item)if (StackEmpty(*S) exit(“Stack is empty”);else *item=S-top-item; p=S-top; S-top=p-next; free(p); 数据结构C语言版(栈和队列)4. 获

11、取栈顶元素内容获取栈顶元素内容 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;数据结构C语言版(栈和队列) 3.1.4 3.1.4 栈的应用举例栈的应用举例 【举例举例1 1】将从键盘输入的字符序列逆置输出将从键盘输入的字符序列逆置输出 比如，从键盘上输入：比如，从键盘上输入：t

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

13、while (!StackEmpty(S) /依次退栈并输出退出的字符依次退栈并输出退出的字符 Pop(&S,&ch); putchar(ch);putchar(n);数据结构C语言版(栈和队列)【举例举例2 2】十进制数值转换成二进制十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以数值。即用该十进制数值除以2，并保留其余数；重复，并保留其余数；重复此操作，直到该十进制数值为此操作，直到该十进制数值为0为止。最后将所有的余为止。最后将所有的余数反向输出就是所对应的二进制数值。数反向输出就是所对

14、应的二进制数值。 比如：比如：(692)10 = (1010110100)2，其展转相除的过程，其展转相除的过程如图如图3-4所示：所示：数据结构C语言版(栈和队列)图图 3-4除数 被除数余数2 6922 346 02 173 02 86 12 43 02 21 12 10 12 5 02 2 12 1 00 1数据结构C语言版(栈和队列)下面给出解决这个问题的完整算法。下面给出解决这个问题的完整算法。void Decimal _ Binary ( )STACK S; /定义栈结构定义栈结构SInitStack(&S); /初始化栈初始化栈Sscanf(“%d”,data); /输入

15、十进制正整数输入十进制正整数数据结构C语言版(栈和队列)while (data) Push(&S,data%2); /余数入栈余数入栈 data/=2; /被除数被除数data整除以整除以2，得到新的被除数，得到新的被除数while (!StackEmpty(S) /依次从栈中弹出每一个余数，并输出之依次从栈中弹出每一个余数，并输出之 Pop(&S,&data); printf(“%d”,data);数据结构C语言版(栈和队列)【举例举例3 3】检验表达式中的括号匹配情况检验表达式中的括号匹配情况 假设在一个算术表达式中，可以包含三种括号：假设在一个算术表达式中，可以包

16、含三种括号：圆括号圆括号“（”和和“）”，方括号，方括号“”和和“”和花括号和花括号“”和和“”，并且这三种括号可以按任意的次序嵌套，并且这三种括号可以按任意的次序嵌套使用。比如，使用。比如，.(.).。现在需要设。现在需要设计一个算法，用来检验在输入的算术表达式中所使用计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。括号的合法性。 算术表达式中各种括号的使用规则为：出现左括算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个可以嵌套，但不能出现交叉情况。

17、我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结遇到以下几种情况之一，就可以得出括号不匹配的结论。论。数据结构C语言版(栈和队列) （1）当遇到某一个右括号时，栈已空，说明到目）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；前为止，右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；型不同，说明出现

18、了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。下面是解决这个问题的完整算法。 typedef char StackEntry; int Check( ) STACK S; /定义栈结构定义栈结构S char ch;数据结构C语言版(栈和队列)InitStack(&S); /初始化栈初始化栈Swhile (ch=getchar()!=n) /以字符序列的形式输入表达式以字符序列的形式输入表达式 switch (ch) c a s e (

19、c h = = ( | | c h = = | | c h = = ) : Push(&S,ch);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);数据结构C语言版(栈和队列)if (c

20、h!= ) 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;数据结构C语言版(栈和队列) 3.2.1 3.2.1 队列的定义队列的定义 队列特殊性在于限定插入在线性表的一端进行，队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如图删除在线性表的另外一

21、端进行。如图3-5所示：所示：a1a2a3.ai.an -1an插 入 端删 除 端图图 3-5数据结构C语言版(栈和队列) 插入端和删除端都是浮动的。通常我们将插入端插入端和删除端都是浮动的。通常我们将插入端称为称为队尾队尾，用一个，用一个“队尾指针队尾指针”指示；而删除端被称指示；而删除端被称为为队头队头，用一个，用一个“队头指针队头指针”指示。指示。 结论：结论：先进先出先进先出（First In First Out），简称为），简称为FIFO线性表。线性表。 举例举例1：到医院看病，首先需要到挂号处挂号，然：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。后，按号码顺序救诊。

22、举例举例2：乘坐公共汽车，应该在车站排队，车来后，：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。按顺序上车。 举例举例3：在：在Windows这类多任务的操作系统环境中，这类多任务的操作系统环境中，每个应用程序响应一系列的每个应用程序响应一系列的“消息消息”，像用户点击鼠，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息

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

24、所示：012n-2n-1a1a2a3.an-1an frontrear图图 3-6数据结构C语言版(栈和队列) 问题问题1：当队空时，队头和队尾指针都为：当队空时，队头和队尾指针都为-1，队列，队列将处于下图将处于下图3-7所示的状态：所示的状态：012.n-2n-1front=-1rear=-1图图 3-7数据结构C语言版(栈和队列) 此时若进行入队操作，就需要让队头和队尾指针此时若进行入队操作，就需要让队头和队尾指针都增都增1，再将新数据元素放入该位置。也就是说，这样，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队设置队头、队尾指针位置，在进行入队操

25、作时，空队与非空队状态所需要执行的操作不完全一样。与非空队状态所需要执行的操作不完全一样。 解决方法：在算法中，需要对这两种情况加以区分，解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图一个位置，如下图3-8所示。所示。数据结构C语言版(栈和队列)012n-2n-1a1a2a3.an-1anfrontrear图图 3-8数据结构C语言版(栈和队列) 问题问题2：由于顺序存储结构的存储空间属于静态分：

26、由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。单元的情况。对于队列来说，这一点又有它的特殊性。下面我们讨论一下下图下面我们讨论一下下图3-10所示的队列。所示的队列。01234567a5a6a7a8frontrear图图 3-10数据结构C语言版(栈和队列) “假溢出假溢出”现象。现象。 解决方法：将存储队列元素的一维数组首尾相接，解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。如图形成一个环状。如图3-11所示。我们将这种形式表示所示。我们将这种形式表示

27、的队列称之为的队列称之为循环队列循环队列。数据结构C语言版(栈和队列)a8a7a6a576543210rearfront图图 3-11数据结构C语言版(栈和队列) 假设为队列开辟的数组单元数目为假设为队列开辟的数组单元数目为MAX_QUEUE，在在C语言中，它的下标在语言中，它的下标在0MAX_QUEUE-1之间，若之间，若增加队头或队尾指针，可以利用取模运算（一个整数增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：数值整除以另一个整数数值的余数）实现。如下所示： front=(front+1)%MAX_QUEUE； rear=(rear+1)%M

28、AX_QUEUE； 当当front或或rear为为MAXQUEUE-1时，上述两个公式时，上述两个公式计算的结果就为计算的结果就为0。这样，就使得指针自动由后面转到。这样，就使得指针自动由后面转到前面，形成循环的效果。前面，形成循环的效果。 队空和队满的标志问题：队空和队满的标志问题： 队列变为空，队头和队尾指针相等。队列变为空，队头和队尾指针相等。数据结构C语言版(栈和队列)a7 a876543210rearfront76543210rearfront(a)(b)图图 3-12队列变为满，队头和队尾指针也相等。队列变为满，队头和队尾指针也相等。数据结构C语言版(栈和队列)rearfronta

29、6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210rearfront(a)(b)图图 3-13数据结构C语言版(栈和队列) 解决方法：一是为队列另设一个标志，用来区分解决方法：一是为队列另设一个标志，用来区分队列是队列是“空空”还是还是“满满”；二是当数组只剩下一个单；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头元时就认为队满，此时，队尾指针只差一步追上队头指针，即：指针，即：(rear+1)%MAX_QUEUE=front。 类型定义：类型定义： #define MAX_QUEUE 10 /队列的最大数据元素数目队列的最大数据元素数

30、目 typedef struct queue /假设当数组只剩下一个单元时认为队满假设当数组只剩下一个单元时认为队满 QueueEntry itemMAX_QUEUE; /存放队列中数据元素的存储单元存放队列中数据元素的存储单元 int front,rear; /队头指针、队尾指针队头指针、队尾指针 QUEUE;数据结构C语言版(栈和队列)各项基本操作算法。各项基本操作算法。（1）初始化队列）初始化队列Q void InitQueue(QUEUE *Q) Q-front=-1; Q-rear=-1;数据结构C语言版(栈和队列)（2）入队）入队 void EnQueue(QUEUE *Q,Que

31、ueEntry item) if (Q-rear+1)%MAX_QUEUE=Q-front) exit(OVERFLOW); else Q-rear=(Q-rear+1)%MAX_QUEUE; Q-itemQ-rear=item; 数据结构C语言版(栈和队列)（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; 数据结构C语言版(栈和队列)（4）获取队头

32、元素内容）获取队头元素内容 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;数据结构C语言版(栈和队列) 3.2.3 3.2.3 队列的链式存储队列的链式存储 在用链式存储结构表示队列时，需要设置队头指在用链式

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

34、指向后继结点的指针NODE;typedef struct queue /链式队列链式队列 NODE *front; /队头指针队头指针 NODE *rear; /队尾指针队尾指针QUEUE; 数据结构C语言版(栈和队列)下面我们给出链式队列的基本操作算法。下面我们给出链式队列的基本操作算法。（1）初始化队列）初始化队列Q void InitQueue(QUEUE *Q) Q-front=(NODE*)malloc(sizeof(NODE); if (Q-front=NULL) exit(ERROR); Q-rear= Q-front;数据结构C语言版(栈和队列)（2）入队）入队 void En

35、Queue(QUEUE *Q,QueueEntry item) s=(NODE*)malloc(sizeof(NODE); if (!s) exit(ERROR); s-item=item; s-next=NULL; Q-rear-next=s; Q-rear=s; 数据结构C语言版(栈和队列)（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

36、(s); 数据结构C语言版(栈和队列)（4）获取队头元素内容）获取队头元素内容 void GetFront(QUEUE Q,QueueEntry *item) if (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;数据结构C语言版(栈和队列) 4 4队列的应用举例队列的应用举例【举例举例1 1】汽车加油站。汽车加油站。 随着城市里汽车数量的急速增长，汽车加油站也随着城市里汽车数量的