Ch.3 栈和队列 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥）

§3.1 栈 定义和运算 入栈 出栈 栈 —— 仅在表的一端插、删的线性表 栈顶 —— 插删的一端 栈底 —— 另一端 插入——进（入）栈、删除——出（退）栈 栈顶 —— 插删的一端 栈底 —— 另一端 结构特征 --“后进先出” 修改原则：退栈者总是最近入栈者 服务原则：后来者先服务 （LIFO表） 例： 入栈 出栈

§3.1 栈 Note:后入栈者先出栈，但不排除后者未进栈，先入栈者先出栈。 基本运算：① 判栈空 ②入栈 ③出栈 ④判栈 满 ⑤读栈顶 ⑥置空栈

§3.1.1 顺序栈 底相对固定 可设在向量的任一端 Top指针为下标类型 (整型量) #define StackSize 100 typedef struct { DataType data[StackSize]; int top; }SeqStack;

§3.1.1 顺序栈 设栈底在向量低端data[0]，则： 入栈 ：top+1 出栈：top-1 栈空：top<0 栈满：top=StackSize-1 上溢：满时入栈 下溢：空时出栈(不一定是错误，可能是转移控制条件)

§3.1.1 顺序栈 Note：top指针不是指物理地址，与C的指针变量含义不同。可理解为相对地址，是指示元素的所在位置

§ 3.1.1 顺序栈 实现 初始化 （置空栈） int StacEmpty(SeqStack *S) { //亦可用非指针类型 判栈满 void InitStack(SeqStack *S) { S->top=-1; } 判栈空 int StacEmpty(SeqStack *S) { //亦可用非指针类型 return S->top<0; 判栈满 int StackFull (SeqStack *S) { return S->top==StackSize-1;

§ 3.1.1 顺序栈 入栈 void Push(SeqStack *S, DataType x) { if ( StackFull(S) ) Error(“overflow”);//上溢，退出运行 S->data[++S->top]=x; // 指针先加1，后x入栈 } 出栈 DataType Pop(SeqStack *S) { if ( StackEmpty(S) ) Error(“UnderFlow”); //下溢 return S->data[S->top--]; //返回栈顶后指针减1 读栈顶

§ 3.1.2 链栈 只在表头操作，故头指针即为top，无需头结点 定义 typedef struct snode { DataType data; struct snode *next; } StackNode; typedef struct { StackNode *top; } LinkStack; 链栈动态分配结点，无需考虑上溢

§ 3.1.2 链栈 void InitStack(LinkStack *S) { S->top=NULL; } int StackEmpty (LinkStack *S) { return S->top==NULL; void Push(LinkStack *S, DataType x) { StackNode *p=(StackNode*) malloc (sizeof(StackNode)); p->data=x; p->next=s->top; s->top=p;

§ 3.1.2 链栈 DataType Pop(LinkStack *S) { DataType x; StackNode *p=S->top; //保存栈顶指针 if ( StackEmpty(S) ) Error (“underflow”); // 下溢 x=p->data; //保存栈顶数据 S->top=p->next; //将栈顶结点从链头摘下 free(p); //释放原栈顶结点空间 return x; } EX.3.6，3.17，3.19

§3.2 队列 定义 队列：运算受限的线性表，一端插入(队尾)，另一端删除(队头)。 结构特征 先进先出，先来先服务，FIFO表 例子：排队现象 操作 入队(插入)序列： 出队(删除)序列：

§ 3.2 队列 顺序队列 —— 队列的顺序存储结构 空队列：front = rear； 初值为0 入队：插入rear位置，然后加1

§ 3.2 队列 上溢：队满时入队 下溢：队空是出队 (不一定是错误，可能是转移控制条件) 伪上溢：队非满但不能插入 原因：f，r 只增不减 例如：入，出，入，出，…… 尽管任一时刻，队中最多只有1个元素，但无论事先定义多大的空间，均会产生指针越界

§ 3.2 队列 怎样消除伪上溢？ 循环队列 实用顺序队列多为循 重复利用已删除的结点空间，将向量视为首尾相接的环。这种用循环向量实现的队列称为循环队列。 f，r在循环意义下的加1动作：越界时，令其指向下界0 i = (i+1==QueueSize) ? 0:i++; // i为front或rear 可用模运算简化： i=(i+1)%QueueSize; 循环队列 实用顺序队列多为循 环队列

§ 3.2 队列 边界问题 定义 队满和队空时，front=rear，如何区分？解决方法： 设一布尔量以示区分 留一个结点不用。约定 入队前，测试尾指针+1 (循环定义下) 是否等于头指针。若相等则为满 使用1个计数器，记录队列长度 （用此法） 定义 #define QueueSize 100 typedef struct { int front; int rear; int count; DataType data [QueueSize]; } CirQueue;

§ 3.2 队列 操作实现 置空队 void InitQueue (CirQueue *Q) { Q->front = Q->rear = 0; Q->count = 0; // 队空 } 判队空 int QueueEmpty (CirQueue *Q) { return Q->count == 0; } 判队满 int QueueFull (CirQueue *Q) { return Q->count ==QueueSize; }

§ 3.2 队列 入队 void EnQueue (CirQueue *Q, DataType x) { if (QueueFull (Q) ) Error(“overflow”); //上溢 Q->count++; Q->data [Q->rear] = x; // 插入 Q->rear = (Q->rear+1)%QueueSize; // 尾指针加1 } 出队 DataType DeQueue (CirQueue *Q) { if (QueueEmpty (Q) ) Error (“underflow”); //下溢，不一定是错 temp = Q->data[Q->front]; Q->count--; Q->front= (Q->front+1)%QueueSize; // 头指针加1 return temp; }

§ 3.2 队列 链队列 仅限于在表头和尾插删的单链表 typedef struct qnode{ DataType data; struct qnode *next; }QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; LinkQueue Q; 不带头节点：

void InitQueue (LinkQueue *Q) { Q->front = Q->rear = NULL; //若有头结点则不同 } int QEmpty (LinkQueue *Q) { //无上溢，故不判满队 return Q->front == NULL; //头尾指针均为空，有头结点时f = r void EnQueue (LinkQueue *Q, DataType x) { QNode *p = (QNode *) malloc( sizeof(QNode) ); p->data = x; p->next = NULL; // 新结点作为新的队尾 if ( QEmpty(Q) ) // 若有头结点无需判此项 Q->front = Q->rear = p; // *p插入空队 else { // 插入非空队尾，有无头结点均要做此项 Q->rear->next = p; // *p链到原尾结点之后。 Q->rear = p; // 指向新尾*p

3.链队列 DataType DeQueue (LinkQueue *Q) { if ( QEmpty(Q) ) } Ex.3.28 Error (“underflow”); //下溢 p = Q->front; // 指向队头 x = p->data; Q->front = p->next; // 队头摘下 if (Q->rear == p) // 原队中只有一个结点，删去后队变空 Q->rear = NULL; free (p) ; return x; } Ex.3.28

§ 3.3 栈和队列的应用 § 3.3.1 栈的应用 数据转换 问题： 一非负十进制整数N  B进制整数 例：2810= 3•81 + 4•80 = 348 7710= 1•43 + 0•42 + 2•41 + 5•40 = 10254 规律： 其中 表示B进制数的第 i 位数字 十进制数N可用 位B进制数表示为 (3.1)

§3.3.1 栈的应用 如何确定bj ？ 令 ，则（3.1）式为： （3.2） 该式整除B，则余数为b0，商为括号内的和式。故 (3.2)式可表达为： N = ( N/B )•B + N%B // “/”为整除 算法思想 模除求余数： N%Bb0 整除求商：N/B，令其为新N，重复①求b1，反复至某N为0时结束 上述过程依次求出的B进制各位为(从低位至高位): b0,b1 ,… , bj，用栈保存，退栈输出bj,bj-1 ,… , b0即为所求。

§ 3.3.1 栈的应用 例如：

while (N) { //从右向左产生bi , i=0,1, …, j Push( &S, N%B); // 将 bi 入栈 N=N/B; 实现 typedef int DataType； void MultiBaseOutput (int N, int B) { // N为非负十进制整数， B为基 int i; SeqStack S; //顺序栈S InitStack( &S ); //置空栈 while (N) { //从右向左产生bi , i=0,1, …, j Push( &S, N%B); // 将 bi 入栈 N=N/B; } while( !StackEmpty(&S) ) { // 栈S非空 i = Pop(&S); printf(“%d”,i); 时间复杂度：O(logBN ) 25 25

2.栈与递归 § 3.3.1 栈的应用 递归是一种强有力的数学工具，可使问题的描述和求解变得简洁与清晰 递归 若一函数、过程或数据结构定义的内部又直接或间接使用了定义本身，则称它们是递归的，或递归定义的 26 26

2.栈与递归 例：Bakus-Naur Form (BNF) 巴科式范式早期定义Algol 60 语法。 直接递归 <标识符> ::= <字母>|<标识符><字母>|<标识符><数字> <字母> ::= a| b | …… | y | z <数字> ::= 0 | 1| 2| | …… | 8 | 9 由此定义的标识符是由字母打头的字母数字串 简接递归 <表达式> ::= <项> + <项> | <项> － <项> | <项> <项> ::= <因子> * <因子> | <因子> / <因子> | <因子> <因子> ::= (<表达式>) | <字母> | <数字> 合法的表达式：A+5，B*C+D，(A+B*C)/D 非终结符 终结符 可选分隔符

//递归终结条件 //递归步骤 (n-1)!的规模比n!小1 2.栈与递归 例 1： 递归算法设计（分治法）分解、求解、组合 step1： 将原问题分解为一个或多个规模更小，但与问题特性类似的子问题 (递归步骤) // 解子问题为调用语句 step2：确定一个或多个无须分解，可直接求解的最小子问题 (终结条件)// 归纳基础 例 1： //递归终结条件 //递归步骤 (n-1)!的规模比n!小1

2.栈与递归 int F (int n) { //设n为非负整数 if (n==0) return 1; else return n*F(n-1) ; } 至少有一个直接求解的最小子问题，保证递归终止，否则无限循环 分解为一个子问题，若F(n)是解n!，则F(n-1)可解(n-1)! 29 29

2.栈与递归 有些问题表面上不是递归定义的，但可通过分析，抽象出递归的定义。 例2：写一个就地生成n个元素a1, a2, …, an全排列 (n!) 的算法，要求算法终止时保持a1, a2, …, an原状 解：设 A[0 ..n-1] 基类型为char,“就地”不允许使用 A 以外的数组 生成a1, a2, …, an全排列  n个子问题 求n-1个元素的全排列 + nth个元素 1st子问题 a1, a2, …, an-1 an // 2nd子问题 a1, …, an-2, an an-1 //A[n-1]↔A[n] 3rd子问题 a1, …, an, an-1 an-2 //A[n-2]↔A[n] ┊ ┊ ┊ nth子问题 an,a2 …, an-1 a1 //A[1]↔A[n] 递归终结分支 当 n=1 时， 一个元素全排列只有一种，即为本身。实际上无须进一步递归，可直接打印输出A

2.栈与递归 算法：以A[0..7]为例 void permute (char A[ ], int n) { //外部调用时令 n=7 if (n==0) print (A); // 打印A[0..n] else { Permute(A,n-1); //求A[0..n-1]的全部排列。1st子问题不用交换 for (i=n-1; i>0; i--) { Swap(A[i], A[n]); // 交换ai 和an 内容，说明为引用 Permute(A,n-1); // 求A[0..n-1] 全排列 Swap(A[i],A[n]); //交换，恢复A[0..n]原状 }//endfor }//endif } 时间： 所以实验时，n不能太大

2.栈与递归 例3：n阶Hanoi塔问题 将X上的圆盘移到Z上，要求按同样次序排列，且满足： 每次只能移动一片 圆盘可插在X,Y,Z任一塔座上 任一时刻大盘不能压在小盘上

分解 设 n>1 原问题：将n片从X移到Z，Y为辅助塔，可分解为： 将上面n-1 个盘从X移至Y，Z为辅助盘 将 nth 片从X移至 Z 将Y上n-1个盘子移至Z，X为辅助盘 终结条件 n = 1时，直接将编号为1的盘子从 X 移到Z void Hanoi (int n, char x, char y, char z ) { // n个盘子从 X 移至 Z，Y 为辅助 if ( n==1 ) move(X,1,Z); // 将1号盘子从 X 移至 Z, 打印 else { Hanoi (n-1,x,z,y); //源X，辅Z，目Y move (x,n,z); Hanoi (n-1,y,x,z); //源Y，辅X，目Z } //子问题特征属性与原 //问题相同规模小1，参 //数不同

§ 3.3.1 栈的应用 3.递归的内部实现 调用 调用一个函数时，系统将为调用者构造一个活动记录，并将其压入栈的顶，然后将程序控制权转移到被调用函数。若被调用函数有局部变量，则在栈顶也要为其分配空间，形成一个活动结构。 实际上所有的递归或非递归函数都是这样实现的 活动结构： 局部变量 活动记录：参数表的内容为实参 返址为函数调用语句的下一指令的位置

3.递归的内部实现 返回 当被调用函数执行完毕时，系统将活动结构退栈，并根据退栈返回地址将程序控制权转移给调用者继续执行 例： F(4)为例 改写： int F (int n) { int temp; if (n==0) return 1; //返回语句引 起退栈 else { //调用F(n-1) 引起入栈 temp = n*F(n-1); return temp; // 退栈 } void main(void) { int n; n = F(4); //调用引起压栈 } Ret L1 Ret L1: 赋值语句的地址 Ret L2: 计算乘法的地址 为简单起见，假设局部变量不入栈 Ret L2

3.递归的内部实现 执行返回指令 Ret L2: temp=1*1; //从F(0）返回 0! = 1 是递归终结条件，故执行F(0)引起返回(return 1) 退栈 , 返回到F(1)的Ret L2处，继续执行temp = 1*1； 按着执行return temp又引起 退栈，返回到F(2)的Ret L2处，执行temp = 2*1，… 执行返回指令 Ret L2: temp=1*1; //从F(0）返回

§ 3.3.1 栈的应用 4.递归算法的正确性 初学者很难相信递归程序的正确性 原因：一个函数尚未完成 (即对本函数的正确性还未确 信) 时又调用了自身，故对递归函数正确性缺乏信心 例：非递归函数或过程 假设Q正确的情况下，证明了P正确， 则一旦证明了被调过程Q是正确的，我们就对P的正确性深信不疑！ 由于P、Q各自独立，独立于P来证明Q的正确性很容易，这大概是对自己写非递归程序较有信心的缘故

4.递归算法的正确性 若P是递归过程，则不可能独立于P来证明被调过程 (亦自身) 是否正确。因此，我们只能假设过程P内部所有递归的调用是正确的 (不考虑其内部实现细节)，才能由此证明P的正确性。其理论依据是数学归纳法： （1）证明参数满足递归终结条件时函数或过程正确 (相当于归纳基础)。 （2）假设过程函数内部的所有递归调用语句正确 (相当于归纳假设)，由此证明过程正确或函数是正确的 (相当于归纳步骤) Note: 函数内的递归调用语句的参数应比函数本身的参数更接近递归终结条件参数，这样才能确保递归是可终止的

§ 3.3.1 栈的应用 上机题： 调试跟踪：全排列和Hanoi塔

§3.3.2 队列的应用 例：周末舞会，男、女各排成一队，跳舞时，依次从男、女队的头上各出一人配成舞伴，若两队人数不同，较长的队中未配对者等下一轮舞曲 typedef struct { char name[20]; char sex; // M—男，F—女 } Person; typedef person DataType; //将队列定义中的数据类型改为Person void DancePartners（Person dancer[ ], int num）{ int i; Person P; CirQueue Mdancers, Fdancers; InitQueue(&Mdancers); // 男士队列 InitQueue(&Fdancers);

§3.3.2 队列的应用 for( i=0; i<num; i++ ) {//num个男女依其性别入队 P = dancer[ i ]; if (P.sex == ‘M’) EnQueue (&Mdancers, P); // 入男队 else EnQueue (&Fdancers, P); // 入女队 } printf (“The dancing partners are:\n\n”); while (!QueueEmpty(&Fdancers) && !QueueEmpty(&Mdancers)) { // 男女队列均非空 P=DeQueue(&Fdancers); // 女士出队 printf(“%s ”, P.name); // 女士姓名 P=DeQueue(&Mdancers); //男士出队 printf(“%s\n”, P.name);

§3.3.2 队列的应用 if (!QueueEmpty(&Fdancers)) { //女队非空，输出剩余人数及队头者名字 printf(“\n There are %d women waiting for the next round.\n”, Fdancers.count);// count是队列属性，长度 P=QueueFront(&Fdancers); // 取队头 printf (“%s will be the first to get a partner.\n”, P.name); } else{ // 男队类型处理 } 时间复杂度：O(n)