狠狠撸

通常称，栈和队列是限定插入和
删除只能在表的 “ 端点 ” 进行的线性表。

线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n

栈和队列是两种常用的数据类型

第三章栈和队列
3.1 栈 (stack)
3.2 栈的应用举例
3.4 队列
(Queue)

学习提要：
1. 掌握栈和队列这两种抽象数据类型的特
点，
并能在相应的应用问题中正确选用它们。
2. 熟练掌握栈类型的两种实现方法，即两
种存
储结构表示时的基本操作实现算法，特别
应
注意栈满和栈空的条件以及它们的描述方
法。
3. 熟练掌握循环队列和链队列的基本操作
实现

§3.1 栈（ stack ）
3.1.1 栈的类型定义

3.1.2 栈的表示和实现

3.1.1 栈的类型定义
?栈的定义和特点
?定义：限定仅在表尾进行插入或删
除操作的线性表，表尾 — 栈顶，表头
— 栈底，不含元素的空表称空栈。
进栈出栈
栈 ...
an
顶
……...

栈 s=(a1,a2,……,an)
a2
栈底 a1

?特点：先进后出（ FILO ）或后进先
出（ LIFO ）

? 栈的类型定义
ADT Stack {
数据对象：
D ＝ { ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：
R1 ＝ { <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定 an 端为栈顶， a1 端为栈底。
基本操作：
} ADT Stack

InitStack(&S)
DestroyStack(&S)
StackLength(S)
StackEmpty(s)
GetTop(S, &e)
ClearStack(&S)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())

3.1.2 栈的表示和实现
?顺序栈
类似于线性表的顺序映象实
现，指向表尾的指针可以作为栈
顶指针。
//----- 栈的顺序存储表示 -----
#define STACK_INIT_SIZE 100; // 存储空间初始分配量
#define STACKINCREMENT 10;// 存储空间分配增量
typedef struct {
SElemType *base; // 栈底指针
SElemType *top; // 栈顶指针
int stacksize; // 栈的当前可使用的最大容量
} SqStack;

实现：一维数组 s[M]
栈满栈空
top
5 top F 5 5
4 top E 4 4
3 top D 3 3
top 2
2 top C 2
top B 1
1 top B 1
top top A 0
base 0 top A 0 base
base 出栈
空栈进栈
栈底指针 b a s e , 始设数组维数为 M
终指向栈底位置； to p =b a s e , 栈空，此时出栈，
栈顶指针 to p , 其初则下溢（ und e rflo w)
值指向栈底，始终
在栈顶元素的下一
to p =M, 栈满，此时入栈，则
个位置上溢（ o ve rflo w)

Status InitStack (SqStack &S)
{// 构造一个空栈 S
S.base=(SElemType*)malloc(STACK_INIT_SIZ
E *sizeof(SElemType));
if (!S.base) exit (OVERFLOW); // 存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}

Status Push (SqStack &S, SElemType e) {
if (S.top - S.base >= S.stacksize) {// 栈满，追加存储空
间
S.base = (SElemType *) realloc ( S.base,
(S.stacksize + STACKINCREMENT) *
sizeof (SElemType));
if (!S.base) exit (OVERFLOW); // 存储分配失
败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;

Status Pop (SqStack &S, SElemType &e) {
// 若栈不空，则删除 S 的栈顶元素，
// 用 e 返回其值，并返回 OK ；
// 否则返回 ERROR
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}

?链栈
栈的链式存储结构。栈顶指针
就是链表的头指针。
栈顶指针
an an-1 a1 ∧

注意 : 链栈
中指针的方
向

? 入栈操
作
top top
栈底
p x …... ^

p->next=top ; top=p
? 出栈操
作
q top
栈底
top …... ^

q=top ; top=top->next; //q 返回了出栈的元素

§3.2 栈的应用
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.3 行编辑程序问题
3.2.4 迷宫求解
3.2.5 表达式求值

3.2.1 数制转换

十进制 N 和其他 d 进制数的转换
原理 :

N=( N div d )*d + N mod d

其中： div 为整除运算， mod 为
求余运算

例如： (1348)10=(2504)8 ，其运算过程如
下：
N N div 8 N mod 输
8
计
算 1348 出
168 4
顺顺
序 168 21 0 序

21 2 5 top
top 2
2 0 top
2 5 5
top 0 0
top 4 4 0
4 4

void conversion( ) {
initstack(S); // 构造空栈
scanf (“%d”,N);
while(N){
push(S ， N%8);
N=N/8; }
while(! Stackempty(s)){
pop(S,e);
printf(“%d”,e); }
}//conversion

3.3.2 括号匹配的检验
假设在表达式中
（［］（））或［（［］［］）］
等为正确的格式，
［（］）或（［（））或（（）
］ ) 均为不正确的格式。

则检验括号是否匹配的方法可用
“ 期待的急迫程度 ” 这个概念来描述。

例如：考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 34 5 6 7 8
分析可能出现的不匹配的情况 :
?到来的右括弧并非是所 “ 期待
” 的；
?直到结束，也没有到来所
“ 期待” 的括弧。

算法的设计思想：
1 ）凡出现左括弧，则进栈；
2 ）凡出现右括弧，首先检查栈是否空
若栈空，则表明该“ 右括弧 ” 多余，
否则和栈顶元素比较，
若相匹配，则“ 左括弧出栈 ” ，
否则表明不匹配。
3 ）表达式检验结束时，
若栈空，则表明表达式中匹配正确，
否则表明“ 左括弧 ” 有余。

3.2.3 行编辑程序问题
不恰
如何实现？当!
“ 每接受一个字符即存入存储器 ” ?
合理的作法是：
设立一个输入缓冲区，用以接
受用户输入的一行字符，然后逐行
存入用户数据区，并假设 “ #” 为退
格符， “ @” 为退行符。

假设从终端接受了这样两行字符：
whli##ilr#e （ s#*s)
outcha@putchar(*s=#++);
则实际有效的是下列两行：
while (*s)
putchar(*s++);
算法见 P50 算法 3.2

while (ch != EOF) { //EOF 为全文结束符
while (ch != EOF && ch != 'n') {
switch (ch) {
case '#' : Pop(S, c); break;
case '@': ClearStack(S); break;// 重置 S 为空栈
default : Push(S, ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}
将从栈底到栈顶的字符传送至调用过程的
数据区；
ClearStack(S); // 重置 S 为空栈
if (ch != EOF) ch = getchar();

3.2.4 迷宫求解
通常用的是“ 穷举求解 ” 的方法
# # # # # # # # # #
# →↓ # $ $ $ # #
# ↓ # $ $ $ # #
# ↓ ←$ $ # # #
# ↓ # # # # #
# →→↓ # # #
# # →→↓ # #
# # # # # ↓ # # #
# →→→Θ #
# # # # # # # # # #

求迷宫路径算法的基本思想是
：
?若当前位置“ 可通 ” ，则纳入
路径，继续前进 ;
?若当前位置“ 不可通” ，则后退，
换方向继续探索 ;
?若四周“ 均无通路” ，则将当前位
置从路径中删除出去。

根据算法思想 , 为了保证在任
何位置上都能沿原路退回 , 需要用一
个后进先出的结构来保存从入口到
当前位置的路径 .
算法描述 : 见书 P51
算法演示

3.2.5 表达式求值
限于二元运算符的表达式定义 :

Exp = S1 OP S2
操作数 : 变量、常量、表达式
运算符 : 算术运算符、关系运算符、
逻辑运算符
界限符：括号、结束符

例： 3 * ( 7 – 2 ) ＃
C C C C C C C C

－

2 ( 7－2
5
7 *
3*5
15
3 ＃

OPND 栈 OPTR 栈

例： 3 * ( 7 – 2 )
OPTR 栈 OPND 栈输入操作
1 # 3*(7–2)# PUSH( OPND, ‘3’ )
2 # 3 *(7–2)# PUSH( OPTR, ‘*’ )
3 #* 3 (7–2)# PUSH( OPTR, ‘(’ )
4 #*( 3 7–2)# PUSH( OPND, ‘7’ )
5 #*( 3 7 –2)# PUSH( OPTR, ‘–’ )
6 # * (– 3 7 2)# PHSH( OPND, ‘2’ )
7 # * (– 3 7 2 )# operate( ‘7’,’-’,’2’ )
8 #*( 3 5 )# POP( OPTR )
9 #* 3 5 # operate( ‘3’, ‘*’, ‘5’ )
10 # 15 # return GetTop( OPND )

OperandType EvaluateExpression() {
// 设 OPTR 和 OPND 分别为运算符栈和运算数栈， OP 为运算符集合。

InitStack (OPTR); Push (OPTR, '#');
initStack (OPND); c = getchar();
while (c!= '#' || GetTop(OPTR)!= '#') {
if (!In(c, OP)) { Push((OPND, c); c = getchar(); }
// 不是运算符则进栈
else
……
} // while
return GetTop(OPND);
} // EvaluateExpression

switch ( precede(GetTop(OPTR), c) {
case '<': // 栈顶元素优先权低
Push(OPTR, c); c = getchar();
break;
case '=': // 脱括号并接收下一字符
Pop(OPTR, x); c = getchar();
break;
case '> ': // 退栈并将运算结果入栈
Pop(OPTR, theta);
Pop(OPND, b); Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
} // switch

§3.3 栈与递归的实现
3.4.1 递归函数
3.4.2 Hanoi 塔问题

递归函数
一个直接调用自己或通过
一系列的调用语句间接调用自己的
函数 , 称为递归函数 .( 见书 P54)
1. 阶乘函数
3. 2 阶 Fibonacci 数列
4. Ackerman 函数

Hanoi 塔问题
问题本身没有明显的递归结构 ,
但递归求解比迭代求解更简单 .
问题描述 : 见 P55 例 3-2
解决方案 : 将 n-1 个圆盘从一个塔座
移至另一个塔座的问题是一个和原问
题具有相同特征属性的问题 , 只是问题
规模小 1. 采用递归的求解思路 .

Hanoi 塔问题
求解 n 阶 Hanoi 塔问题的 C 函数 .
见书 P55 算法 3.5
调用函数和被调用函数之间及
信息交换需要通过栈来进行 .( 见 P55)

Hanoi 塔问题
一个递归函数的运行过程类似于
多个函数的嵌套调用 , 只是调用函数
和被调用函数是同一个函数 , 因此和
每次调用相关的一个重要概念是递归
函数运行的“ 层次 ” 。 P55-P56
Hanoi 塔的递归函数运行示意 P57 图
3.7

§3.4 队列
3.4.1 队列的类型定义
3.4.2 链队列
3.4.3 循环队列

3.4.1 队列的类型定义
?队列是限定只能在表的一端进行插入，
在表的另一端进行删除的线性表。
出
a1 a2 a3…………………….an 入队
队
front rear
队列 Q=(a1,a2,……,an)
?队尾 (rear)—— 允许插入的一端
?队头 (front)—— 允许删除的一端
?队列特点：先进先出 ( F IF O )

?队列的类型定义
ADT Queue {
数据对象：
D ＝ {ai | ai∈ ElemSet, i=1,2,...,n, n≥0}
数据关系：
R1 ＝ { <a i-1,ai > | ai-1, ai ∈ D, i=2,...,n}
约定其中 a1 端为队列头， an 端为队列尾
基本操作：
} ADT Queue

队列的基本操作：
InitQueue(&Q) DestroyQueue(&Q)
QueueEmpty(Q) QueueLength(Q)
GetHead(Q, &e) ClearQueue(&Q)
EnQueue(&Q, e) DeQueue(&Q, &e)
QueueTravers(Q, visit())

3.4.2 链队列－队列的链式表示和
实现
typedef struct QNode{// 结点类型
QElemType data ;
struct QNode *next ;
}QNode, *QueuePtr;
typedef struct{ // 链队列类型
QueuePtr front ; // 队头指针
QueuePtr rear ; // 队尾指针
} LinkQueue;

Q.front a1 … an ∧

Q.rear

Q.front
空队 ∧
Q.rear
列

空
队 ^
front rear
x 入队 x ^ Q.rear -> next=p
front rear Q.rear=p
y 入队 x y ^
front rear
x 出队 x y ^
front rear
y 出队 ^ p= Q.front -> next
Q.front -> next = p -> next
front ear
r

Status InitQueue (LinkQueue &Q) {
// 构造一个空队列 Q
Q.front = Q.rear =
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit (OVERFLOW);
// 存储分配失败
Q.front->next = NULL;
return OK;
}

Status EnQueue (LinkQueue &Q,
QElemType e) {
// 插入元素 e 为 Q 的新的队尾元素
p = (QueuePtr) malloc (sizeof (QNode));
if (!p) exit (OVERFLOW); // 存储分配失败
p->data = e; p->next = NULL;
Q.rear->next = p; Q.rear = p;
return OK;
}

Status DeQueue (LinkQueue &Q,
QElemType &e) {
// 若队列不空，则删除 Q 的队头元素，
// 用 e 返回其值，并返回 OK ；否则返回
ERROR
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;

3.4.3 循环队列－队列的顺序表示和实
现
#define MAXQSIZE 100 // 最大队列长度
typedef struct {
QElemType *base; // 动态分配存储空间
int front; // 头指针，若队列不空，
// 指向队列头元素
int rear; // 尾指针，若队列不空，指向
// 队列尾元素的下一个位置
} SqQueue;

?实现：用一维数组实现 sq[M]
rear
5 5 5 J6 5
4 4 4 J5 4
rear rear J4
3 3 3 3
rear
2 J3 2 front J3 2 front 2
rear front J2
1 J2 1 front 1 1
rear=0 rear
0 front J1 0 front J1 0 0
front=0 J4,J5,J6 入
空队列 J1,J1,J3 入队 J1,J2,J3 出队队

?存在问题：
?当 front=0,rear=M 时再有元素入队发生溢出 — — 真
溢出
?当 front≠0,rear=M 时再有元素入队发生溢出 — — 假

?解决方案
?队首固定，每次出队剩余元素向下移动 — —
浪费时间
?循环队列
? 基本思想：把队列设想成环形，让
sq[0] 接在 sq[M-1] 之后，若
rear+1==M, 则令 rear=0;
?实现：利用“ 模” 运算
?入队： base[rear]=x;
rear=(rear+1)%M;
?出队： x=base[front];
front=(front+1)%M;
?队满、队空判定条件

front
队空： fro nt==re a r rear
队满： fro nt==re a r
4 5 0
3
2 1
rear
J6
J5 4 5 0
3 J4,J5 ,J6 出队 J6
2 1
J4 J7,J8
,J9 入 J5 4 5 0 J7
front
队 3 2 1 J8
J4
初始状态 front J9
解决方案： rear
1. 另外设一个标志位以区别队空、队满
2. 少用一个元素空间：
队空： front==rear 队满：
(rear+1)%M==front
3. 使用一个计数器记录队列中元素的总数

Status InitQueue (SqQueue &Q) {
// 构造一个空队列 Q
Q.base = (QElemType *) malloc
(MAXQSIZE *sizeof (QElemType));
if (!Q.base) exit (OVERFLOW);
// 存储分配失败
Q.front = Q.rear = 0;
return OK;
}

Status EnQueue (SqQueue &Q, QElemType
e) { // 插入元素 e 为 Q 的新的队尾元素
if ((Q.rear+1) % MAXQSIZE == Q.front)
return ERROR; // 队列满
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}

Status DeQueue (SqQueue &Q, QElemType &e)
{ // 若队列不空，则删除 Q 的队头元素，
// 用 e 返回其值，并返回 OK; 否则返回 ERROR
if (Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1) % MAXQSIZE;
return OK;
}

第三章作业
3.1 设将整数 1 、 2 、 3 、 4 依次进栈，但只要
出栈时栈非空，则可将出栈操作按任何次序夹
入其中，请回答下列问题：
（ 1 ）若入栈次序为
push(1) ， pop() ， push(2 ）， push(3) ， pop()
， pop( ) ， push(4) ， pop( ) ，则出栈的数字序
列为什么？
3.2 写出检验括号匹配的算法。

3.3 写出以下程序段的输出结果（队列中的元素
类型 QElemType 为 char ）。
Void main( ){
Queue Q; InitQueue(Q);
Char x=‘e’, y=‘c’;
EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y);
DeQueue(Q, x); EnQueue(Q, x);
DeQueue(Q, x); EnQueue(Q, ‘a’);
While ( !QueueEmpty(Q) ){
DeQueue(Q, y);
Printf(y);
}
Printf(x);
}

狠狠撸

第三章栈和队列

Recommended

More Related Content

What's hot (20)

Viewers also liked (18)

Similar to 第三章栈和队列 (20)

第三章栈和队列

狠狠撸

第三章 栈和队列

Recommended

More Related Content

What's hot (20)

Viewers also liked (18)

Similar to 第三章 栈和队列 (20)

第三章 栈和队列

第三章栈和队列

Similar to 第三章栈和队列 (20)

第三章栈和队列