数据结构教程 栈和队列

1、第3章 栈和队列本章主要介绍以下内容1栈的概念、存储结构、基本操作、应用举例2队列的概念、存储结构、基本操作、应用举例课时分配：第1节四个学时，第2节两个学时，上机两个学时重点、难点：栈的存储结构及其基本操作、队列存储结构及其基本操作第一节 栈1栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：结论：后进先出（Last In First Out），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从

2、底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的基本操作：（1）初始化栈 InitStack(S) （2）入栈 Push(S,elem) （3）出栈 Pop(S,elem) （4）获取栈顶元素内容 GetTop(S,elem) （5）判断栈是否为空 StackEmpty(S) 2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#define MAX_STACK 10 /栈的最大数据元素数目typedef struct stackElemtype elemMAX_STACK; /存放栈中数据元素的

3、存储单元int top; /栈顶指针STACK;基本操作算法（1）初始化栈void InItStack(STACK *S) s->top=-1; （2）入栈 void Push(STACK *S,Elemtype elem)if (S->top=MAX_STACK-1) exit("Stack is full");else S->elem+S->top=elem;（3）出栈 void Pop(STACK *S,Elemtype *elem)if (StackEmpty(*S) exit("Stack is empty");else

4、 *elem=S->elemS->top-;（4）获取栈顶元素内容 void GetTop(STACK S,Elemtype *elem)if (StackEmpty(S) exit("Stack is empty");else *elem=S.elemS.top;（5）判断栈S是否为空int StackEmpty(STACK S)if (S.top=-1) return TRUE;else FALSE;结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。3栈的链式存

5、储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作"链栈"。链栈通常用一个无头结点的单链表表示。由于栈的操作是线性表操作的特例，则链栈的操作易于实现，主要由学生完成，下述内容仅供学生参考，不作详细讨论。链栈各项基本操作的算法（1）初始化栈S void InitStack(STACK *S)S->top=NULL;（2）入栈 void Push(STACK *S,Elemtype elem)p=(LINKLIST*)malloc(sizeof(LINKLIST);if (!p) exit(OVERFLOW)

6、;else p->elem=elem;p->next=S->top;S->top=p;（3）出栈void Pop(STACK*S, Elemtype *elem)if (StackEmpty(*S) exit("Stack is empty");else *elem=S->top->elem;p=S->top;S->top=p->next; free(p);（4）获取栈顶元素内容void GetTop(STACK S,Elemtype *elem)if (StackEmpty(S) exit("Stack is

7、 empty");else *elem=S.top->elem;（5）判断栈S是否空 int StackEmpty(STACK S)if (S.top=NULL) return TRUE;return else FALSE;4栈的应用举例【举例1】将从键盘输入的字符序列逆置输出比如，从键盘上输入：tset a si sihT；算法将输出：This is a test下面我们给出解决这个问题的完整算法。typedef char Elemtype;void ReverseRead( ) STACK S; /定义一个栈结构Schar ch; InitStack(&S); /初

8、始化栈while (ch=getchar()!='n') /从键盘输入字符，直到输入换行符为止Push(&S ,ch); /将输入的每个字符入栈while (!StackEmpty(S) /依次退栈并输出退出的字符Pop(&S,&ch);putchar(ch);putchar('n');【举例2】十进制数值转换成二进制使用连续除商法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10 = (1010110100)2

9、，其相除过程如图所示：下面给出解决这个问题的完整算法。void Decimal _ Binary ( )STACK S; /定义栈结构S InitStack(&S); /初始化栈Sscanf("%d",data); /输入十进制正整数while (data) Push(&S,data%2); /余数入栈data/=2; /被除数data整除以2，得到新的被除数while (!StackEmpty(S) /依次从栈中弹出每一个余数，并输出之Pop(&S,&data); printf("%d",data);【举例3】检验表达式

10、中的括号匹配情况（时间不够，则该例作为选学内容）假设在一个算术表达式中，可以包含三种括号：圆括号"（"和"）"，方括号""和""和花括号""和""，并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配

11、情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。下面是解决这个问题的完整算法。typedef char Elemtype;int Check( )STACK S; /定义栈结构Schar ch; InitStack(&S); /初始化栈Swhile (ch=getchar()!='n') /以字符序列的形式输入表达式switch

12、 (ch) case (ch='('|ch= ''|ch= ''): 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,&

13、amp;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;第二节 队列1队列的定义插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个"队尾指针"指示；而删除端被称为队头

14、，用一个"队头指针"指示。结论：先进先出（First In First Out），简称为FIFO线性表。举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。举例3：在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的"消息"，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。下面我们给出队列结构的基本操作（1）初始化队列 I

15、nitQueue(Q) （2）入队 EnQueue(Q,elem) （3）出队 DeQueue(Q,elem) （4）获取队头元素内容 GetFront(Q,elem) （5）判断队列是否为空 QueueEmpty(Q)假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样

16、，就使得指针自动由后面转到前面，形成循环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等。解决方法：一是为队列另设一个标志，用来区分队列是"空"还是"满"；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%MAX_QUEUE=front。类型定义：#define MAX_QUEUE 10 /队列的最大数据元素数目typedef struct queue /假设当数组只剩下一个单元时认为队满Elemtype elemMAX_QUEUE; /存放队列数据元素的存储单元int front,rear; /

17、队头指针、队尾指针 QUEUE;各项基本操作算法（1）初始化队列Q void InitQueue(QUEUE *Q)Q->front=-1;Q->rear=-1;（2）入队 void EnQueue(QUEUE *Q,Elemtype elem)if (Q->rear+1)%MAX_QUEUE=Q->front) exit(OVERFLOW);else Q->rear=(Q->reasr+1)%MAX_QUEUE;Q->elemQ->rear=elem; （3）出队 void DeQueue(QUEUE*Q,Elemtype *elem)if (

18、QueueEmpty(*Q) exit("Queue is empty.");else Q->front=(Q->front+1)%MAX_QUEUE;*elem=Q->elemQ->front;（4）获取队头元素内容 void GetFront(QUEUE Q,Elemtype *elem) if (QueueEmpty(Q) exit("Queue is empty.");else *elem=Q.elem(Q.front+1)%MAX_QUEUE;（5）判断队列Q是否为空 int QueueEmpty(Queue Q)if

19、(Q.front=Q.rear) return TRUE;else return FALSE; 入队需要执行下面三条语句：s->next=NULL; rear->next=s;rear=s;下面是在C语言中，实现队列链式存储结构的类型定义：type struct linklist /链式队列的结点结构Elemtype Entry; /队列的数据元素类型struct linklist *next; /指向后继结点的指针 LINKLIST;typedef struct queue /链式队列LINKLIST *front; /队头指针LINKLIST *rear; /队尾指针 QUEU

20、E; 下面我们给出链式队列的基本操作算法（1）初始化队列Q void InitQueue(QUEUE *Q)Q->front=(LINKLIST*)malloc(sizeof(LINKLIST);if (Q->front=NULL) exit(ERROR);Q->rear= Q->front;（2）入队 void EnQueue(QUEUE *Q,Elemtype elem)s=(LINKLIST*)malloc(sizeof(LINKLIST);if (!s) exit(ERROR);s->elem=elem;s->next=NULL;Q->rear

21、->next=s;Q->rear=s;（3）出队 void DeQueue(QUEUE *Q,Elemtype *elem)if (QueueEmpty(*Q) exit(ERROR);else *elem=Q->front->next->elem; s=Q->front->next;Q->front->next=s->next;free(s);（4）获取队头元素内容 void GetFront(QUEUE Q,Elemtype *elem) if (QueueEmpty(Q) exit(ERROR);else *elem=Q->front->next->elem;（5）判断队列Q是否为空 int QueueEmpty(QUEUE Q)if (Q->front=Q->rear) r