1
栈和队列的基本操
作是线性表操作的子集，
是限定性（操作受限制）
的数据结构。
第三章栈和队列
数
据
结
构
之
栈
和
队
列
2
3. 1 栈
? 定义：是限定仅在表尾进行插入或删除操作
的线性表。 (后进先出线性表 LIFO)
? 栈底指针 (base) :是线性表的基址；
? 栈顶指针 (top):指向线性表最后一个元素的后面。
? 当 top=base 时，为空栈。
? 基本操作：
InitStack(&S), DestroyStack(&S),
StackEmpty(S) , ClearStack(&S),
GetTop(S ,&e), StackLength(S) ,
Push(&S, e): 完成在表尾插入一个元素 e.
Pop(&S,&e): 完成在表尾删除一个元素。
2
数
据
结
构
之
栈
和
队
列
3
?栈的表示和实现
? 顺序栈：是利用一组地址连续的存储单元
依次存放自栈底到栈顶的数据元素；栈满
之后，可再追加栈空间即为动态栈。
? 顺序栈的结构类型定义：
typedef int SElemType;
typedef struct{
SElemType *base; /* 栈底指针 */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 栈空间大小 */
}SqStack ;
数
据
结
构
之
栈
和
队
列
4
? 基本算法描述
?建立能存放 50个栈元素的空栈
#define STACK_INIT_SIZE 50
#define STACKINCREMENT 10
Status InitStack_Sq(Stack &S){
S.base=(SET*)malloc(STACK_INIT_SIZE
*sizeof(SET)); /*为栈分配空间 */
if(S.base==NULL)
exit(OVERFLOW); /*存储分配失败 */
S.top=S.base;
S.stacksize = STACK_INIT_SIZE;
return OK; }
3
数
据
结
构
之
栈
和
队
列
5
?出栈操作算法
void pop(Sqstack s, SElemType e)
{
if(s.top= = s.base)
return ERROR;
else{
s.top--;
e= *s.top;
}
return OK;
}
出栈操作
top
A
B
Y top
A
B
Ybase base
数
据
结
构
之
栈
和
队
列
6
?压栈操作算法
void Push(SqStack s, SElemType e)
if(s.top-s.base>= S.stacksize;) {
S.base=(SET*)realloc(S,base,(S.stacksize+STACKINCREMEN
T) *sizeof(SET)); /*为栈重新分配空间 */
if(！ S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;}
return OK; }
top
A
B
压栈操作
top
A
B
e
base
base
4
数
据
结
构
之
栈
和
队
列
7
?栈的销毁
void DestroyStack_Sq(Stack &S){
if (S.base) free(S.base);
S.base=NULL;S.top=NULL;
S.stacksize=0;
}
?栈的清除
void ClearStack_Sq(Stack &S){
S.top = S.base ;
}
数
据
结
构
之
栈
和
队
列
8
?判断栈是否为空栈
Status StackEmpty_Sq(Stack S){
if(S.top==S.base) return TRUE;
else return FALSE;
}
?获得栈的实际长度
int StackLength_Sq(Stack S){
return(abs(S.top-S.base));
}
5
数
据
结
构
之
栈
和
队
列
9
? 多个栈共享邻接空间
两个栈共享一空间
:
:
:
:
:
:
top1
top2
1
m
中间可用空间
栈 1
栈 2
地址
Base1
Base 2
……
数
据
结
构
之
栈
和
队
列
10
3. 3 栈与递归
? 递归函数：一个直接调用自己或通
过一系列的调用语句间接地调用自
己的函数。
? 调用函数前，系统需先完成三件事：
?将所有的实在参数、返回地址等信息传
递给被调用函数保存；
?为被调用函数的局部变量分配存储区；
?将控制转移到被调用函数的入口。
6
数
据
结
构
之
栈
和
队
列
11
? 从被调用函数返回调用函数之前，系
统需先完成三件事：
?保存被调函数的计算结果；
?释放被调函数的数据区；
?依照被调函数保存的返回地址将控制转
移到调用函数。
? 嵌套调用时，按照“后调用先返回”
的原则
数
据
结
构
之
栈
和
队
列
12
? 栈的应用 ——递归和非递归
? 函数之间的信息传递和控制转移必须通过
“栈”来实现：系统将整个程序运行时所
需的数据空间安排在一个栈中，每当调用
一个函数时，就为它在栈顶分配一个存储
区；每当从一个函数退出时，就释放它的
存储区，则当前正运行的函数的数据区必
在栈顶。 ( Page 56 )
7
数
据
结
构
之
栈
和
队
列
13
? 递归函数的运行过程类似于多个函数
的嵌套调用
? 递归函数的运行的“层次”
数
据
结
构
之
栈
和
队
列
14
例 1.已知 f(m,n)函数 (m,n均为自然数 )的定义
如下：
m+n+1 (m*n=0)
f(m,n)=
f(m-1,f(m,n-1)) (m*n≠0)
( 1)写出计算f(m,n)的递归算法。
( 2)利用堆栈改写出非递归算法。
( 3)根据非递归算法，画出计算f(2,1)时
值参、局部变量以及堆栈的变化情况。
8
数
据
结
构
之
栈
和
队
列
15
F函数的递归算法
int f(int m,int n){
if(m*n==0)
return(m+n+1);
else
return( f (m-1, f(m,n-1) ) );
}
数
据
结
构
之
栈
和
队
列
16
F函数递归示意图
5
3
5
3
4
2 , 0
1,0
0,2
1 , 2
0 , 4
1, 1
0, 3
1 , 3
2， 1
2
3
4
5
int f(int m,int n){
if(m*n==0)
return(m+n+1);
else {x=f(m,n-1) ;
y=f (m-1, x) ;
return(y);}
}
9
数
据
结
构
之
栈
和
队
列
17
F函数的非递归算法
int F(int m,int n){
if(m>=0 && n>=0){
InitStack(S); push(S, m , n);
while(!StackEmpty(S) ){
pop(S, m , n);
if (n==-1) n=result;
if (m*n= =0) {result = m+n+1;}
else {push(S,m-1,-1);push(S,m,n-1);} }
return result; }
} //typedef struct{int m,n;}SElemType;
数
据
结
构
之
栈
和
队
列
18
while(!StackEmpty(S) )
{
pop(S, m , n);
if(n==-1)
n=result;
if(m*n= =0)
result = m+n+1;
else {
push(S,m-1,-1);
push(S,m,n-1);
} }
0， -1320第七次循环
0， -1
0， -1
0， -1
201第六次循环
1， 0
0， -1
0， -1
0， -1
311第五次循环
1， 1
0， -1
0， -1
321第四次循环
1， 2
0， -1
331第三次循环
1， -1302第二次循环
2， 0
1， -1
12第一次循环
2,1121,2条语句
SResultNM标号
10
数
据
结
构
之
栈
和
队
列
19
? 例 2： Hanoi问题：设有三座塔，依次命名为 X、
Y、 Z，有 n个直径不相同的圆盘，由小到大依
次编号为 1， 2， 3， ….n，开始时，它们前部按
大小递减的顺序插在塔座 X上，现在要求把 n个
圆盘按大小递减的顺序放在塔座 Z上。其移动规
则如下：
1、每次只能移动一个圆盘；
2、圆盘可以放在任一个塔座上；
3、任何时刻不能将大圆盘压在小圆盘上；
1
2
3
1
2
3
XY Z
X
Y
Z
数
据
结
构
之
栈
和
队
列
20
int count=0;
void hanoi(int n,char x,char y, char z) {
if（ n == 1） move(x,1,z);
else{
hanoi(n-1,x,z,y); /*递归调用 */
move(x,n,z); /*将 x上编号为 n的盘放到 z上 */
hanoi(n-1,y,x,z);
} }
void move(char x, int n, char z) {
printf(“%d: move disk %d from %c to
%c\n”,++count, n,x,z);
return; }
11
数
据
结
构
之
栈
和
队
列
21
汉诺塔问题的非递归算法。
void Hanoi(int n,int x,int y,int z){
InitStack(S);push(S , n , x , y , z);
while(!StackEmpty(S)){
pop(S,n,x,y,z);
if ((y== -1)||(n ==1)) move(n,x,z);
else{ push(S,n-1,y,x,z);
push(S,n,x,-1,z);
push(S,n-1,x,z,y);} }
}
void move(int n,int a,int b){
printf(“第 %d号盘子从 %d柱移到 %d柱 ”,n,a,b);}
数
据
结
构
之
栈
和
队
列
22
1. 4 队列
? 定义：是一种先进先出的线性表，它只允
许在表的一端进行插入，而在另一端删除
元素。
? 队头 (front)——是删除元素（出队操作）端；
? 队尾 (rear)——是插入元素（入队操作）端。
12
数
据
结
构
之
栈
和
队
列
23
? 基本操作：
? InitQueue(&Q)
? DestroyQueue(&Q)
? ClearQueue(&Q)
? QueueEmpty(Q)
? QueueLength(Q)
? GetHead(Q,&e)
? EnQueue(&Q, e)
? DeQueue(&Q,&e)
数
据
结
构
之
栈
和
队
列
24
? 链式队列
typedef int QElemType; /* 队列元素类型 */
typedef struct QNode{
QElemType data;
struct QNode *next;
} Qnode; /* 队列结点类型 */
typedef struct Queue{
Qnode *rear ;
Qnode *front ;
} LinkQueue; /* 链式队列类型 */
13
数
据
结
构
之
栈
和
队
列
25
LinkQueue Q ;
队列： 出队端 入队端
空队列：
头 5 8 3 6 ^front
rear
Q.
头 ^front
rear
Q.
数
据
结
构
之
栈
和
队
列
26
? 链式队列的基本操作
Status InitQueue(LinkQueue &Q){
p=(Qnode *)malloc(sizeof(Qnode));
if(!p) exit(OVERFLOW);
p->next = NULL;
Q.front =p;
Q.rear =p;
return OK;
}
14
数
据
结
构
之
栈
和
队
列
27
void addq(LinkQueue &Q,QElemType e) {
p=(Qnode *)malloc(sizeof(Qnode));
if(!p) return (OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p; Q.rear=p;
return OK; }
队首 队尾
front
rear
……
^
队首
队尾
front
rear
……
^
数
据
结
构
之
栈
和
队
列
28
void deleteq(LinkQueue Q,QElemType &e) {
/* 在 front 处删除一个元素，把值送入 e中 */
if(Q.front==Q.rear) return ERROR;
p = Q.front->next; e=p->data;
Q.front->next=p->next;
if(Q.rear= =p) Q.rear=Q.front;
free(p); return OK; }
队首 队尾
front
rear
……
^
队首
front
……
队尾
^
rear
15
数
据
结
构
之
栈
和
队
列
29
? 队列的顺序表示和实现
typedef Struct {
QElemType *base ;
int front ;
int rear ;
int qsize ;
} SqQueue ;
SqQueue Q;
空队状态： Q.front == Q.rear
满队状态： Q.rear == Q.qsize
数
据
结
构
之
栈
和
队
列
30
? 循环队列
? 定义 :设向量 Q(0:n-1)表示队列， Q(0)表示队
首， Q(n-1)表示队尾，而 Q(0)接在 Q(n-1)后面
形成一个环，顺时针方向旋转。
? 为了测定队列是否满，将采用队列少用一个
元素空间，作为队列呈“满”状态的标志。
空队： Q.front = = Q.rear
满队： (Q.rear+1) % Q.qsize = = Q.front
16
数
据
结
构
之
栈
和
队
列
31
#define MAXQSIZE 100
typedef struct{
QElemType *base; /*初始化的动态分配
存储空间 */
int front; /*头指针，若队列不空，
指向队列头元素 */
int rear; /*尾指针，队列不空时指
向队列的下一个元素 */
} SqQueue; /*队列名称 */
数
据
结
构
之
栈
和
队
列
32
入队列的程序段如下：
int en_cycque(SqQueue &Q, QElemType e)
{
if (Q.rear+1)%MAXQSIZE=Q.front)
return ERROR
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%maxsize;
return OK;
}
Q.front=3 Q.rear=2
J1
J2
J4
J3
01
2
3
队满，不能插入，此方法
少用一个元素空间。
17
数
据
结
构
之
栈
和
队
列
33
出队列的程序段如下：
void DeQueue(SqQueue &Q, QElemType &e) {
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}
Q.front=0
Q.rear=2
J1
J2
0 1
2
3
J4
J3
数
据
结
构
之
栈
和
队
列
34
? 循环队列的基本操作：
……必须熟练掌握这些算法 …...
?InitQueue(&Q)
?DestroyQueue(&Q)
?ClearQueue(&Q)
?QueueEmpty(Q)
?QueueLength(Q)
?GetHead(Q,&e)
?EnQueue(&Q, e)
?DeQueue(&Q,&e)
18
数
据
结
构
之
栈
和
队
列
35
问题：
确定一个链式队列需要头、尾
两个指针，而确定链式循环队列只
需一个指针，问该指针应该指向循
环链队的何处？
? 算法练习：算法练习：
请编写循环链队的出、入队算法。请编写循环链队的出、入队算法。
数
据
结
构
之
栈
和
队
列
36
?本章重点
? 堆栈和队列的基本概念和基本操作
? 分别用顺序结构和链式结构实现堆栈
及队列的基本操作
? 堆栈及队列的应用及程序设计。
19
数
据
结
构
之
栈
和
队
列
37
单元测验
? 线性表、栈、队列的基本概念、
基于两种存储表示的各类型定义；
? 各基本操作的算法描述；
? 线性表、栈、队列的应用。
