本章主要内容1、栈的概念、存储结构及其基本操作及其应用;2、.

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

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

3、类定义 */int elementsMAXSIZE;int top; Stack;基本操作算法：(1)初始化栈void InitStack( Stack *S ) /* 初始化栈，将栈置空 */ S-top = 0;(2) 入栈void Push(Stack *S, int x) /* 将元素 x 压入到栈 S 中 */if( !IsFull(*S) ) /* 如果尚未达到栈满，则将 x 压入栈 S 中，并使栈顶指针增 1 */ S-elementsS-top = x;S-top+;else printf( 栈上溢！ n );(3) 出栈int Pop( Stack *S ) /* 将栈 S

4、中的栈顶元素出栈 */if( !IsEmpty( *S ) ) /* 如果栈非空，则返回栈顶元素，并使栈顶指针减 1 */ S-top-;return S-elementsS-top;elseprintf( 栈下溢！ n ); return ERROR;(4) 获取栈顶元素内容 int GetTop( Stack S ) /* 获取栈顶元素，但不改变栈顶指针 */ if( !IsEmpty( S ) )return S.elementsS.top-1; elseprintf( 栈空！ n ); return ERROR;(5) 判断栈 S 是否为空 bool IsEmpty( Stack S)

5、 /* 判断栈是否为空。如果栈空，返回 true ，否则返回 false */if( S.top = 0 ) return true; else return false;结论： 由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元 素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。人们将用3.1.3 栈的链式存储及其基本运算的实现 若是栈中元素的数目变化范围较大或不清楚栈元素的数目， 就应该考虑使用链式存储结构。链式存储结构表示的栈称作 链栈 。链栈通常用一个无头结点的单链表表示。如图示：bottom结点类型定义：t ypedef struct nod

6、e /* 栈类定义 */int data;struct node *next; LinkStack;(1) 初始化void InitLinkStack( LinkStack *top ) /* 初始化栈，将栈置空 */ *top = NULL;2) 判断是否为空bool IsEmpty( LinkStack *top) /* 判断栈是否为空。如果栈空，返回true ，否则返回 false */if( top = NULL ) return true;else return false;3) 进栈void Push(LinkStack *top, int x) /* 将元素 x 压入到栈 S 中

7、，先申请结点再将其入栈 */LinkStack *S;S = (LinkStack *)malloc( sizeof(LinkStack) );S-data = x;S-next = *top;*top = S;4) 出栈int Pop( LinkStack *top ) /* 将栈 S 中的栈顶元素出栈 */LinkStack *S;int data;if( !IsEmpty( *top ) ) /* 如果栈非空，则返回栈顶元素，并使栈顶指针减1 */S = *top;*top = (*top)-next;data = S-data;free( S );return data;elsepri

8、ntf( 栈下溢！ n );return ERROR;(5) 取栈顶元素int GetTop( LinkStack *top ) /* 获取栈顶元素，但不改变栈顶指针 */if( !IsEmpty( top ) )return top-data;elseprintf( 栈空！ n );return ERROR;(6) 清空void EmptyLinkStack( LinkStack *top ) /* 清空堆栈 S ，使其栈顶指针为 0 */LinkStack *S;while( *top != NULL )S = (*top)-next;free( *top );*top = S;3.1.4

9、 栈的应用举例例 3-3: 将从键盘输入的字符序列逆置输出比如，从键盘上输入： tset a si sihT ；算法将输出： This is a test 下面我们给出解决这个问题的完整算法。typedef char Elemtype;void ReverseRead( )Stack S; / 定义一个栈结构 Schar ch;InitStack(&S); /初始化栈while (ch=getchar()!=n) / 从键盘输入字符，直到输入换行符为止Push(&S ,ch); / 将输入的每个字符入栈while (!StackEmpty(S) / 依次退栈并输出退出的字符Pop(&S,&ch

10、);putchar(ch);putchar(n);例 3 4： 十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数； 重复此操作， 直到该十进制数值为 0 为止。 最后将所有的余数反向输出就是所对应的二进制数值。 比如： (692)10 = (1010110100)2 ，其展转相除的过程如图所示：下面给出解决这个问题的完整算法。void Decimal _ Binary ( )STACK S; / 定义栈结构 SInitStack(&S); / 初始化栈 S scanf(%d,data); / 输入十进制正整数 while (data)

11、Push(&S,data%2); / 余数入栈data/=2; / 被除数 data 整除以 2 ，得到新的被除数while (!StackEmpty(S) /依次从栈中弹出每一个余数，并输出之Pop(&S,&data); printf(%d,data); 例 3 5： 检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：圆括号 (和 ) ，方括号 和 和花括号 和 ，并且这三种括号可以按任意的次序嵌套使用。 比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括

12、号之间可以 嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中 弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。(1) 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；(2) 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；(3) 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。typedef char Elemtype;int Check( )STACK S; / 定义栈结构 Schar ch;InitStack(&

13、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 (ch!= () return FALSE; break;case (ch= ): if (StackEmpty(S) retrun FALSE;else Pop(&S,&ch);if (ch!= ) return

14、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.1 队列的定义插入端和删除端都是浮动的。 通常我们将插入端称为队尾， 用一个 队尾指针 指示；而删除端被称为队头，用一个 队头指针 指示。结论： 先进先出( First In First Out)，简称为 FIFO 线性表。例 3-6 ： 到医院

15、看病，首先需要到挂号处挂号，然后，按号码顺序救诊。例 3-7 ： 乘坐公共汽车，应该在车站排队，车来后，按顺序上车。例 3-8 ：在 Windows这类多任务的操作系统环境中，每个应用程序响应一系列的 消息 ，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放 发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。 下面我们给出队列结构的基本操作：( 1 )初始化队列 InitQueue(Q)( 2 )入队 EnQueue(Q,elem)( 3 )出队 DeQueue(Q,elem)( 4 )获取队头

16、元素内容 GetFront(Q,elem)( 5 )判断队列是否为空 QueueEmpty(Q)3.2.2 队列的顺序存储结构及其基本运算的实现队列的顺序存储结构如下图所示：012n-2n-1a1a2a3an-1an问题 1：当队列空时，对头和队尾指针都为1，队列将变成下图所示状态：012n-2n-1问题 2：假溢出，即，在添加数据时，可能出现没有剩余空间而实际队列又不满的状况。 如：01234567a5a6a7a8front rear解决办法：将存储队列元素的一维数组首尾相接形成一个环状，即循环队列，如下图：front4假设为队列开辟的数组单元数目为 MAX_QUEU，E在 C语言中，它的下

17、标在 0MAX_QUEUE-之1 间，若增加队 头或队尾指针，可以利用取模运算(一个整数数值整除以另一个整数数值的余数)实现。如下所示： front=(front+1)%MAX_QUEUE ； rear=(rear+1)%MAX_QUEUE ；当 front 或 rear 为 MAXQUEUE-时1 ，上述两个公式计算的结果就为 0 。这样，就使得指针自动由后面转到 前面，形成循环的效果。队空和队满的标志问题： 队列变为空，队头和队尾指针相等。解决方法： 一是为队列另设一个标志，用来区分队列是 为队满，此时，队尾指针只差一步追上队头指针，即： 类型定义：#define MAX_QUEUE 10

18、 / 队列的最大数据元素数目 typedef struct queue /空 还是满 ；二是当数组只剩下一个单元时就认 (rear+1)%MAX_QUEUE=front。Elemtype elemMAX_QUEUE; / int front,rear; /队头指针、队尾指针假设当数组只剩下一个单元时认为队满存放队列中数据元素的存储单元QUEUE; 各项基本操作算法。 (1)初始化队列 Q void InitQueue(QUEUE *Q) Q-front=-1;Q-rear=-1;(2) 入队void EnQueue(QUEUE *Q,Elemtype elem)if (Q-rear+1)%MA

19、X_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 (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(Q

20、ueue is empty.);else *elem=Q.elem(Q.front+1)%MAX_QUEUE; (5) 判断队列 Q是否为空int QueueEmpty(Queue Q)if (Q.front=Q.rear) return TRUE;else return FALSE;3.2.3 队列的链式存储结构及其基本运算的实现在用链式结构存储队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点链式存储的队列的一般形式 结点结构定义如下： typedef struct node /* 队列结点类型定义 */int data; struct node *next; LinkQueu

21、e;typedef struct /* 队列头结点类型定义 */LinkQueue *front; /*队列的队首指针 */LinkQueue *rear; /*队列的队尾指针 */ Queue;基本运算：(1 ) 初始化void InitQueue( Queue *Q ) /* 初始化队列，生成一个带哨兵的空队列 */Q-front = (LinkQueue *)malloc( sizeof(LinkQueue) );Q-front-next = NULL;Q-rear = Q-front;(2 ) 判空bool IsEmpty( Queue Q) /* 判断队列是否为空。如果队列为空，返回

22、 true ，否则返回 false */if( Q.front = Q.rear ) return true;else return false;(3 ) 进队void EnQueue( Queue *Q, int x) /* 将元素 x 压入到队列 Q 中，先申请结点再将其入队 */Q-rear-next = (LinkQueue *)malloc( sizeof(LinkQueue) );Q-rear = Q-rear-next;Q-rear-data = x;Q-rear-next = NULL;(4 ) 出队int DeQueue( Queue *Q ) /*将队列 Q 中的队首元素出队 */LinkQueue *p;int data;if( !IsEmpty( *Q ) ) /* 如果队列非空，则返回队首元素 */p = Q-front-next;Q-front-next = p-next;/* 当将队列中的一个元素删除后，指针 rear 就悬浮起来了， 需要将其调整到正确的状态，即必须使其等于 front *