清华大学数据结构讲义ch3

第三章 栈和队列

栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。

3．1 栈

３.１.１ 栈的定义及基本运算

栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。如图3.1.1所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（Last In First Out），简称 LIFO表。

入栈 top

a3 a2 a1 出栈

图3.1 栈示意图

在日常生活中，有很多后进先出的例子，读者可以列举。在程序设计中，常常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。对于栈，常做的基本运算有： ⑴ 栈初始化：Init_Stack(s)

初始条件：栈s不存在 操作结果：构造了一个空栈。 ⑵ 判栈空：Empty_Stack(s)

初始条件：栈s已存在

操作结果：若s为空栈返回为1，否则返回为0。 ⑶ 入栈： Push_Stack(s，x)

初始条件：栈s已存在

操作结果：在栈s的顶部插入一个新元素x， x成为新的栈顶元素。栈发生变化。 ⑷ 出栈：Pop_Stack(s)

初始条件：栈s存在且非空 38

操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。 ⑸ 读栈顶元素：Top_Stack(s)

初始条件：栈s存在且非空

操作结果：栈顶元素作为结果返回，栈不变化。

3.1.2 栈的存储实现和运算实现

由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。

1． 顺序栈

利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的

一维数组来实现：datatype data[MAXSIZE]，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个int top 来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：

#define MAXSIZE 1024 typedef struct

{datatype data[MAXSIZE]; int top; }SeqStack

定义一个指向顺序栈的指针： SeqStack *s;

通常0下标端设为栈底，这样空栈时栈顶指针top=-1; 入栈时，栈顶指针加１，即s->top++; 出栈时，栈顶指针减１，即s->top--。栈操作的示意图如图3.2所示。

图(a)是空栈，图(c)是A、B、C、D、E 5个元素依次入栈之后，图(d)是在图(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素D、E仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素D、E已不在栈中了，通过这个示意图要深刻理解栈顶指针的作用。 在上述存储结构上基本操作的实现如下：

top=-1 top=0 top=4 top=2 top=-1

(a)空栈 (b)一个元素 (c)5个元素 (d)3个元素 (e)空栈 图3.2 栈顶指针top与栈中数据元素的关系

39

⑴ 置空栈：首先建立栈空间，然后初始化栈顶指针。 SeqStack *Init_SeqStack() { SeqStack *s;

s=malloc(sizeof(SeqStack)); s->top= -1; return s; } ⑵ 判空栈

int Empty_SeqStack(SeqStack *s) { if (s->top= = -1) return 1; else return 0;

}

⑶ 入栈

int Push_SeqStack (SeqStack *s, datatype x)

{if (s->top= =MAXSIZE-1) return 0; /*栈满不能入栈*/ else { s->top++; s->data[s->top]=x; return 1;

}

} ⑷ 出栈

int Pop_SeqStack(SeqStack *s, datatype *x)

{ if (Empty_SeqStack ( s ) ) return 0; /*栈空不能出栈 */ else { *x=s->data[s->top];

s->top--; return 1; } /*栈顶元素存入*x，返回*/ } ⑸ 取栈顶元素

datatype Top_SeqStack(SeqStack *s)

{ if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/

else return (s->data[s->top] ); } 以下几点说明：

1. 对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：s->top= =MAXSIZE-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。

2. 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

2. 链栈

用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表示，即有： typedef struct node 40

{ datatype data; struct node *next; }StackNode，* LinkStack;

说明top为栈顶指针： LinkStack top ;

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。通常将链栈表示成图3.3的形式。链栈基本操作的实现如下：

⑴ 置空栈

LinkStack Init_LinkStack（）

{ return NULL; } ⑵ 判栈空

int Empty_LinkStack（LinkStack top ） { if（top==-1） return 1; else return 0;

} ⑶ 入栈

top

∧ 图3.3 链栈示意图

LinkStack Push_LinkStack（LinkStack top, datatype x） { StackNode *s;

s=malloc（sizeof（StackNode））; s->data=x; s->next=top; top=s; return top; }

⑷ 出栈

LinkStack Pop_LinkStack (LinkStack top, datatype *x) { StackNode *p;

if （top= =NULL） return NULL; else { *x = top->data;

p = top; top = top->next; free (p); return top;

}

}

3．2 栈的应用举例

由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。

41

例 3.1 简单应用：数制转换问题

将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下： N N / 8 （整除） N % 8（求余）

3467 433 3 低 433 54 1 54 6 6

6 0 6 高 所以：（3456）10 =（6563）8

我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。

算法思想如下：当N>0时重复1，2

1． 若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。 2． 用N / r 代替 N 算法如下：

typedef int datatype; #define L 10

void conversion(int N，int r) void conversion(int N，int r)

{ SeqStack s; { int s[L],top; /*定义一个顺序栈*/ datetype x; int x;

Init_SeqStack(&s); top =-1; /*初始化栈*/ while ( N ) while ( N )

{ Push_SeqStack ( &s ，N % r ); { s[++top]=N%r; /*余数入栈 */ N=N / r ; N=N / r ; /* 商作为被除数继续 */ } }

while ( Empty_SeqStack(& s ) ) while (top!=-1) { Pop_SeqStack (&s ，&x ) ; { x=s[top--]; printf ( “ %d ”，x ) ; printf(“%d”,x); } } } }

算法3.1(a) 算法3.1(b)

算法3.1(a)是将对栈的操作抽象为模块调用，使问题的层次更加清楚。而算法3.1(b)中的直接用int向量S和int 变量top作为一个栈来使用，往往初学者将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”，当应用程序中需要一个与数据保存时相反顺序使用数据时，就要想到栈。通常用顺序栈较多，因为很便利。

在后面的例子中，为了在算法中表现出问题的层次，有关栈的操作调用了的相关函数，如象算法3.1(a)那样，对余数的入栈操作：Push_SeqStack ( &s ，N % r ); 因为是用c语言描述，第一个参数是栈的地址才能对栈进行加工。在后面的例子中，为了算法的清楚易读，在不至于混淆的情况下，不再加地址运算符，请读者注意。

例 3.2 利用栈实现迷宫的求解。

问题： 这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。

求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，42

switch (ch).

{ case ch= =’+’： c =a+b ; break ; case ch= =’-’： c=a-b ; break ; case ch= =’*’： c=a*b ; break ; case ch= =’/ ’： c=a/b ; break ; case ch= =’%’： c=a%b ; break ; }

Push_SeqStack (s, c) ; } ch=*A++ ; }

Pop _SeqStack ( s , result ) ; return result ; }

算法3.3

栈中状态变化情况：

当前字符 栈中数据 说明 ３ ２ ４ ２ ２ ＊ ＋ １ ３ ＊ － ^ * 5 - 结束符

图 3.8 后缀表达式求值过程

3． 中缀表达式转换成后缀表达式：

将中缀表达式转化为后缀表达示和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不在赘述。

3 3，２ 3，2，4 3，2，4，2 3，2，4，2，2 3，2，4，4 3，2，8 3，2，8，1 3，2，8，1，3 3，2，8，3 3，2，5 3，32 96 96，5 96 空 ３入栈 ２入栈 ４入栈 ２入栈 ２入栈 计算２＊２，将结果４入栈 计算４＋４，将结果８入栈 １入栈 ３入栈 计算１＊３，将结果４入栈 计算８－５，将结果５入栈 计算2^5，将结果32入栈 计算３＊32，将结果96入栈 5入栈 计算96-5，结果入栈 结果出栈 例3.4 栈与递归：

栈的一个重要应用是在程序设计语言中实现递归过程。现实中，有许多实际问题是递归定义的，这时用递归方法可以使许多问题的结果大大简化，以 n!为例：

n!的定义为： 48

n! =

1 n=0 /*递归终止条件*/ n*(n-1) n>0 /*递归步骤*/

根据定义可以很自然的写出相应的递归函数

int fact (int n)

{ if (n= =0) return 1 ;

else return (n* fact (n-1) ) ;

}

递归函数都有一个终止递归的条件，如上例n=0时，将不再继续递归下去。

递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（ActivaTion Record），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为过程建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。下面以求3!为例说明执行调用时工作栈中的状况。

为了方便将求阶乘程序修改如下： main () { int m，n=３ ; m=fact (n) ; R1：

printf (“%d!=%d\\n”，n，m) ;

}

int fact (int n) { int f ; if (n= =0) f=1 ; else f=n*fact (n-1) ; R2: return f ; }

算法3.4

其中R1为主函数调用fact 时返回点地址，R2为fact函数中递归调用fact (n -1)时返回点地址。 程序的执行过程可用图3.10来示意。 设主函数中n=3 ：

图3.9 递归工作栈示意图 fact(0) fact(1) fact(2) fact(3)

参数 返回地址 0 1 2 3 R2 R2 R2 R１ n=3 n=2 n=1 n=0

m=fact(n) f=3*fact(2) f=2*fact(1) f=1*fact(0) f=1 return f； return f return f return f f=3*2*1*1 f=2*1*1 f=1*1 f=1

图 3.10 fact(3) 的执行过程

49

3.3 队列

3.3.1 队列的定义及基本运算

前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出” (FIFO---First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。如图3.11所示是一个有5 个元素的队列。入队的顺序依次为a1、 a2 、a3 、a4 、 a5 ，出队时的顺序将依然是a1、 a2 、a3 、a4 、 a5 。

出队

a1 a2 a3 a4 a5

图3.11 队列示意图

入队

显然，队列也是一种运算受限制的线性表，所以又叫先进先出表。

在日常生活中队列的例子很多，如排队买东西，排头的买完后走掉，新来的排在队尾。在队列上进行的基本操作有：

⑴ 队列初始化：Init_Queue(q)

初始条件： 队q不存在。 操作结果： 构造了一个空队。 ⑵ 入队操作： In_Queue(q,x),

初始条件： 队q存在。

操作结果： 对已存在的队列q，插入一个元素x到队尾，队发生变化。 ⑶ 出队操作： Out_Queue(q,x)

初始条件: 队q存在且非空

操作结果： 删除队首元素，并返回其值，队发生变化。 ⑷ 读队头元素：Front_Queue(q,x)

初始条件: 队q存在且非空

操作结果： 读队头元素，并返回其值，队不变； ⑸ 判队空操作：Empty_Queue(q)

初始条件： 队q存在

操作结果： 若q为空队则返回为1，否则返回为0。

3.3.2 队列的存储实现及运算实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。

1 顺序队

顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两

个指针。顺序队的类型定义如下： 50

define MAXSIZE 1024 /*队列的最大容量*/ typedef struct

{datatype data[MAXSIZE]; /*队员的存储空间*/ int rear,front; /*队头队尾指针*/ }SeQueue;

定义一个指向队的指针变量： SeQueue *sq;

申请一个顺序队的存储空间： sq=malloc(sizeof(SeQueue)); 队列的数据区为：

sq->data[0]---sq->data[MAXSIZE -1]

队头指针：sq->front 队尾指针：sq->rear

设队头指针指向队头元素前面一个位置，队尾指针指向队尾元素（这样的设置是为了某些运算的方便，并不是唯一的方法）。

置空队则为：sq->front=sq->rear=-1;

在不考虑溢出的情况下，入队操作队尾指针加1，指向新位置后，元素入队。 操作如下： sq->rear++;

sq->data[sq->rear]=x; /*原队头元素送x中*/

在不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。 操作如下：

sq->front++;

x=sq->data[sq->front];

队中元素的个数：m=(sq->rear)-(q->front); 队满时：m= MAXSIZE； 队空时：m=0。

按照上述思想建立的空队及入队出队示意图如图3.12所示，设MAXSIZE=10。

从图中可以看到，随着入队出队的进行，会使整个队列整体向后移动，这样就出现了图3.12(d)中的现象：队尾指针已经移到了最后,再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由于“队尾入队头出”这种受限制

的操作所造成。解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队”，“循环队”的示意图如图3.13所示。

front=rear=-1 front=-1 rear=2 front=5 rear=8 front=5 rear=9 (a) 空队 (b)有3个元素 (c)一般情况 (d) 假溢出现象 图3.12 队列操作示意图

51

图3.13 循环队列示意图

因为是头尾相接的循环结构，入队时的队尾指针加1操作修改为：

sq->rear=(sq->rear+1) % MAXSIZE;

出队时的队头指针加1操作修改为：

sq->front=(sq->front+1) % MAXSIZE;

设MAXSIZE=10，图3.14是循环队列操作示意图。

front=4 rear=8 front=-1 rear=2 front=5 rear=8 front=5 rear=9 (a) 有4个元素 (b) 队满 (c) 队空 (d) 队满

图3.1４ 循环队列操作示意图

从图3.14所示的循环队可以看出，(a)中具有 a5 、a6 、a7 、a8四个元素，此时front=4,rear=8；随着a9~a14相继入队，队中具有了10个元素---队满，此时 front=4,rear=4,如（b）所示，可见在队满情况下有：front==rear。若在（a）情况下，a5~a8相继出队，此时队空， front=4，rear=4，如（c）所示，即在队空情况下也有：front==rear。就是说“队满”和“队空”的条件是相同的了。这显然是必须要解决的一个问题。

方法之一是附设一个存储队中元素个数的变量如num，当num==0时队空，当num==MAXSIZE时为队满。 另一种方法是少用一个元素空间，把图（d）所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1) % MAXSIZE==front，也能和空队区别开。

下面的循环队列及操作按第一种方法实现。 52

本文来源：https://www.bwwdw.com/article/dosx.html