《数据结构C语言版(栈和队列).ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版(栈和队列).ppt（54页珍藏版）》请在三一办公上搜索。
1、第3章 栈和队列,本章主要介绍以下内容：栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用举例,退出,3.1 栈3.2 队列,3.1 栈,3.1.1 栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：,a1,a2,a3,.,an 插入和删除端,图 3-1,结论：后进先出（Last In First Out），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个
2、一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：（1）初始化栈 InitStack(S)（2）入栈 Push(S,item)（3）出栈 Pop(S,item)（4）获取栈顶元素内容 GetTop(S,item)（5）判断栈是否为空 StackEmpty(S),3.1.2 栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#define MAX_STACK
3、 10/栈的最大数据元素数目 typedef struct stack StackEntry itemMAX_STACK;/存放栈中数据元素的存储单元 int top;/栈顶指针 STACK;,基本操作算法：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;,图 3-2,3.出栈 void Pop(STACK*S,StackEntry*item)if(Sta
4、ckEmpty(*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;,5.判断栈S是否为空 int StackEmpty(STACK S)if(S.top=-1)return TRUE;else FALSE;结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的
5、弱点仍就没有摆脱。,3.1.3 栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,图 3-3,栈的链式存储结构在C语言中可用下列类型定义实现：type struct node/链栈的结点结构 StackEntry item;/栈的数据元素类型 struct node*next;/指向后继结点的指
6、针NODE;typedef struct stack NODE*top;STACK;,下面我们将给出链栈各项基本操作的算法。1.初始化栈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 i
7、s empty”);else*item=S-top-item;p=S-top;S-top=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 栈的应用举例【举例1】将从键盘输入的字符序列逆置输出 比如，从键盘上输入：tset a si sihT；算法将
8、输出：This is a test 下面我们给出解决这个问题的完整算法。typedef char StackEntry;void ReverseRead()STACK S;/定义一个栈结构S char ch;InitStack(/初始化栈,while(ch=getchar()!=n)/从键盘输入字符，直到输入换行符为止 Push(,【举例2】十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10=(1010110100)2，其展转相除
9、的过程如图3-4所示：,图 3-4,下面给出解决这个问题的完整算法。void Decimal _ Binary()STACK S;/定义栈结构SInitStack(/输入十进制正整数,while(data)Push(,【举例3】检验表达式中的括号匹配情况 假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“”和“”和花括号“”和“”，并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况
10、。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。,（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。下面是解决这个问题的完整算法。typedef char StackEntry;int Check()STACK S;/定义栈结构S char ch;,InitStack(,if(ch!=)return FALSE;b
11、reak;case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(,3.2 队列,3.2.1 队列的定义 队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如图3-5所示：,图 3-5,插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。结论：先进先出（First In First Out），简称为FIFO线性表。举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。举例3：在Windows这类多任务
12、的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。,下面我们给出队列结构的基本操作：（1）初始化队列 InitQueue(Q)（2）入队 EnQueue(Q,item)（3）出队 DeQueue(Q,item)（4）获取队头元素内容 GetFront(Q,item)（5）判断队列是否为空 QueueEmpty(Q),3.2.2 队列的顺序存储 队列的顺序存储结构如下图3-6所示：,图 3-6,问题
13、1：当队空时，队头和队尾指针都为-1，队列将处于下图3-7所示的状态：,图 3-7,此时若进行入队操作，就需要让队头和队尾指针都增1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。解决方法：在算法中，需要对这两种情况加以区分，这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图3-8所示。,图 3-8,问题2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。下面我们讨论一下下图3
14、-10所示的队列。,图 3-10,“假溢出”现象。解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。如图3-11所示。我们将这种形式表示的队列称之为循环队列。,图 3-11,假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循
15、环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等。,(a),(b),图 3-12,队列变为满，队头和队尾指针也相等。,rear,front,a6,a5,a4,a3,a1,a2,7,6,5,4,3,2,1,0,a6,a5,a4,a3,a1,a2,a8,a7,7,6,5,4,3,2,1,0,rear,front,(a),(b),图 3-13,解决方法：一是为队列另设一个标志，用来区分队列是“空”还是“满”；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%MAX_QUEUE=front。类型定义：#define MAX_QUEUE 10/
16、队列的最大数据元素数目 typedef struct queue/假设当数组只剩下一个单元时认为队满 QueueEntry itemMAX_QUEUE;/存放队列中数据元素的存储单元 int front,rear;/队头指针、队尾指针 QUEUE;,各项基本操作算法。（1）初始化队列Q void InitQueue(QUEUE*Q)Q-front=-1;Q-rear=-1;,（2）入队 void EnQueue(QUEUE*Q,QueueEntry item)if(Q-rear+1)%MAX_QUEUE=Q-front)exit(OVERFLOW);else Q-rear=(Q-rear+1)
17、%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）获取队头元素内容 void GetFront(QUEUE Q,QueueEntry*item)if(QueueEmpty(Q)exit(“Queue is empty.”);else*item=Q.item(Q.front+1)%MAX_QUEUE;（5
18、）判断队列Q是否为空 int QueueEmpty(Queue Q)if(Q.front=Q.rear)return TRUE;else return FALSE;,3.2.3 队列的链式存储 在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。,图 3-14,入队需要执行下面三条语句：s-next=NULL;rear-next=s;rear=s;下面是在C语言中，实现队列链式存储结构的类型定义：type struct node/链式队列的结点结构 QueueEntry Entry;/队列的数据元素类型 struct node*next;/指向后继结点的指针NO
19、DE;typedef struct 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(NODE);if(!s)exit(ERROR);s-item=item;
20、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(QueueEmpty(Q)exit(ERROR);else*item=Q-front-next-item;（5）判断队列Q是否为空 i
21、nt QueueEmpty(QUEUE Q)if(Q-front=Q-rear)return TRUE；else return FALSE;,4队列的应用举例【举例1】汽车加油站。随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。,【举例2】模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度与打印机
22、的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。,【举例3】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。,
