第 4章 栈和队列引例
1,餐馆中一叠一叠的盘子,如果它们是按 1,2,…,n 的次序往上叠的，那么使用时候的次序应是什么样的？
必然是 依从上往下 的次序，即 n,…,2,1。它们遵循的是 "后进先出 "的规律，这正是本章要讨论的 "栈 "的结构特点。
是 "排队 "。在计算机程序中，模拟排队的数据结构是 "队列 "。
栈和队列是两种特殊的线性表,是 操作受限 的线性表,
称 限定性数据结构 。
2,在日常生活中，为了维持正常的社会 秩序 而出现的常见 现象 是什么？
4.1 栈
4.2 栈的应用举例
4.3 队列
4.4 队列应用举例
【 学习目标 】
1.掌握 栈 和 队列 这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2.熟练掌握栈类型的两种实现方法。
3.熟练掌握 循环队列 和 链队列 的 基本操作实现算法。
4.理解递归算法执行过程中栈的状态变化过程。
【 重点和难点 】
栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。
重点,栈和队列的基本特征，表示与实现难点,递归、循环队列算法,栈和队列的实现及其应用顺序栈、链栈、递归、循环队列、链队列
【 知识点 】
【 学习指南 】
本章主要是学习如何在求解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，
如 栈满和栈空、队满和队空的条件以及它们的描述方法。
本章要求必须完成的算法设计题为：
4.1,4.2,4.3,4.4,4.5,4.6,4.9,4.11,4.12
4.1 栈是限定仅 在表尾进行插入或删除 操作的 线性表。
允许插入,删除的一端称为 栈顶 (top),另一端称为 栈底 (bottom)
top
bottom
进栈出栈
an
.
.
.
.
a1
基本操作：
后进先出 (LIFO)
定义,栈 ─ 特殊的线性表,操作受限的线性表逻辑特征：
创建一个空栈；
判断栈是否为空栈；
判断栈是否为满；
往栈中插入 (或称推入 )一个元素；
从栈中删除 (或称弹出 )一个元素；
求栈顶元素的值。
访问栈中每个元素栈和队列是两种常用的数据类型栈和队列是限定插入和删除只能在表的,端点,进行的线性表。
线性表 栈 队列
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
一般线性表 堆栈逻辑结构,一对一 逻辑结构,一对一存储结构,顺序表、链表 存储结构,顺序栈、链栈运算规则,随机存取 运算规则,后进先出 (LIFO)
1,定义与线性表相同,仍为一对一关系。
用 顺序栈 或 链栈 存储均可,顺序栈更常见只能在 栈顶 运算,且访问结点时依照后进先出 (LIFO)或先进后出 (FILO)的原则。
关键是编写 入栈 和 出栈 函数，具体实现依顺序栈或链栈的不同而不同。
基本操作有 入栈,出栈,读栈顶元素值,建栈,
判栈满,判 栈空 等。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构限定只能在 表的一端 进行插入和删除运算的 线性表 (只能在栈顶操作 )
4.1.1 栈的特点和操作例如,栈 s = ( a1,a2,a3,……,an-1,an )
an 称为栈顶元素插入元素到 栈顶 (即表尾 )的操作，称为 入栈 。
从 栈顶 (即表尾 )删除最后一个元素的操作，称为 出栈 。
强调,插入和删除都只能在表的一端（栈顶）进行！
a1 称为栈底元素栈是仅在 表尾 进行插入、删除操作的线性表。
表尾 (即 an 端 )称为 栈顶 top ; 表头 (即 a1 端 )称为 栈底 base
“进,＝压入 =PUSH（ x)
“出,＝弹出 =POP ( y )
4.1.1 栈的特点和操作栈的基本操作
InitStack(&S)
操作结果,构造一个空栈 S。
DestroyStack(&S)
初始条件,S已存在。 操作结果,栈 S被销毁。
ClearStack(&S)
初始条件,S已存在。 操作结果,将 S清为空栈。
StackEmpty(S)
初始条件,S已存在。 操作结果,若栈 S为空栈，则返回 TRUE，否则 FALE。
StackLength(S)
初始条件,S已存在。 操作结果,返回 S的元素个数，即栈的长度。
GetTop(S,&e)
初始条件,S已存在且非空。 操作结果,用 e返回 S的栈顶元素。
Push(&S,e)
初始条件,S已存在。 操作结果,插入元素 e为新的栈顶元素。
Pop(&S,&e)
初始条件,S已存在且非空。 操作结果,删除 S的栈顶元素,并用 e返回其值。
StackTraverse(S)
初始条件,S已存在且非空。 操作结果,从底到顶依次输出 S中的元素。
ana1 a2 … …
GetTop(S,&e)
初始条件,栈 S 已存在且非空。
操作结果,用 e 返回 S 的栈顶元素。
e
Push(&S,e)
初始条件,栈 S 已存在。
操作结果,插入元素 e 为新的栈顶元素。
Pop(&S,&e)
初始条件,栈 S 已存在且非空。
操作结果,删除 S 的栈顶元素，并用 e 返回其值。
图示栈的三种常用基本操作
ana1 a2 … …
an-1a1 a2 … … an-
4.1.2 栈的表示和操作实现
1、顺序栈
2、链 栈顺序栈的存储结构实现：一维数组 s[M]
top=0
1
2
3
4
5
0
栈空栈顶指针 top,指向实际栈顶后的空位臵，初值为 0
top 1
2
3
4
5
0
进栈
A
top
出栈栈满
B
C
D
E
F
top
top
top
top
top
1
2
3
4
5
0A
B
C
D
E
Ftop
top
top
top
top
top
栈空设数组维数为 M
top=0,栈空,此时出栈，则 下溢 （ underflow)
top=M,栈满,此时入栈，则 上溢 （ overflow)
1、栈的表示与实现 ──顺序栈
1、栈 的表示与实现 ──顺序栈顺序栈基本操作的实现：
– 栈顶的初始化,S.top = S.base
– 栈空,S.base == S.top
– 栈满,S.top - S.base >= S.stacksize
– 入栈,*S.top ++ = e，出栈,e = *--S.top
base
空栈 a 进栈 b 进栈
atop base
top
base
top
a
b
约定,top指向栈顶元素的下一个位置
a1
a2
……
an
顺序栈 S
ai
……
表和栈的操作区别 —— 对线性表 s = ( a1,a2,….,an-1,an )
表头表尾栈底 base
栈顶 top
低地址高地址写入,v[i]= ai
读出,x= v[i]
压入,PUSH (an+1)
弹出,POP (x)
前提：一定要 预设 栈顶指针 top！
低地址高地址
v[i]
a1
a2
ai
an
……
顺序表 V[n]
……
an+1
入栈操作,
例如用堆栈存放 (A,B,C,D)(注意要遵循,后进先出,原则 )
A A
C
B
A
B
Atop
核心语句：
top=L; 顺序栈中的 PUSH函数status Push( ElemType x )
{
if ( top>M ) { 上溢 }
else v[top++] = x;
}
Push( B );
Push( C );
Push( D );
top
top
top
top
低地址 L
Push( A );
高地址 M
B
C
D
出栈操作,例如从栈中取出 ‘ B’（注意要遵循,后进先出,原则）
D
C
B
A top
top
D
C
A
B
D
C
B
A
topD
C
B
A
top
低地址 L
高地址 M
核心语句：
Pop ( );
Pop ( );
Printf( Pop () );
顺序栈中的 POP函数
status Pop( )
{
if ( top=L ) { 下溢 }
else {
y = v[--top];
return( y );
}
}
若入栈动作使地址向高端增长,称为,向上生成,的栈；
若入栈动作使地址向低端增长,称为,向下生成,的栈；
对于向上生成的栈入栈 口诀,堆栈指针 top先压后加 （ v[top++]=x） ；
出栈 口诀,堆栈指针 top先减后弹 （ y=v[--top]) 。
栈不存在的条件,base=NULL;
栈为空 的条件,base=top;
栈满的条件,top-base=stacksize;
问,为什么要设计堆栈？它有什么独特用途？
1,调用函数或子程序非它莫属；
2,递归运算的有力工具；
3,用于保护现场和恢复现场；
4,简化了程序设计的问题。
答：
问,栈是什么？ 它与一般线性表有什么不同？
答,栈是一种特殊的线性表,它只能在 表的一端 (即栈顶 )进行插入和删除运算。
与一般线性表的区别,仅在于 运算规则 不同。
例 对于一个栈,给出输入项 A,B,C,如果输入项序列由 ABC组成，
试给出所有可能的输出序列。
A进 A出 B进 B出 C进 C出 ABC
A进 A出 B进 C进 C出 B出 ACB
A进 B进 B出 A出 C进 C出 BAC
A进 B进 B出 C进 C出 A出 BCA
A进 B进 C进 C出 B出 A出 CBA
不可能产生输出序列 CAB
例 一个栈的输入序列是 12345，若在入栈的过程中允许出栈，则栈的输出序列 43512可能实现吗？ 12345的输出呢？
43512不可能实现,主要是其中的 12顺序不能实现；
12345的输出可以实现，只需压入一个立即弹出一个即可。
435612中到了 12顺序不能实现；
135426可以实现。
例 如果一个栈的输入序列为 123456，能否得到 435612和 135426的出栈序列？
答：
答：
例,设依次进入一个栈的元素序列为 c,a,b,d,则可得到出栈的元素序列是：
Ａ） a,b,c,d Ｂ） c,d,a,b Ｃ） b,c,d,a Ｄ） a,c,d,b
A,D可以 ( B,C不行 )。
讨论,有无通用的判别原则？
有。 在可能的输出序列中，不存在这样的输入序列 i,j,k，能同时满足 i<j<k 和 Pj<Pk<Pi
答：
SqStack,结构类型名；
SqStack,它的三个域分别是：
elem,栈底指针，指向栈底位置；
top,栈顶指针；
Stacksize,已分配的存储空间 (一元素为单位 )大小；
const STACK_INIT_SIZE 100
const STACKINCREMENT 10
typedef struct {
SElemType *elem;
int top //栈顶指针
int stacksize;
int increment;
} SqStack;
顺序栈算法约定栈顶指针指向栈顶元素的下 (后面 )一个位置
elem
top
stacksize
increment
0
0
0
a1
a2
an-2
an-1
an
...
...
elem
top
stacksize
increment
0
0
0
void InitStack_Sq(SqStack &S,
int maxsize=STACK_INIT_SIZE,
int incresize = SRACKINCREMENTSIZE )
{
S.base= new SElemType[STACK_INIT_SIZE];
S.top = 0;
S.stacksize = maxsize;
S.incrementsize = incresize;
} //InitStack_Sq
1) 初始化操作 InitStack_Sq((SqStack &S)
参数,S是存放栈的结构变量；
功能,建一个空栈 S；
a1
a2
an-2
an-1
an
...
...100
0
10
顺序栈算法
const STACK_INIT_SIZE 100
const STACKINCREMENT 10
void DetroyStack_Sq ( SqStack &S)
{
If ( !S.elem) return ERROR;
delete S.elem;
S.top = 0;
S.stacksize = 0;
S.increment = 0;
}
2) 销毁栈操作 DestroyStack_Sq(SqStack &S )
功能,销毁一个已存在的栈 ;
elem
top
stacksize
increment
20
100
10
a1
a2
an-2
an-1
an
...
...
0
0
0
null
顺序栈算法
3) 置空栈操作 ClearStack_Sq(SqStack &S)
功能,将栈 S置为空栈
void ClearStack_Sq ( SqStack &S)
{
If ( !S.elem ) return ERROR;
S.top = 0;
}
elem
top
stacksize
increment
20
100
10
a1
a2
an-2
an-1
an
...
...
0
顺序栈算法
bool GetTop_Sq(SqStack S,SelemType &e)
{
if ( S.top == 0 ) return FALSE;
e = S.elem[S.top-1];
return TRUE;
}
4) 取栈顶元素操作 GetTop_Sq(SqStack S,SElemType &e)
功能,取栈顶元素，并用 e返回 ;
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e iai
void Push( SqStack &S,SElemType e )
{
if ( S.top>=S.stacksize)
incrementStackSize( S );
S.elem[S.top++] = e;
}
1) S是否已满,若 栈 满，重新分配存储空间；
2) 将元素 e 写入栈顶；
3) 修改栈顶指针,使栈顶指针指向栈顶元素的下 (后面 )一个位臵；
6) 入栈操作 Push(SqStack &S,SElemType e )
功能：将 e入栈 ;
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e x
i+1
x
6) 出 栈操作 Pop(SqStack &S,SElemType &e )
功能,栈顶元素退栈，并用 e 返回 ;
bool Pop_Sq( SqStack &S,SElemType &e)
{
if ( S.top== 0) return FALSE;
e = S.elem[--S.top];
return TRUE;
}//Pop
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e iai
-1
约定,top指向栈顶元素所在的结点
链栈
– 无栈满问题 (除非分配不出内存 ),空间可扩充
– 栈顶 ----链表的表头
– 可以不必引入头结点
^top
栈顶指针 ∧a1an
注意,链栈中指针的方向
an-1
栈底元素
N
2、栈的表示与实现 ── 链栈
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作链栈栈顶
^…top data next
栈底结点定义,
–入栈算法
–出栈算法
typedef struct node
{ int data;
struct node *next;
} Node;
typedef LinkList LinkStack;
^…...
栈底
toptop
xp
^…...
栈底
top
q
链栈的定义
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int Data;
typedef struct node {
ElemType data;
struct node *next;
} LNode;
Typedef LinkList LinkStack
初始化
void InitStack_L( LinkStack *S )
{
S = NULL;
}
入栈
void Push_L ( LinkStack *S,ElemType e )
{
LNode *p = new LNode ;
p->data = e;
p->next = S;
S = p;
}
顺序栈算法
–入栈算法
^…...
栈底toptop
xp
判栈空
bool StackEmpty_L( LinkStack *S )
{
return !S;
}
出栈
bool Pop_L( LinkStack *S,ElemType *e )
{
if ( S ) {
LNode *p = S;
S = S->next;
*e = p->data;
delete p;
return TRUE;
}
else return FALSE;
}
取栈顶
bool GetTop_L( LinkStack *S,ElemType *e )
{
if ( !S ) return 0;
else {
*e = S->data;
return 1;
}
}
臵栈空
int MakeEmpty_L( LinkStack *S )
{ Lnode *p;
while( S )
{
p = S; S = S->next;
delete p;
}
}
链栈算法
–出栈算法
^…...
栈底
top
q
X
3.2 栈的应用举例例一,数制转换例二,括号匹配的检验例三,背包问题求解例四,表达式求值例五,实现递归例如,（ 1348)10 = (2504)8,其运算过程如下：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
计算顺序输出顺序算法基于原理,N = (N div d)× d + N mod d
例一 数制转换
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
假设在表达式中,（［］（））或［（［ ］［ ］）］ 等为正确的格式，［（ ］）或（［（ ））或 ( ( ) ] ) 均为不正确的格式。
检验括号是否匹配 的方法可用,期待的急迫程度” 来描述。
例二 括号匹配的检验例如,考虑下列括号序列,
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的 不匹配 的情况,
算法的设计思想
1）凡出现 左括弧,则 进栈 ；
2）凡出现 右括弧,首先检查栈是否空,若 栈空,则表明该,右括弧,多余,否则 和栈顶元素 比较，若 相匹配,则,左括弧出栈,
否则表明 不匹配
3）表达式检验结束时，若栈空，则表明表达式中 匹配正确否则表明,左括弧,有余
bool matching(string exp[] )
{
int state = 1; ch = *exp++；
while ( ch !=?#? && state ) {
switch ( ch ) {
case?(?,
case?[?,{ Push(S,ch ); break; }
case?)?,{
if ( !StackEmpty(S) && GetTop(S) =?(? ) Pop(S,e);
else state = 0;
break;
}
case?]?,{
if ( !StackEmpty(S) && GetTop(S) =?[? ) Pop(S,e);
else state = 0;
break;
}
} //switch
ch = *exp++;
} //while
if (StackEmpty(S) && state) return TRUE;
else return FALSE;
}
设有一个背包可以放入的物品的重量为 s,现有 n件物品,重量分别为 w[1],w[2],…,w[n]。 问能否从这 n件物品中选择若干件放入此背包中,使得放入的重量之和正好为 s。 如果存在一种符合上述要求的选择,则称此背包问题有解 (或称其解为真 )；否则称此背包问题无解 (或称其解为假 )。
例三 背包问题一个背包可以放入的物品重量为 s,现有 n件物品,重量分别为 w1,w2,…,wn,问能否从这些物品中选若干件放入背包中,
使得放入的重量之和正好是 s。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解。
例三 背包问题如果有解：
1,选择的一组物品中不包含 wn;
knap( s,n-1 ) 的解就是 knap( s,n)的解；
2,选择的一组物品中包含 wn;
knap( s-wn,n -1 )的解就是 knap( s,n)的解,
背包问题表示,int knap( int s,int n ) 其中,s>=0,n>=1
top
8 4
3 5 2
S
1
背包容积 T=10
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
k=0
0 1 2
3 4 5
k
背包问题求解
T=10
S
top 1->8
4
3 5 2
0->1
背包容积 T=1
k=2 放不进去
0 1 2
3 4 5
3 放不进去4 放不进去K=0,1进栈,k=3,4,5 放不进去,k=6
注意内循环条件 while (T >0 && k < n )
k=1(体积 8)必须出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=1
0 1 2
3 4 5
k=2,3进栈外循环条件 while (!(StackEmpty(S) && k == n));
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
2,3进栈 k=4 放不下
0 1 2
3 4 5
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
55->2
0->1
背包容积 T=0
k=5
进栈
0 1 2
3 4 5
if (T == 0 ) StackTraverse(S,w);条件满足输出一组解
k=6 注意内循环条件栈顶元素出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
k=5
0 1 2
3 4 5
栈不空继续找解 (注意外循环条件 )
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
k=6
0 1 2
3 4 5
T不等于 0,不输出,栈顶出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=3
0 1 2
3 4 5
k=4 继续入栈
k=4
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3
4->5
2
0->1
背包容积 T=0
k=4
0 1 2
3 4 5
T=0 又找到一组解
k=5
栈顶元素出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=4
0 1 2
3 4 5
K=5 进栈,继续找解
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5
5->2
0->1
背包容积 T=3
k=5
0 1 2
3 4 5
T不为 0 继续找解,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=5
0 1 2
3 4 5
栈不空继续找解 (外循环 )
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=6
0 1 2
3 4 5
不满足内循环条件,T<>0,出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=2
0 1 2
3 4 5
继续找解
k=3
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
4->5
2
0->1
背包容积 T=1
k=3
进栈
0 1 2
3 4 5
脱离内循环,必须出栈,继续找解
k=4
进栈
k=5
不进栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5 2
0->1
背包容积 T=6
k=4
0 1 2
3 4 5
k=4栈顶出栈后,k=5进栈继续找解
k=5(进栈 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5
5->2
0->1
背包容积 T=4
k=5
0 1 2
3 4 5
T不为 0不输出,栈顶出栈
k=6脱离内循环物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5 2
0->1
背包容积 T=6
k=5出栈
0 1 2
3 4 5
外循环条件,栈不空继续找解
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=3出栈
0 1 2
3 4 5
不进入内循环,栈顶出栈,继续找解
k=4
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3
4->5
5->2
0->1
背包容积 T=2
k=4进栈
0 1 2
3 4 5
T不为 0不输出,栈顶出栈
k=5进栈 k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3
4->5
5->2
0->1
背包容积 T=4
k=5出栈后
0 1 2
3 4 5
栈不空继续找解,k=6不进入内循环
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=4出栈
0 1 2
3 4 5
继续找解
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5
5->2
0->1
背包容积 T=7
k=5进栈
0 1 2
3 4 5
T不为 0不输出,不进入内循环,出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=5出栈后
0 1 2
3 4 5
栈不空继续找解,不进入内循环
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
Stop
8 4
3 5 2
1
背包容积 T=10
k=0出栈后
0 1 2
3 4 5
栈空了，但 k<>n继续找解,进入内循环
k=1
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top 1->8
4
3 5 2
1
背包容积 T=2
k=2
不进栈
0 1 2
3 4 5
继续找解
k=3
不进栈
k=4
不进栈
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
1->8
4
3 5
5->2
1
背包容积 T=0
k=5进栈
0 1 2
3 4 5
找到一组解,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top 1->8
4
3 5 2
1
背包容积 T=0
k=5出栈
0 1 2
3 4 5
栈不空继续找解,不进入内循环,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
Stop
8 4
3 5 2
1
背包容积 T=10
k=1出栈后
0 1 2
3 4 5
栈空了，但 k<>n继续找解,进入内循环
k=2(下面该它进栈了 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
继续找解继续找解
… … … …
吐血！！！！
S
top
8 4
3 5
5->2
1
背包容积 T=2
快完了 k=5进栈
0 1 2
3 4 5
脱离内循环,栈顶出栈
k=6(脱离内循环 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
背包问题求解
top
8 4
3 5 2
1
背包容积 T=10
k=5
0 1 2
3 4 5
终于！栈空了,k==n了，呜呼哀哉！
没有计算机是多么痛苦并快乐的事！
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6T=10
1
( )
[ 3 8,3 2 ]
{ 0,0 }
2
( 0 )
[ 3 2,2 2 ]
{ 0,0 }
4
( 0 0 )
{ 0,0 }
5
( 0 1 )
{ 4,1 0 }
8
( 0 0 0? )
{ 0,0 }
1 6
( 0 0 0 0 )
{ 0,0 }
9
( 0 0 1? )
{ 6,1 2 }
1 7
( 0 0 0 1 )
{ 9,1 8 }
1 8
( 0 0 1 0 )
{ 6,1 2 }
1 9
( 0 0 1 1 )
{ 1 5,3 0 }
1 0
( 0 1 0? )
{ 4,1 0 }
2 0
( 0 1 0 0 )
{ 4,1 0 }
1 1
( 0 1 1? )
{ 1 0,2 2 }
2 1
( 0 1 0 1 )
{ 1 3,2 8 }
2 2
( 0 1 1 0 )
{ 1 0,2 2 }
2 3
( 0 1 1 1 )
{ 1 9,4 0 }
3
( 1 )
[ 3 8,3 2 ]
{ 2,1 0 }
6
( 1 0 )
{ 2,1 0 }
7
( 1 1 )
{ 6,2 0 }
1 2
( 1 0 0? )
{ 2,1 0 }
2 4
( 1 0 0 0 )
{ 2,1 0 }
1 3
( 1 0 1? )
{ 8,2 2 }
2 5
( 1 0 0 1 )
{ 1 1,2 8 }
2 6
( 1 0 1 0 )
{ 8,2 2 }
2 7
( 1 0 1 1 )
{ 1 7,4 0 }
1 4
( 1 1 0? )
{ 6,2 0 }
2 8
( 1 1 0 0 )
{ 6,2 0 }
1 5
( 1 1 1? )
{ 1 2,3 2 }
2 9
( 1 1 0 1 )
{ 1 5,3 8 }
2 0
( 1 1 1 0 )
{ 1 2,3 2 }
3 1
( 1 1 1 1 )
{ 2 1,5 0 }
★
[ 3 6,2 2 ] [ 3 8,3 2 ]
[ 3 8,3 2 ][ 3 8,3 8 ]
n = 4,m = 1 5
w = { 2,4,6,9 }
p = { 1 0,1 0,1 2,1 8 }
( x
1
x
2
x
3
x
4
)
{ w x,p x }
[ U,L ]
[ 2 0,2 0 ] [ 3 8,3 8 ]
递归定义
1,0)1,(
1,0)1,(
0,00
00
01
),(
nsnwsk n a p
nsnsk n a p
ns
s
s
nsK n a p
n
int knap( int s,int n )
{
if ( s==0 ) return 1;
else if ( s<0 || s>0 && n<1 ) return 0;
else if ( knap(s-w[n-1],n-1) == 1 )
{
printf(“n=%d,w[%d]=%d \n”,n,n-1,w[n-1]);
return 1;
}
else return (knap( s,n-1 ) );
}
非递归程序
struct NodeBag {
int s,n ;
int r ; /* r的值为 1,2,3 */
int k;
};
typedef struct NodeBag DataType;
PSeqStack st;
struct NodeBag x;
void knapsack( int w[],int T,int n )
{
InitStack(S); k = 0;
do {
while( T>0 && k<n ) {
if ( T-w[k]>=0 ) {
Push( S,k );
T -= w[k];
}
k++;
}
if ( T==0 ) StackTraverse( S );
Pop( S,k );
T += w[k];
k++;
} while ( StackEmpty(S) && k==n );
}
限于二元运算符的表达式定义,
表达式,:= (操作数 ) (运算符 ) (操作数 )
操作数,:= 简单变量 | 表达式简单变量,,= 标识符 | 无符号整数例四 表达式求值表达式的三种标识方法：
设 Exp = S1 OP S2
则称 OP S1 S2 为 前缀表示法
S1 S2 OP 为 后缀表示法
S1 OP S2 为 中缀表示法例如,Exp = a? b + (c? d / e)? f
前缀式,+? a b c / d e f
中缀式,a? b + c? d / e? f
后缀式,a b? c d e /? f? +
结论,
1) 操作数之间的相对次序不变 ;
2) 运算符的相对次序不同 ;
3) 中缀式丢失了括弧信息,致使运算的次序不确定 ;
4) 前缀式的运算规则为,连续出现的两个操作数和在它们前且紧靠它们的运算符构成一个最小表达式 ;
5) 后缀式的运算规则为,运算符在式中出现的顺序恰为表达式的运算顺序 ;
每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式 ;
如何从后缀式求值？
先找运算符，再找操作数例如：
a b? c d e /? f? +
a?b d/e
c-d/e
(c-d/e)?f
如何从原表达式求得后缀式？
每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。
分析,原表达式” 和,后缀式”中的运算符,
原表达式,a + b? c? d / e? f
后缀式,a b c? + d e / f
从原表达式求得后缀式的规律为：
1) 设立暂存 运算符 的 栈 ;
2) 设表达式的结束符为,#”,予设 运算符栈的 栈底为,#”
3) 若 当前字符 是操作数,则 直接发送给后缀式 ;
4) 若 当前 运算符的 优先数高 于栈顶运算符，则 进栈 ;
5) 否则，退出栈顶运算符发送给后缀式 ;
6),(” 对它之前后的运算符 起隔离作用,,)”可视为自相应左括弧开始的表达式的结束符。
算法思想
设定两栈,操作符栈 OPTR,操作数栈 OPND
栈初始化,设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘ #?；
依次读入字符,是操作数则入 OPND栈，是操作符则要判断：
if 操作符 < 栈顶元素,则退栈、计算，结果压入 OPND栈；
操作符 = 栈顶元素且不为‘ #?，脱括号（弹出左括号）；
操作符 > 栈顶元素,压入 OPTR栈。
表达式求值中缀表达式 后缀表达式（ RPN)
a*b+c ab*c+
a+b*c abc*+
a+(b*c+d)/e abc*d+e/+
中缀表达式,操作数栈和运算符栈例 计算 2+4-3*6
操作数 运算符
2
4
+
操作数 运算符
6 -
操作数 运算符
6 -
3
6
*
操作数 运算符
6 -
18
操作数 运算符
-12
中缀表达式求值举例
OPTR OPND INPUT OPERATE
3*(7-2)# Push(opnd,’3’)#
*(7-2)#3# Push(optr,’*’)
#,* 3 (7-2)# Push(optr,’(’)
#,*,( 3 7-2)# Push(opnd,’7’)
#,*,( 3,7 -2)# Push(optr,’-’)
#,*,(,－ 3,7 2)# Push(opnd,’2’)
#,*,(,－ 3,7,2 )# Operate(7-2)
#,*,( 3,5 )# Pop(optr)
#,* 3,5 # Operate(3*5)
# 15 # GetTop(opnd)
表达式求值示意图,5+6?(1+2)-4
top
base
OPTR栈
#
OPND栈
top
base
toptop +
top top×
top (
top
top
+
top
toptop
top
top-top
5读入表达式过程,+6× (1+2)-4 #
=19
1+2=3
6× 3=18
5+18=23
23-4=19
6
1
2
3
184
52319
中缀表达式求值后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转 4
3、若是运算符，从栈中弹出 2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转 1
top
4
top
4
3
top
7
3
5
top
例 计算 4+3*5 后缀表达式,435*+
top
4
15 top
19
后缀表达式求值
double evalution ( char suffix[] )
{
ch = *suffix++; InitStack( S );
while ( ch !=,#” ) {
if ( !OpMember(ch) ) Push(S,ch);
else {
Pop( S,b ); Pop( S,a );
Push( S,Operate( a,ch,b ) );
}
ch = *suffix++;
}
Pop( S,result );
return result;
}
运算符 # ( + - ) * / |(乘幂 )
优先级 -1 0 1 1 2 2 2 3
void transform( char suffix[ ],char exp[ ] )
{
InitStack(S); Push(S,?#?);
p = exp; ch = *p; k=0;
while (!StackEmpty(S)) {
if (!OpMember(ch)) Suffix[k++] = ch;
else { }
if ( ch!=?#?) ch = *++p;
} // while
suffix[k] =?\0?;
}
… … switch (ch) {case?(?,Push(S,ch); break;
case?)?,Pop(S,c);
while (c!=?(?) { suffix[k++] = c; Pop(S,c); }
break;
defult,while( Gettop(S,c) && ( precede(c,ch)) )
{ suffix[k++] = c; Pop(S,c); }
if ( ch!=?#?) Push( S,ch);
break;
} // switch
递归的定义例 5 实现递归递归的过程,一个过程直接或间接地调用自己如,0的阶乘是 1,n(n>0)的阶乘等于 n乘上 (n-1)的阶乘线性表的另一种定义,
若元素个数为 0，则称为空表
若元素个数大于 0,则有且仅有一个第一个元素 (即表头 ),
剩余 元素形成一个表 (即表尾 ) 。
递归的对象,一个对象部分地包含它自己，或用它自己给自己定义。 (如某些数据结构的定义 )
递归的应用
–递归定义,如阶乘,Fibonacci数列等
–数据结构,如表、树、二叉树等
–问题求解,如 Hanoi塔例 5 实现递归
将所有的实在参数、返回地址等 信息 传递给被调用函数 保存 ;
为被调用函数的局部变量 分配存储区 ;
将 控制转移 到被调用函数的入口。
当在一个函数的运行期间 调用另一个函数 时，在 运行该被调用函数之前,需先完成三项任务：
从被调用函数 返回 调用函数 之前,应该完成三项任务：
保存 被调函数的 计算结果 ;
释放 被调函数的 数据区 ;
依照被调函数保存的返回地址将 控制转移 到调用函数。
多个函数嵌套调用的规则是,
此时的内存管理实行,栈式管理
”
后调用先返回！
例如：
void main( ) { void a( ) { void b( ) {
… … …
a( ); b( );
… …
} //main } // a } // b main的数据区函数 a的数据区函数 b的数据区递归工作栈,递归过程执行过程中占用的数据区。
递归工作记录,每一层的递归参数合成一个记录。
当前活动记录,栈顶记录指示当前层的执行情况。
当前环境指针,递归工作栈的栈顶指针。
递归函数执行过程可视为同一函数进行嵌套调用,例如：
栈的应用 - 过程的嵌套调用
r
主程序
s
rr
r
s
子过程
1 r
s
t
子过程
2 rs
t 子过程
3
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
输出：
(2) 2
(1) 3
输出：
( ) 1
( ) 2
( ) 3
top
输出,
( ) 3
返回
(3) 1
(2) 2
(1) 3
top (4) 0
结束
void print(int w)
{ int i;
if ( w!=0) {
print(w-1);
for(i=1;i<=w;++i) printf(“%3d,”,w);
printf(“/n”);
}
}
运行结果：
1，
2,2，
3,3,3，
栈与递归的实现
定义是递归的
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘函数的递归算法
long fact ( long n )
{
if ( n == 0 ) return 1; //递归结束条件
else return n*fact (n-1); //递归的规则
}
我们看一下 n=3阶乘函数 fact(n)的执行过程
main( ) {
int n=3,y;
L y= fact(n);
}
调用调用调用
int fact (n) {
if（ n=1） return（ 1） ；
else
L1 return (n*fact (n-1))；
}//fact
n=3 int fact (int n) {
if（ n=1） return 1;
else
L1 return（ n*fact (n-1));
}//fact
n=2
int fact(int n) {
if (n=1) return 1；
else
L1 return (n*fact (n-1))；
}//fact
n=1
L 3
L1 1
L1 2
返回 1
返回 2
返回 6
1
ct 1)ct 1)
ct(n)
返回地址 实参注意递归调用中栈的变化栈与递归的实现主程序 main( ),fact(4)
参数传递递归调用结果返回回归求值
fact(4),
fact(3),
fact(2):
fact(1),
fact(0),
1
直接定值为 1
计算 4*fact(3)
计算 3*fact(2)
计算 2*fact(1)
计算 1*fact(0)
1
2
6
24
[例 ] Ackermann函数 A(n,x,y)的计算
x+1 n=0
x n=1,y=0
0 n=2,y=0
A(n,x,y)= 1 n=3,y=0
2 n>=4,y=0
A(n-1,A(n,x,y-1),x) n!=0,y!=0
A(3,1,2)
=A(2,A(3,1,1),1)
=A(2,A(2,A(3,1,0),1),1)
=A(2,A(2,1,1),1)
=A(2,A(1,A(2,1,0),1),1)
=A(2,A(1,0,1),1)
=A(2,A(0,A(1,0,0),0),1)
=A(2,A(0,0,0),1)
=A(2,1,1)
=A(1,A(2,1,0),1)
=A(1,0,1)
=A(0,A(1,0,0),0)
=A(0,0,0)
计算 Ackermann函数 A(n,x,y)的算法思想可以描述如下：
反复执行：
(1) 递归,只要有 n!=0&&y!=0 则反复执行：
计算 A(n,x,y-1); y--; 并将 (n-1,x)作返回信息进栈；
(2) 返回,计算出递归函数 终点值 v ;
若栈空则结束算法,
否则,出栈一组值，作新参数 (n,y)； v赋给 x；
构造出一个新函数 A(n,x,y)，再递归。
定义递归出口，即 n=0或 y=0时的 Ackermann函数,
int Ackerman( int n,int x,int y )
{
InitStack(S);
e.nval = n; e.xval = x; e.yval = y;
Push( S,e );
do {
GetTop( S,e );
while( e.navl!=0 && e.yval!=0 ) {
e.yval--; Push( S,e );
}
Pop( S,e );
u = value(e.nval,e.xval,e.yval);
if ( !StackEmpty(S) ) {
pop( S,e );
e.nval--;
e.yval = e.xval;
e.xval = =u;
Push( S,e );
}
} while ( !StackEmpty(S) );
return u;
}
typedef struct {
int nval; int xval; int yval;
} Elemtype;
int value( int n,int x,int y )
{
if ( n==0 ) return ( x+1 );
else switch( n ) {
case 1,return x;
case 2,return 0;
case 3,return 1;
default,return 2;
}
}
5.3 队列 ( Queue )
定义队列是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性先进先出 (FIFO,First In First Out)
常用操作 初始化空队、入队、出队、判断队空、
判断队满、取队头
a0 a1 a2 an-1
front rear
队头入队出队队尾
队列的抽象数据类型定义见教材
队列的存储结构为 链队 或 顺序队 （常用循环顺序队）
插入元素称为 入队 ；删除元素称为 出队 。
1,定 义
4.3.1 队列的结构特点和操作与同线性表相同，仍为一对一关系。
顺序队 或 链队,以循环顺序队更常见。
只能在队首和队尾运算，且访问结点时依照先进先出 （ FIFO） 的原则。
关键是掌握 入队 和 出队 操作，具体实现依顺序队或链队的不同而不同。
基本操作有入队或出队，建空队列，判队空或队满等操作。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （ 头删尾插 ）
例如：队列 Q = ( a1,a2,a3,……….,an-1,an )
队头 队尾队列的进队和出队原则
进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位臵加入。
出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
队满时再进队将 溢出出错 ；
队空时再出队将 队空处理 。
解决办法之一,将队列元素存放数组首尾相接,
形成 循环 (环形 )队列 。
队列的进队和出队示例
front rear 空队列 front rear A进队
A
front rear B进队
A B
front rear C,D进队
A B C D
front rear A退队
B C D
front rear B退队
C D
front rear E,F,G进队
C D E F G C D E F G
front rear H进队,溢出队列的基本操作
InitQueue(&Q)
操作结果,构造一个空队列 Q。
DestroyQueue(&Q)
初始条件,队列 Q已存在。
操作结果,队列 Q被销毁，不再存在。
QueueEmpty(Q)
初始条件,队列 Q已存在。
操作结果,若 Q为空队列，则返回 TRUE，否则返回 FALSE。
QueueLength(Q)
初始条件,队列 Q已存在。
操作结果,返回 Q的元素个数，即队列的长度。
ClearQueue(&Q)
初始条件,队列 Q已存在。
操作结果,将 Q清为空队列。
a1 a2 an… …
GetHead(Q,&e)
初始条件,Q为非空队列。
操作结果,用 e返回 Q的队头元素。
EnQueue(&Q,e)
初始条件,队列 Q已存在。
操作结果,插入元素 e为 Q的新的队尾元素。
a1 a2 an e … …
DeQueue(&Q,&e)
初始条件,Q为非空队列。
操作结果,删除 Q的队头元素，并用 e返回其值。
a1 a2 an… …
链队列,基本操作的实现
无队满问题 (除非分配不出内存 ),空间可扩充
引入头结点 (一定需要吗？ )
a1 a2 an ^
Q.front
Q.rear
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
队头在链头，队尾在链尾。
链式队列在进队时无队满问题,但 有队空问题 。
队空条件为,front == NULL
4.3.2 队列的表示和操作实现
Q.front
Q.rear
∧
空队列
Q.front
Q.rear
Q.front
Q.rear
Q.front
Q.rear
X ∧
Y ∧X
Y ∧X
元素 X入队列元素 Y入队列元素 X出队列链队列讨论讨论：
① 空队列的特征？
(队尾 )(队首 )
front
a1 a2 a3 ^
rear
p
front
^
rear
③ 怎样实现入队和出队操作？
入队（尾部插入）,rear->next=S; rear=S;
出队（头部删除）,front->next=p->next;
② 队列会满吗？
front=rear
一般不会，因为删除时有 free动作。除非内存不足！
Typedef LinkList QuencePtr;
typedef struct { // 链队列类型
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue;
a1 ∧an…Q.front
Q.front
Q.rear ∧空队列
Q.rear
队列 –链队列的表示与实现
void InitQueue_L( LinkQueue &Q )
{ // 构造一个空队列 Q
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
}
void DestroyQuence_L( LinkQueue &Q )
{ // 销毁链队列结构 Q
while ( Q,front ) {
Q.rear = Q,front->next;
delete Q.front;
Q,front = Q.rear;
}
}
void EnQueue_L( LinkQueue &Q,QElemType e )
{ // 插入元素 e为 Q的新的队尾元素
p = new QNode;
p->data = e; p->next = NULL;
Q.rear->next = p; Q.rear = p;
}
a1 ∧anQ.front
Q.rear
∧e
p
bool DeQueue_L( LinkQueue &Q,QElemType &e )
{
//若队列不空，则删除 Q的队头元素，用 e 返回其值，并返回 TRUE；
//否则返回 FALSE
if (Q.front == Q.rear) return FALSE;
p = Q.front->next; e = p->data;
Q.front->next = p->next;
delete (p);
return OK;
}
if ( Q.rear == p ) Q.rear = Q.front;
null
*q
q.rear x null
q.front
p
存储池循环队列队列的顺序存储约定与类型定义,Q.front和 Q.rear的含义删除,避免大量的移动 ->头指针增 1
问题,假上溢?首尾相接的环（ 钟 ）
队头
Q.front
入队出队
a1 a2 a3 … … an
Q.rear
队尾
2、循环队列基本操作的实现初始化空队,Q.front=Q.rear=0;
入队,判断是否队满；非队满时,Q.rear位置放新插入的元素,Q.rear++
出队,判断是否队空，非队空时,Q.front位置为待删除的元素,Q.front++
队空条件,Q.front == Q.rear
队满条件,Q.rear == MAXQSIZE
问题,假上溢 ()
Q.front
入队出队
a1 a2 a3 … … an
Q.rear
队尾循环队列实现：用一维数组实现 sq[M]
front=-1
rear=-1
1
2
3
4
5
0
队空
1
2
3
4
5
0
front J
1,J1,J3入队
J1
J2
J3rear
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
设两个指针 front,rear,约定：
rear指示队尾元素；
front指示队头元素前一位臵初值 front=rear=-1
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
front
front
front
循环队列当 J6 入队后,队尾指针 Q.rear越界,不可能再插入新的队尾元素,但是另一方面,
队列的实际可用空间并未占满。一个巧妙的办法是,将顺序队列设想为首尾相连的环状空间,当 Q.rear 值超出队列空间的最大位臵时,令 Q.rear= 0,使队列空间能
“循环”使用。这种循环使用空间的队列称为循环队列。
J6
J4
J5
Q.rear
Q.front 3 1
2
4 05
循环队列图示
5
4
3
2
1
0
Q.rear
Q.front
J6
J5
J4
存在问题,设数组维数为 M,则,队首固定，每次出队剩余元素向下移动 ——浪费时间解决方案,循环队列基本思想,把队列 设想成环形,让 sq[0]接在 sq[M-1]之后,
若 rear+1==M,则令 rear=0;
0
M-1
1
front
rear
实现,利用“模”运算入队,rear=(rear+1)%M; sq[rear]=x;
出队,front=(front+1)%M; x=sq[front];
队满、队空判定条件循环队列假上溢的解决办法把顺序队列看成首尾相接的环 (钟表 )-循环队列基本操作的实现
– 入队,Q.rear = ( Q.rear+1)%MAXQSIZE
– 出队,Q.front = ( Q.front+1)%MAXQSIZE
– 队空条件,Q.front == Q.rear
由于出队 Q.front追上了 Q.rear
– 队满条件,Q.front == Q.rear
由于入队 Q.rear追上了 Q.front
问题,队空和队满的判断条件一样循环队列
0
123
4 5
rear
front
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
J4
J5
J6
0
123
4 5
rear
front
初始状态队空,front==rear
队满,front==rear
解决方案：
1,另外 设一个标志 以区别队空、队满
2,少用一个元素空间,
队空,front==rear
队满,(rear+1)%M==front
新问题,在循环队列中，空队特征是 front=rear； 队满时也会有
front=rear； 判决条件将出现二义性！
解决方案有三：
① 加设标志位，让删除动作使其为 1,插入动作使其为 0,则可识别当前 front=rear
② 使用一个计数器记录队列中元素个数（即队列长度）；
③ 人为浪费一个单元，令 队满特征为 front=(rear+1)%N；
循环队列讨论
② 队列会满吗？
很可能会，因为数组前端空间无法释放。因此 数组应当有长度限制。
① 空队列的特征？
约定,front=rear
入队 (尾部插入 ),v[rear]=e; rear++;
出队 (头部删除 ),x=v[front]; front++;
讨论：
假溢出有缺陷
③ 怎样实现入队和出队操作？
J2 J3
J1 J4
J5
front
rear
问 2,在具有 n个单元的循环队列中，
队满时共有多少个元素？ n-1个
6 问 1：上图中队列长度 L=？
队列存放数组被当作首尾相接的表处理。
队头、队尾指针 加 1时从 maxSize -1直接进到 0，可用语言的取模 (余数 )运算实现。
队头指针出,front = (front+1) % maxSize;
队尾指针进,rear = (rear+1) % maxSize;
队列初始化,front = rear = 0;
队空条件,front == rear;
队满条件,(rear+1) % maxSize == front
4,循环队列 (Circular Queue)
队空,Q.front =Q,rear
队满,Q.front =(Q.rear + 1) % maxSize
入队,Q.rear = (Q.rear + 1) % maxSize
出队,Q.front = (front + 1) % maxSize;
求队长,(Q.rear-Q.front+maxSize)%maxSize
#define MAXQSIZE 100 //最大队列长度
const QUENCE_INIT_SIZE = 100;
Const QUENCEINCREMENTSIZE = 10;
typedef struct {
QElemType *elem; // 动态分配存储空间
int front; //头指针,若队列不空,指向队列头元素
int rear; //尾指针,若队列不空,指向队列尾元素 的下一个位置
int queuesize;
int incrementsize;
} SqQueue;
循环队列
void InitQueue_Sq(SqQueue &Q,int maxsize=QUENCE_INIT_SIZE,
int incresize = QUENCEINCREMENT) {
//构造一个最大存储空间为 maxsize 的空循环队列 Q
Q.elem = new QElemType[maxsize+1];
Q.queuesize = maxsize;
Q.incrementsize = incresize;
Q.front = Q.rear = 0;
}
int QuenceLength(SqQueue Q)
{
//返回 Q的元素个数，即队列的长度
return (Q.rear-Q.front+Q.quencesize)%Q.quencesize;
}
Status DeQueue (SqQueue &Q,QElemType &e) {
// 若队列不空，则删除 Q的队头元素，
// 用 e返回其值，并返回 TRUE; 否则返回 FALSE
if (Q.front == Q.rear) return FALSE;
e = Q.elem[Q.front];
Q.front = (Q.front+1) % Q.queuesize;
return TRUE;
}
void EnQueue (SqQueue &Q,QElemType e)
{
// 插入元素 e为 Q的新的队尾元素
if ((Q.rear+1) % Q.queuesize == Q.front)
incrementQuencesize(Q);
Q.elem[Q.rear] = e;
Q.rear = (Q.rear+1) % Q.queuesize;
return OK;
}
J6 J5
J7
J8 J9
例：一循环队列如下图所示，若先删除 4个元素，接着再插入 4个元素，请问队头和队尾指针分别指向哪个位置?
J2 J3
J1 J4
J5
front
rear
解,由图可知，队头和队尾指针的初态分别为 front=1和 rear=6。
front
rear
删除 4个元素后 front=5；再插入 4个元素后,r=(6+4)%6=4
front front
front
front
问：什么叫,假溢出,？如何解决？
答,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位臵，这就叫,假溢出,。
解决假溢出的途径 —采用循环队列例：数组Ｑ [n]用来表示一个循环队列,f 为当前队列头元素的前一位置,r 为队尾元素的位置。假定队列中元素的个数小于 n，计算队列中元素的公式为,
（Ａ） r－ f （Ｂ）（ n＋ f－ r） % n
（Ｃ） n＋ r－ f （Ｄ） （ n＋ r－ f） % n
4种公式哪种合理？
当 r ≥f时 （ A） 合理；
当 r < f 时 （ C） 合理；
分析：
综合 2种情况，以（ D）的表达最为合理例,在一个循环队列中，若约定队首指针指向队首元素的 前一个位置。那么，从循环队列中删除一个元素时，其操作是先,后 。移动队首指针 取出元素
√
问,为什么要设计队列？它有什么独特用途？
1,离散事件的模拟（模拟事件发生的先后顺序）；
2,操作系统中多道作业的处理（一个 CPU执行多个作业）；
3,简化程序设计。
答：
第 1 行 1 1
第 2 行 1 2 1
第 3 行 1 3 3 1
第 4 行 1 4 6 4 1
二项式系数值（杨辉三角）
设第 i-1行的值,(a[0]=0) a[1]..a[i] (a[i+1]=0)
则第 i 行的值,b[j] = a[j-1]+a[j],j=1,2,…,i+1
1、计算 n 行杨辉三角的值
4.4 队列应用举例利用循环队列计算二项式的过程：
假设只计算三行，则队列的最大容量为 5。
1 1 00
q.front q.rear
1 1 00 1
q.frontq.rear
1 1 02 1
q.frontq.rear
1 1 02 1
q.frontq.rear
1 0 02 1
q.frontq.rear
1 0 12 1
q.frontq.rear
1 0 12 1
q.frontq.rear
1 0 12 3
q.frontq.rear
1 0 13 3
q.frontq.rear
1 0 13 3
q.frontq.rear
do {
DeQueue(Q,s);
GetHead(Q,e);
if (e!=0) printf (“%d”,e);
EnQueue(Q,s+e);
} while (e!=0);
void yanghui( int n )
{
SqQuence Q;
for ( i=1; i<=n; i++ ) cout <<;
cout <<?1? << endl;
InitQuence_Sq( Q,n+1 );
EnQuence_Sq( Q,0 ); EnQuence_Sq( Q,1 ); EnQuence_Sq( Q,1 );
k = 1;
while ( k<n ) {
for ( i=1; i<=n-k; i++ ) cout <<;
EnQuence_Sq( Q,0 );
do {
DeQuence_Sq( Q,s ); GetHead)Sq( Q,e );
if ( e ) cout << e <<; else cout << endl;
EnQuence_Sq( Q,s+e );
} while ( e!=0 );
k++
}
DeQuence_Sq( Q,e );
while ( !QuenceEmpty(Q) ) { DeQuence_Sq( Q,e ); cout << e <<; }
}
算法某运动会设立 N个比赛项目,每个运动员可以参加一至三个项目 。 试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行,又使总的竞赛日程最短 。
若将此问题抽象成数学模型，则归属于,划分子集,问题。 N
个比赛项目构成一个大小为 n 的集合，有同一运动员参加的项目则抽象为,冲突,关系。
2,,划分无冲突子集问题,求解例如：某运动会设有 9 个项目,A = { 0,1,2,3,4,5,6,7,8 }，
七名运动员报名参加的项目分别为：
(1,4,8),(1,7),(8,3),(1,0,5),(3,4),(5,6,2),(6,4)
它们之间的冲突关系为,
R = { (1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4) }
将集合 A划分成 k个互不相交的子集
A1,A2,…,Ak（ k≤n ）,
使同一子集中的元素均无冲突关系,并要求划分的子集数目尽可能地少 。
“划分子集,问题即为,
对前述例子而言，问题即为,同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。
可利用,过筛,的方法来解决划分子集问题。从第一个元素考虑起,凡不和第一个元素发生冲突的元素都可以和它分在同一子集中,然后再,过筛,出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止
。为了减少重复察看 R 数组的时间，可另设一个数组 clash[n] 记录和当前已入组元素发生冲突的元素的信息。每次新开辟一组时，
令 clash 数组各分量的值均为,0”，当序号为,i”的元素入组时，
将和该元素发生冲突的信息记入 clash 数组。
0 1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0 0 0
1 1 0 0 0 1 1 0 1 1
2 0 0 0 0 0 1 1 0 0
3 0 0 0 0 1 0 0 0 1
4 0 1 0 1 0 0 1 0 1
5 1 1 1 0 0 0 1 0 0
6 0 0 1 0 1 1 0 0 0
7 0 1 0 0 0 0 0 0 0
8 0 1 0 1 1 0 0 0 0
012345678
14568
458
8
1 2 11 12
pre (前一个出队列的元素序号 ) = n; 组号 = 0;
全体元素入队列 ;
while ( 队列不空 ) {
队头元素 i出队列 ;
if ( i < pre ) // 开辟新的组
{ 组号 ++; clash 数组初始化 ; }
if ( i 能入组 ) {
i 入组,记下序号为 i 的元素所属组号 ;
修改 clash 数组 ;
}
else i 重新入队列 ;
pre = i;
}
划分子集算法的基本思想问题描述,已知集合 A={a1,a2,……a n},及集合上的关系
R={ (ai,aj) | ai,aj?A,i?j},其中 (ai,aj)表示 ai与 aj间存在冲突关系。
要求将 A划分成 互不相交 的子集 A1,A2,……Ak,(k?n),使任何子集中的元素均无冲突关系，同时要求 分子集个数尽可能少例 A={1,2,3,4,5,6,7,8,9}
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),
(3,7),(6,3) }
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
划分子集问题所用数据结构
–冲突关系矩阵,r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
–循环队列 cq[n]
–数组 result[n]存放每个元素分组号
–工作数组 newr[n]
算法思想,利用 循环筛选 。从第一个元素开始，
凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组划分子集问题工作过程
1,初始状态,A中元素放于 cq中,result和 newr数组清零，组号 group=1
2,第一个元素出队，将 r矩阵中第一行,1”拷入 newr
中对应位臵，这样，凡与第一个元素有冲突的元素在 newr中对应位臵处均为,1”,下一个元素出队
3,若其在 newr中对应位臵为,1”，有冲突，重新插入 cq队尾，参加下一次分组
4,若其在 newr中对应位臵为,0”,无冲突，可划归本组；再将 r矩阵中该元素对应行中的,1”拷入 newr
中
5,如此反复，直到 9个元素依次出队，由 newr中为,0”
的单元对应的元素构成第 1组,将组号 group值,1”
写入 result对应单元中
6,令 group=2,newr清零，对 cq中元素重复上述操作，
直到 cq中 front==rear,即队空,运算结束。
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
初始
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 1 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 1 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 7 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
6 7 9 5
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
7 9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
5 6 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
6 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
9 6
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 0 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 1 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 4
0 1 2 3 4 5 6 7 8
result
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
void division ( int R[ ][ ],int n,int result [ ] ) {
// 已知 R[n][n] 是编号为 0 至 n-1 的 n 个元素的关系矩阵，子集划分的
//结果记入 result 数组,result[k] 的值是编号为 k 的元素所属组号
pre = n; group = 0;
InitQueue_Sq ( Q,n ); // 设置最大容量为 n 的空队列
for ( e = 0; e < n; e++ ) EnQueue_Sq ( Q,e,0 );
while ( !QueueEmpty ( Q ) ) {
DeQueue_Sq ( Q,i );
if ( i < pre ) {
group ++; // 增加一个新的组
for ( j = 0; j < n; j ++ ) clash[j] = 0;
}
if ( clash[i] == 0 ) {
result[i] = group; // 编号为 i 的元素入 group 组
for ( j = 0; j < n; j ++ ) clash[j] += R[i][j]; // 添加和 i冲突的信息
}
else EnQueue ( Q,i,0 ); // 编号为 i 的元素不能入当前组
pre = i;
} // while
} // division
讨论线性表、栈与队的异同点相同点,逻辑结构相同,都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表,即受限的线性表 （ 只是对插入,删除运算加以限制 ） 。
不同点：
① 运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入和删除运算,因而是后进先出表 LIFO；
队列是只允许在一端进行插入,另一端进行删除运算,
因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调用、
递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。
1,掌握栈和队列类型的特点,并能在相应的应用问题中正确选用它们 。
2,熟练掌握栈类型的两种实现方法,特别应注意栈满和栈空的条件以及它们的描述方法 。
3,熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法 。
4,理解递归算法执行过程中栈的状态变化过程 。
总结
1,餐馆中一叠一叠的盘子,如果它们是按 1,2,…,n 的次序往上叠的，那么使用时候的次序应是什么样的？
必然是 依从上往下 的次序，即 n,…,2,1。它们遵循的是 "后进先出 "的规律，这正是本章要讨论的 "栈 "的结构特点。
是 "排队 "。在计算机程序中，模拟排队的数据结构是 "队列 "。
栈和队列是两种特殊的线性表,是 操作受限 的线性表,
称 限定性数据结构 。
2,在日常生活中，为了维持正常的社会 秩序 而出现的常见 现象 是什么？
4.1 栈
4.2 栈的应用举例
4.3 队列
4.4 队列应用举例
【 学习目标 】
1.掌握 栈 和 队列 这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2.熟练掌握栈类型的两种实现方法。
3.熟练掌握 循环队列 和 链队列 的 基本操作实现算法。
4.理解递归算法执行过程中栈的状态变化过程。
【 重点和难点 】
栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。
重点,栈和队列的基本特征，表示与实现难点,递归、循环队列算法,栈和队列的实现及其应用顺序栈、链栈、递归、循环队列、链队列
【 知识点 】
【 学习指南 】
本章主要是学习如何在求解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，
如 栈满和栈空、队满和队空的条件以及它们的描述方法。
本章要求必须完成的算法设计题为：
4.1,4.2,4.3,4.4,4.5,4.6,4.9,4.11,4.12
4.1 栈是限定仅 在表尾进行插入或删除 操作的 线性表。
允许插入,删除的一端称为 栈顶 (top),另一端称为 栈底 (bottom)
top
bottom
进栈出栈
an
.
.
.
.
a1
基本操作：
后进先出 (LIFO)
定义,栈 ─ 特殊的线性表,操作受限的线性表逻辑特征：
创建一个空栈；
判断栈是否为空栈；
判断栈是否为满；
往栈中插入 (或称推入 )一个元素；
从栈中删除 (或称弹出 )一个元素；
求栈顶元素的值。
访问栈中每个元素栈和队列是两种常用的数据类型栈和队列是限定插入和删除只能在表的,端点,进行的线性表。
线性表 栈 队列
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
一般线性表 堆栈逻辑结构,一对一 逻辑结构,一对一存储结构,顺序表、链表 存储结构,顺序栈、链栈运算规则,随机存取 运算规则,后进先出 (LIFO)
1,定义与线性表相同,仍为一对一关系。
用 顺序栈 或 链栈 存储均可,顺序栈更常见只能在 栈顶 运算,且访问结点时依照后进先出 (LIFO)或先进后出 (FILO)的原则。
关键是编写 入栈 和 出栈 函数，具体实现依顺序栈或链栈的不同而不同。
基本操作有 入栈,出栈,读栈顶元素值,建栈,
判栈满,判 栈空 等。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构限定只能在 表的一端 进行插入和删除运算的 线性表 (只能在栈顶操作 )
4.1.1 栈的特点和操作例如,栈 s = ( a1,a2,a3,……,an-1,an )
an 称为栈顶元素插入元素到 栈顶 (即表尾 )的操作，称为 入栈 。
从 栈顶 (即表尾 )删除最后一个元素的操作，称为 出栈 。
强调,插入和删除都只能在表的一端（栈顶）进行！
a1 称为栈底元素栈是仅在 表尾 进行插入、删除操作的线性表。
表尾 (即 an 端 )称为 栈顶 top ; 表头 (即 a1 端 )称为 栈底 base
“进,＝压入 =PUSH（ x)
“出,＝弹出 =POP ( y )
4.1.1 栈的特点和操作栈的基本操作
InitStack(&S)
操作结果,构造一个空栈 S。
DestroyStack(&S)
初始条件,S已存在。 操作结果,栈 S被销毁。
ClearStack(&S)
初始条件,S已存在。 操作结果,将 S清为空栈。
StackEmpty(S)
初始条件,S已存在。 操作结果,若栈 S为空栈，则返回 TRUE，否则 FALE。
StackLength(S)
初始条件,S已存在。 操作结果,返回 S的元素个数，即栈的长度。
GetTop(S,&e)
初始条件,S已存在且非空。 操作结果,用 e返回 S的栈顶元素。
Push(&S,e)
初始条件,S已存在。 操作结果,插入元素 e为新的栈顶元素。
Pop(&S,&e)
初始条件,S已存在且非空。 操作结果,删除 S的栈顶元素,并用 e返回其值。
StackTraverse(S)
初始条件,S已存在且非空。 操作结果,从底到顶依次输出 S中的元素。
ana1 a2 … …
GetTop(S,&e)
初始条件,栈 S 已存在且非空。
操作结果,用 e 返回 S 的栈顶元素。
e
Push(&S,e)
初始条件,栈 S 已存在。
操作结果,插入元素 e 为新的栈顶元素。
Pop(&S,&e)
初始条件,栈 S 已存在且非空。
操作结果,删除 S 的栈顶元素，并用 e 返回其值。
图示栈的三种常用基本操作
ana1 a2 … …
an-1a1 a2 … … an-
4.1.2 栈的表示和操作实现
1、顺序栈
2、链 栈顺序栈的存储结构实现：一维数组 s[M]
top=0
1
2
3
4
5
0
栈空栈顶指针 top,指向实际栈顶后的空位臵，初值为 0
top 1
2
3
4
5
0
进栈
A
top
出栈栈满
B
C
D
E
F
top
top
top
top
top
1
2
3
4
5
0A
B
C
D
E
Ftop
top
top
top
top
top
栈空设数组维数为 M
top=0,栈空,此时出栈，则 下溢 （ underflow)
top=M,栈满,此时入栈，则 上溢 （ overflow)
1、栈的表示与实现 ──顺序栈
1、栈 的表示与实现 ──顺序栈顺序栈基本操作的实现：
– 栈顶的初始化,S.top = S.base
– 栈空,S.base == S.top
– 栈满,S.top - S.base >= S.stacksize
– 入栈,*S.top ++ = e，出栈,e = *--S.top
base
空栈 a 进栈 b 进栈
atop base
top
base
top
a
b
约定,top指向栈顶元素的下一个位置
a1
a2
……
an
顺序栈 S
ai
……
表和栈的操作区别 —— 对线性表 s = ( a1,a2,….,an-1,an )
表头表尾栈底 base
栈顶 top
低地址高地址写入,v[i]= ai
读出,x= v[i]
压入,PUSH (an+1)
弹出,POP (x)
前提：一定要 预设 栈顶指针 top！
低地址高地址
v[i]
a1
a2
ai
an
……
顺序表 V[n]
……
an+1
入栈操作,
例如用堆栈存放 (A,B,C,D)(注意要遵循,后进先出,原则 )
A A
C
B
A
B
Atop
核心语句：
top=L; 顺序栈中的 PUSH函数status Push( ElemType x )
{
if ( top>M ) { 上溢 }
else v[top++] = x;
}
Push( B );
Push( C );
Push( D );
top
top
top
top
低地址 L
Push( A );
高地址 M
B
C
D
出栈操作,例如从栈中取出 ‘ B’（注意要遵循,后进先出,原则）
D
C
B
A top
top
D
C
A
B
D
C
B
A
topD
C
B
A
top
低地址 L
高地址 M
核心语句：
Pop ( );
Pop ( );
Printf( Pop () );
顺序栈中的 POP函数
status Pop( )
{
if ( top=L ) { 下溢 }
else {
y = v[--top];
return( y );
}
}
若入栈动作使地址向高端增长,称为,向上生成,的栈；
若入栈动作使地址向低端增长,称为,向下生成,的栈；
对于向上生成的栈入栈 口诀,堆栈指针 top先压后加 （ v[top++]=x） ；
出栈 口诀,堆栈指针 top先减后弹 （ y=v[--top]) 。
栈不存在的条件,base=NULL;
栈为空 的条件,base=top;
栈满的条件,top-base=stacksize;
问,为什么要设计堆栈？它有什么独特用途？
1,调用函数或子程序非它莫属；
2,递归运算的有力工具；
3,用于保护现场和恢复现场；
4,简化了程序设计的问题。
答：
问,栈是什么？ 它与一般线性表有什么不同？
答,栈是一种特殊的线性表,它只能在 表的一端 (即栈顶 )进行插入和删除运算。
与一般线性表的区别,仅在于 运算规则 不同。
例 对于一个栈,给出输入项 A,B,C,如果输入项序列由 ABC组成，
试给出所有可能的输出序列。
A进 A出 B进 B出 C进 C出 ABC
A进 A出 B进 C进 C出 B出 ACB
A进 B进 B出 A出 C进 C出 BAC
A进 B进 B出 C进 C出 A出 BCA
A进 B进 C进 C出 B出 A出 CBA
不可能产生输出序列 CAB
例 一个栈的输入序列是 12345，若在入栈的过程中允许出栈，则栈的输出序列 43512可能实现吗？ 12345的输出呢？
43512不可能实现,主要是其中的 12顺序不能实现；
12345的输出可以实现，只需压入一个立即弹出一个即可。
435612中到了 12顺序不能实现；
135426可以实现。
例 如果一个栈的输入序列为 123456，能否得到 435612和 135426的出栈序列？
答：
答：
例,设依次进入一个栈的元素序列为 c,a,b,d,则可得到出栈的元素序列是：
Ａ） a,b,c,d Ｂ） c,d,a,b Ｃ） b,c,d,a Ｄ） a,c,d,b
A,D可以 ( B,C不行 )。
讨论,有无通用的判别原则？
有。 在可能的输出序列中，不存在这样的输入序列 i,j,k，能同时满足 i<j<k 和 Pj<Pk<Pi
答：
SqStack,结构类型名；
SqStack,它的三个域分别是：
elem,栈底指针，指向栈底位置；
top,栈顶指针；
Stacksize,已分配的存储空间 (一元素为单位 )大小；
const STACK_INIT_SIZE 100
const STACKINCREMENT 10
typedef struct {
SElemType *elem;
int top //栈顶指针
int stacksize;
int increment;
} SqStack;
顺序栈算法约定栈顶指针指向栈顶元素的下 (后面 )一个位置
elem
top
stacksize
increment
0
0
0
a1
a2
an-2
an-1
an
...
...
elem
top
stacksize
increment
0
0
0
void InitStack_Sq(SqStack &S,
int maxsize=STACK_INIT_SIZE,
int incresize = SRACKINCREMENTSIZE )
{
S.base= new SElemType[STACK_INIT_SIZE];
S.top = 0;
S.stacksize = maxsize;
S.incrementsize = incresize;
} //InitStack_Sq
1) 初始化操作 InitStack_Sq((SqStack &S)
参数,S是存放栈的结构变量；
功能,建一个空栈 S；
a1
a2
an-2
an-1
an
...
...100
0
10
顺序栈算法
const STACK_INIT_SIZE 100
const STACKINCREMENT 10
void DetroyStack_Sq ( SqStack &S)
{
If ( !S.elem) return ERROR;
delete S.elem;
S.top = 0;
S.stacksize = 0;
S.increment = 0;
}
2) 销毁栈操作 DestroyStack_Sq(SqStack &S )
功能,销毁一个已存在的栈 ;
elem
top
stacksize
increment
20
100
10
a1
a2
an-2
an-1
an
...
...
0
0
0
null
顺序栈算法
3) 置空栈操作 ClearStack_Sq(SqStack &S)
功能,将栈 S置为空栈
void ClearStack_Sq ( SqStack &S)
{
If ( !S.elem ) return ERROR;
S.top = 0;
}
elem
top
stacksize
increment
20
100
10
a1
a2
an-2
an-1
an
...
...
0
顺序栈算法
bool GetTop_Sq(SqStack S,SelemType &e)
{
if ( S.top == 0 ) return FALSE;
e = S.elem[S.top-1];
return TRUE;
}
4) 取栈顶元素操作 GetTop_Sq(SqStack S,SElemType &e)
功能,取栈顶元素，并用 e返回 ;
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e iai
void Push( SqStack &S,SElemType e )
{
if ( S.top>=S.stacksize)
incrementStackSize( S );
S.elem[S.top++] = e;
}
1) S是否已满,若 栈 满，重新分配存储空间；
2) 将元素 e 写入栈顶；
3) 修改栈顶指针,使栈顶指针指向栈顶元素的下 (后面 )一个位臵；
6) 入栈操作 Push(SqStack &S,SElemType e )
功能：将 e入栈 ;
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e x
i+1
x
6) 出 栈操作 Pop(SqStack &S,SElemType &e )
功能,栈顶元素退栈，并用 e 返回 ;
bool Pop_Sq( SqStack &S,SElemType &e)
{
if ( S.top== 0) return FALSE;
e = S.elem[--S.top];
return TRUE;
}//Pop
顺序栈算法
elem
top
stacksize
increment
i
100
10
a1
a2
ai-1
ai-
ai+1
...
...
e iai
-1
约定,top指向栈顶元素所在的结点
链栈
– 无栈满问题 (除非分配不出内存 ),空间可扩充
– 栈顶 ----链表的表头
– 可以不必引入头结点
^top
栈顶指针 ∧a1an
注意,链栈中指针的方向
an-1
栈底元素
N
2、栈的表示与实现 ── 链栈
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作链栈栈顶
^…top data next
栈底结点定义,
–入栈算法
–出栈算法
typedef struct node
{ int data;
struct node *next;
} Node;
typedef LinkList LinkStack;
^…...
栈底
toptop
xp
^…...
栈底
top
q
链栈的定义
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int Data;
typedef struct node {
ElemType data;
struct node *next;
} LNode;
Typedef LinkList LinkStack
初始化
void InitStack_L( LinkStack *S )
{
S = NULL;
}
入栈
void Push_L ( LinkStack *S,ElemType e )
{
LNode *p = new LNode ;
p->data = e;
p->next = S;
S = p;
}
顺序栈算法
–入栈算法
^…...
栈底toptop
xp
判栈空
bool StackEmpty_L( LinkStack *S )
{
return !S;
}
出栈
bool Pop_L( LinkStack *S,ElemType *e )
{
if ( S ) {
LNode *p = S;
S = S->next;
*e = p->data;
delete p;
return TRUE;
}
else return FALSE;
}
取栈顶
bool GetTop_L( LinkStack *S,ElemType *e )
{
if ( !S ) return 0;
else {
*e = S->data;
return 1;
}
}
臵栈空
int MakeEmpty_L( LinkStack *S )
{ Lnode *p;
while( S )
{
p = S; S = S->next;
delete p;
}
}
链栈算法
–出栈算法
^…...
栈底
top
q
X
3.2 栈的应用举例例一,数制转换例二,括号匹配的检验例三,背包问题求解例四,表达式求值例五,实现递归例如,（ 1348)10 = (2504)8,其运算过程如下：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
计算顺序输出顺序算法基于原理,N = (N div d)× d + N mod d
例一 数制转换
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
假设在表达式中,（［］（））或［（［ ］［ ］）］ 等为正确的格式，［（ ］）或（［（ ））或 ( ( ) ] ) 均为不正确的格式。
检验括号是否匹配 的方法可用,期待的急迫程度” 来描述。
例二 括号匹配的检验例如,考虑下列括号序列,
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
分析可能出现的 不匹配 的情况,
算法的设计思想
1）凡出现 左括弧,则 进栈 ；
2）凡出现 右括弧,首先检查栈是否空,若 栈空,则表明该,右括弧,多余,否则 和栈顶元素 比较，若 相匹配,则,左括弧出栈,
否则表明 不匹配
3）表达式检验结束时，若栈空，则表明表达式中 匹配正确否则表明,左括弧,有余
bool matching(string exp[] )
{
int state = 1; ch = *exp++；
while ( ch !=?#? && state ) {
switch ( ch ) {
case?(?,
case?[?,{ Push(S,ch ); break; }
case?)?,{
if ( !StackEmpty(S) && GetTop(S) =?(? ) Pop(S,e);
else state = 0;
break;
}
case?]?,{
if ( !StackEmpty(S) && GetTop(S) =?[? ) Pop(S,e);
else state = 0;
break;
}
} //switch
ch = *exp++;
} //while
if (StackEmpty(S) && state) return TRUE;
else return FALSE;
}
设有一个背包可以放入的物品的重量为 s,现有 n件物品,重量分别为 w[1],w[2],…,w[n]。 问能否从这 n件物品中选择若干件放入此背包中,使得放入的重量之和正好为 s。 如果存在一种符合上述要求的选择,则称此背包问题有解 (或称其解为真 )；否则称此背包问题无解 (或称其解为假 )。
例三 背包问题一个背包可以放入的物品重量为 s,现有 n件物品,重量分别为 w1,w2,…,wn,问能否从这些物品中选若干件放入背包中,
使得放入的重量之和正好是 s。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解。
例三 背包问题如果有解：
1,选择的一组物品中不包含 wn;
knap( s,n-1 ) 的解就是 knap( s,n)的解；
2,选择的一组物品中包含 wn;
knap( s-wn,n -1 )的解就是 knap( s,n)的解,
背包问题表示,int knap( int s,int n ) 其中,s>=0,n>=1
top
8 4
3 5 2
S
1
背包容积 T=10
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
k=0
0 1 2
3 4 5
k
背包问题求解
T=10
S
top 1->8
4
3 5 2
0->1
背包容积 T=1
k=2 放不进去
0 1 2
3 4 5
3 放不进去4 放不进去K=0,1进栈,k=3,4,5 放不进去,k=6
注意内循环条件 while (T >0 && k < n )
k=1(体积 8)必须出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=1
0 1 2
3 4 5
k=2,3进栈外循环条件 while (!(StackEmpty(S) && k == n));
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
2,3进栈 k=4 放不下
0 1 2
3 4 5
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
55->2
0->1
背包容积 T=0
k=5
进栈
0 1 2
3 4 5
if (T == 0 ) StackTraverse(S,w);条件满足输出一组解
k=6 注意内循环条件栈顶元素出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
k=5
0 1 2
3 4 5
栈不空继续找解 (注意外循环条件 )
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3->3
5 2
0->1
背包容积 T=2
k=6
0 1 2
3 4 5
T不等于 0,不输出,栈顶出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=3
0 1 2
3 4 5
k=4 继续入栈
k=4
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3
4->5
2
0->1
背包容积 T=0
k=4
0 1 2
3 4 5
T=0 又找到一组解
k=5
栈顶元素出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=4
0 1 2
3 4 5
K=5 进栈,继续找解
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5
5->2
0->1
背包容积 T=3
k=5
0 1 2
3 4 5
T不为 0 继续找解,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=5
0 1 2
3 4 5
栈不空继续找解 (外循环 )
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8
2->4
3 5 2
0->1
背包容积 T=5
k=6
0 1 2
3 4 5
不满足内循环条件,T<>0,出栈物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=2
0 1 2
3 4 5
继续找解
k=3
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
4->5
2
0->1
背包容积 T=1
k=3
进栈
0 1 2
3 4 5
脱离内循环,必须出栈,继续找解
k=4
进栈
k=5
不进栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5 2
0->1
背包容积 T=6
k=4
0 1 2
3 4 5
k=4栈顶出栈后,k=5进栈继续找解
k=5(进栈 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5
5->2
0->1
背包容积 T=4
k=5
0 1 2
3 4 5
T不为 0不输出,栈顶出栈
k=6脱离内循环物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3->3
5 2
0->1
背包容积 T=6
k=5出栈
0 1 2
3 4 5
外循环条件,栈不空继续找解
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=3出栈
0 1 2
3 4 5
不进入内循环,栈顶出栈,继续找解
k=4
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3
4->5
5->2
0->1
背包容积 T=2
k=4进栈
0 1 2
3 4 5
T不为 0不输出,栈顶出栈
k=5进栈 k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3
4->5
5->2
0->1
背包容积 T=4
k=5出栈后
0 1 2
3 4 5
栈不空继续找解,k=6不进入内循环
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=4出栈
0 1 2
3 4 5
继续找解
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5
5->2
0->1
背包容积 T=7
k=5进栈
0 1 2
3 4 5
T不为 0不输出,不进入内循环,出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
8 4
3 5 2
0->1
背包容积 T=9
k=5出栈后
0 1 2
3 4 5
栈不空继续找解,不进入内循环
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
Stop
8 4
3 5 2
1
背包容积 T=10
k=0出栈后
0 1 2
3 4 5
栈空了，但 k<>n继续找解,进入内循环
k=1
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top 1->8
4
3 5 2
1
背包容积 T=2
k=2
不进栈
0 1 2
3 4 5
继续找解
k=3
不进栈
k=4
不进栈
k=5
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top
1->8
4
3 5
5->2
1
背包容积 T=0
k=5进栈
0 1 2
3 4 5
找到一组解,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
top 1->8
4
3 5 2
1
背包容积 T=0
k=5出栈
0 1 2
3 4 5
栈不空继续找解,不进入内循环,栈顶出栈
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
Stop
8 4
3 5 2
1
背包容积 T=10
k=1出栈后
0 1 2
3 4 5
栈空了，但 k<>n继续找解,进入内循环
k=2(下面该它进栈了 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
继续找解继续找解
… … … …
吐血！！！！
S
top
8 4
3 5
5->2
1
背包容积 T=2
快完了 k=5进栈
0 1 2
3 4 5
脱离内循环,栈顶出栈
k=6(脱离内循环 )
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6
背包问题求解
T=10
S
背包问题求解
top
8 4
3 5 2
1
背包容积 T=10
k=5
0 1 2
3 4 5
终于！栈空了,k==n了，呜呼哀哉！
没有计算机是多么痛苦并快乐的事！
k=6
物品体积 w[i] = { 1,8,4,3,5,2 }
i=0…5,n=6T=10
1
( )
[ 3 8,3 2 ]
{ 0,0 }
2
( 0 )
[ 3 2,2 2 ]
{ 0,0 }
4
( 0 0 )
{ 0,0 }
5
( 0 1 )
{ 4,1 0 }
8
( 0 0 0? )
{ 0,0 }
1 6
( 0 0 0 0 )
{ 0,0 }
9
( 0 0 1? )
{ 6,1 2 }
1 7
( 0 0 0 1 )
{ 9,1 8 }
1 8
( 0 0 1 0 )
{ 6,1 2 }
1 9
( 0 0 1 1 )
{ 1 5,3 0 }
1 0
( 0 1 0? )
{ 4,1 0 }
2 0
( 0 1 0 0 )
{ 4,1 0 }
1 1
( 0 1 1? )
{ 1 0,2 2 }
2 1
( 0 1 0 1 )
{ 1 3,2 8 }
2 2
( 0 1 1 0 )
{ 1 0,2 2 }
2 3
( 0 1 1 1 )
{ 1 9,4 0 }
3
( 1 )
[ 3 8,3 2 ]
{ 2,1 0 }
6
( 1 0 )
{ 2,1 0 }
7
( 1 1 )
{ 6,2 0 }
1 2
( 1 0 0? )
{ 2,1 0 }
2 4
( 1 0 0 0 )
{ 2,1 0 }
1 3
( 1 0 1? )
{ 8,2 2 }
2 5
( 1 0 0 1 )
{ 1 1,2 8 }
2 6
( 1 0 1 0 )
{ 8,2 2 }
2 7
( 1 0 1 1 )
{ 1 7,4 0 }
1 4
( 1 1 0? )
{ 6,2 0 }
2 8
( 1 1 0 0 )
{ 6,2 0 }
1 5
( 1 1 1? )
{ 1 2,3 2 }
2 9
( 1 1 0 1 )
{ 1 5,3 8 }
2 0
( 1 1 1 0 )
{ 1 2,3 2 }
3 1
( 1 1 1 1 )
{ 2 1,5 0 }
★
[ 3 6,2 2 ] [ 3 8,3 2 ]
[ 3 8,3 2 ][ 3 8,3 8 ]
n = 4,m = 1 5
w = { 2,4,6,9 }
p = { 1 0,1 0,1 2,1 8 }
( x
1
x
2
x
3
x
4
)
{ w x,p x }
[ U,L ]
[ 2 0,2 0 ] [ 3 8,3 8 ]
递归定义
1,0)1,(
1,0)1,(
0,00
00
01
),(
nsnwsk n a p
nsnsk n a p
ns
s
s
nsK n a p
n
int knap( int s,int n )
{
if ( s==0 ) return 1;
else if ( s<0 || s>0 && n<1 ) return 0;
else if ( knap(s-w[n-1],n-1) == 1 )
{
printf(“n=%d,w[%d]=%d \n”,n,n-1,w[n-1]);
return 1;
}
else return (knap( s,n-1 ) );
}
非递归程序
struct NodeBag {
int s,n ;
int r ; /* r的值为 1,2,3 */
int k;
};
typedef struct NodeBag DataType;
PSeqStack st;
struct NodeBag x;
void knapsack( int w[],int T,int n )
{
InitStack(S); k = 0;
do {
while( T>0 && k<n ) {
if ( T-w[k]>=0 ) {
Push( S,k );
T -= w[k];
}
k++;
}
if ( T==0 ) StackTraverse( S );
Pop( S,k );
T += w[k];
k++;
} while ( StackEmpty(S) && k==n );
}
限于二元运算符的表达式定义,
表达式,:= (操作数 ) (运算符 ) (操作数 )
操作数,:= 简单变量 | 表达式简单变量,,= 标识符 | 无符号整数例四 表达式求值表达式的三种标识方法：
设 Exp = S1 OP S2
则称 OP S1 S2 为 前缀表示法
S1 S2 OP 为 后缀表示法
S1 OP S2 为 中缀表示法例如,Exp = a? b + (c? d / e)? f
前缀式,+? a b c / d e f
中缀式,a? b + c? d / e? f
后缀式,a b? c d e /? f? +
结论,
1) 操作数之间的相对次序不变 ;
2) 运算符的相对次序不同 ;
3) 中缀式丢失了括弧信息,致使运算的次序不确定 ;
4) 前缀式的运算规则为,连续出现的两个操作数和在它们前且紧靠它们的运算符构成一个最小表达式 ;
5) 后缀式的运算规则为,运算符在式中出现的顺序恰为表达式的运算顺序 ;
每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式 ;
如何从后缀式求值？
先找运算符，再找操作数例如：
a b? c d e /? f? +
a?b d/e
c-d/e
(c-d/e)?f
如何从原表达式求得后缀式？
每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。
分析,原表达式” 和,后缀式”中的运算符,
原表达式,a + b? c? d / e? f
后缀式,a b c? + d e / f
从原表达式求得后缀式的规律为：
1) 设立暂存 运算符 的 栈 ;
2) 设表达式的结束符为,#”,予设 运算符栈的 栈底为,#”
3) 若 当前字符 是操作数,则 直接发送给后缀式 ;
4) 若 当前 运算符的 优先数高 于栈顶运算符，则 进栈 ;
5) 否则，退出栈顶运算符发送给后缀式 ;
6),(” 对它之前后的运算符 起隔离作用,,)”可视为自相应左括弧开始的表达式的结束符。
算法思想
设定两栈,操作符栈 OPTR,操作数栈 OPND
栈初始化,设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 ‘ #?；
依次读入字符,是操作数则入 OPND栈，是操作符则要判断：
if 操作符 < 栈顶元素,则退栈、计算，结果压入 OPND栈；
操作符 = 栈顶元素且不为‘ #?，脱括号（弹出左括号）；
操作符 > 栈顶元素,压入 OPTR栈。
表达式求值中缀表达式 后缀表达式（ RPN)
a*b+c ab*c+
a+b*c abc*+
a+(b*c+d)/e abc*d+e/+
中缀表达式,操作数栈和运算符栈例 计算 2+4-3*6
操作数 运算符
2
4
+
操作数 运算符
6 -
操作数 运算符
6 -
3
6
*
操作数 运算符
6 -
18
操作数 运算符
-12
中缀表达式求值举例
OPTR OPND INPUT OPERATE
3*(7-2)# Push(opnd,’3’)#
*(7-2)#3# Push(optr,’*’)
#,* 3 (7-2)# Push(optr,’(’)
#,*,( 3 7-2)# Push(opnd,’7’)
#,*,( 3,7 -2)# Push(optr,’-’)
#,*,(,－ 3,7 2)# Push(opnd,’2’)
#,*,(,－ 3,7,2 )# Operate(7-2)
#,*,( 3,5 )# Pop(optr)
#,* 3,5 # Operate(3*5)
# 15 # GetTop(opnd)
表达式求值示意图,5+6?(1+2)-4
top
base
OPTR栈
#
OPND栈
top
base
toptop +
top top×
top (
top
top
+
top
toptop
top
top-top
5读入表达式过程,+6× (1+2)-4 #
=19
1+2=3
6× 3=18
5+18=23
23-4=19
6
1
2
3
184
52319
中缀表达式求值后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转 4
3、若是运算符，从栈中弹出 2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值；
若表达式未输入完，转 1
top
4
top
4
3
top
7
3
5
top
例 计算 4+3*5 后缀表达式,435*+
top
4
15 top
19
后缀表达式求值
double evalution ( char suffix[] )
{
ch = *suffix++; InitStack( S );
while ( ch !=,#” ) {
if ( !OpMember(ch) ) Push(S,ch);
else {
Pop( S,b ); Pop( S,a );
Push( S,Operate( a,ch,b ) );
}
ch = *suffix++;
}
Pop( S,result );
return result;
}
运算符 # ( + - ) * / |(乘幂 )
优先级 -1 0 1 1 2 2 2 3
void transform( char suffix[ ],char exp[ ] )
{
InitStack(S); Push(S,?#?);
p = exp; ch = *p; k=0;
while (!StackEmpty(S)) {
if (!OpMember(ch)) Suffix[k++] = ch;
else { }
if ( ch!=?#?) ch = *++p;
} // while
suffix[k] =?\0?;
}
… … switch (ch) {case?(?,Push(S,ch); break;
case?)?,Pop(S,c);
while (c!=?(?) { suffix[k++] = c; Pop(S,c); }
break;
defult,while( Gettop(S,c) && ( precede(c,ch)) )
{ suffix[k++] = c; Pop(S,c); }
if ( ch!=?#?) Push( S,ch);
break;
} // switch
递归的定义例 5 实现递归递归的过程,一个过程直接或间接地调用自己如,0的阶乘是 1,n(n>0)的阶乘等于 n乘上 (n-1)的阶乘线性表的另一种定义,
若元素个数为 0，则称为空表
若元素个数大于 0,则有且仅有一个第一个元素 (即表头 ),
剩余 元素形成一个表 (即表尾 ) 。
递归的对象,一个对象部分地包含它自己，或用它自己给自己定义。 (如某些数据结构的定义 )
递归的应用
–递归定义,如阶乘,Fibonacci数列等
–数据结构,如表、树、二叉树等
–问题求解,如 Hanoi塔例 5 实现递归
将所有的实在参数、返回地址等 信息 传递给被调用函数 保存 ;
为被调用函数的局部变量 分配存储区 ;
将 控制转移 到被调用函数的入口。
当在一个函数的运行期间 调用另一个函数 时，在 运行该被调用函数之前,需先完成三项任务：
从被调用函数 返回 调用函数 之前,应该完成三项任务：
保存 被调函数的 计算结果 ;
释放 被调函数的 数据区 ;
依照被调函数保存的返回地址将 控制转移 到调用函数。
多个函数嵌套调用的规则是,
此时的内存管理实行,栈式管理
”
后调用先返回！
例如：
void main( ) { void a( ) { void b( ) {
… … …
a( ); b( );
… …
} //main } // a } // b main的数据区函数 a的数据区函数 b的数据区递归工作栈,递归过程执行过程中占用的数据区。
递归工作记录,每一层的递归参数合成一个记录。
当前活动记录,栈顶记录指示当前层的执行情况。
当前环境指针,递归工作栈的栈顶指针。
递归函数执行过程可视为同一函数进行嵌套调用,例如：
栈的应用 - 过程的嵌套调用
r
主程序
s
rr
r
s
子过程
1 r
s
t
子过程
2 rs
t 子过程
3
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
输出：
(2) 2
(1) 3
输出：
( ) 1
( ) 2
( ) 3
top
输出,
( ) 3
返回
(3) 1
(2) 2
(1) 3
top (4) 0
结束
void print(int w)
{ int i;
if ( w!=0) {
print(w-1);
for(i=1;i<=w;++i) printf(“%3d,”,w);
printf(“/n”);
}
}
运行结果：
1，
2,2，
3,3,3，
栈与递归的实现
定义是递归的
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘函数的递归算法
long fact ( long n )
{
if ( n == 0 ) return 1; //递归结束条件
else return n*fact (n-1); //递归的规则
}
我们看一下 n=3阶乘函数 fact(n)的执行过程
main( ) {
int n=3,y;
L y= fact(n);
}
调用调用调用
int fact (n) {
if（ n=1） return（ 1） ；
else
L1 return (n*fact (n-1))；
}//fact
n=3 int fact (int n) {
if（ n=1） return 1;
else
L1 return（ n*fact (n-1));
}//fact
n=2
int fact(int n) {
if (n=1) return 1；
else
L1 return (n*fact (n-1))；
}//fact
n=1
L 3
L1 1
L1 2
返回 1
返回 2
返回 6
1
ct 1)ct 1)
ct(n)
返回地址 实参注意递归调用中栈的变化栈与递归的实现主程序 main( ),fact(4)
参数传递递归调用结果返回回归求值
fact(4),
fact(3),
fact(2):
fact(1),
fact(0),
1
直接定值为 1
计算 4*fact(3)
计算 3*fact(2)
计算 2*fact(1)
计算 1*fact(0)
1
2
6
24
[例 ] Ackermann函数 A(n,x,y)的计算
x+1 n=0
x n=1,y=0
0 n=2,y=0
A(n,x,y)= 1 n=3,y=0
2 n>=4,y=0
A(n-1,A(n,x,y-1),x) n!=0,y!=0
A(3,1,2)
=A(2,A(3,1,1),1)
=A(2,A(2,A(3,1,0),1),1)
=A(2,A(2,1,1),1)
=A(2,A(1,A(2,1,0),1),1)
=A(2,A(1,0,1),1)
=A(2,A(0,A(1,0,0),0),1)
=A(2,A(0,0,0),1)
=A(2,1,1)
=A(1,A(2,1,0),1)
=A(1,0,1)
=A(0,A(1,0,0),0)
=A(0,0,0)
计算 Ackermann函数 A(n,x,y)的算法思想可以描述如下：
反复执行：
(1) 递归,只要有 n!=0&&y!=0 则反复执行：
计算 A(n,x,y-1); y--; 并将 (n-1,x)作返回信息进栈；
(2) 返回,计算出递归函数 终点值 v ;
若栈空则结束算法,
否则,出栈一组值，作新参数 (n,y)； v赋给 x；
构造出一个新函数 A(n,x,y)，再递归。
定义递归出口，即 n=0或 y=0时的 Ackermann函数,
int Ackerman( int n,int x,int y )
{
InitStack(S);
e.nval = n; e.xval = x; e.yval = y;
Push( S,e );
do {
GetTop( S,e );
while( e.navl!=0 && e.yval!=0 ) {
e.yval--; Push( S,e );
}
Pop( S,e );
u = value(e.nval,e.xval,e.yval);
if ( !StackEmpty(S) ) {
pop( S,e );
e.nval--;
e.yval = e.xval;
e.xval = =u;
Push( S,e );
}
} while ( !StackEmpty(S) );
return u;
}
typedef struct {
int nval; int xval; int yval;
} Elemtype;
int value( int n,int x,int y )
{
if ( n==0 ) return ( x+1 );
else switch( n ) {
case 1,return x;
case 2,return 0;
case 3,return 1;
default,return 2;
}
}
5.3 队列 ( Queue )
定义队列是只允许在一端删除，在另一端插入的顺序表,允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性先进先出 (FIFO,First In First Out)
常用操作 初始化空队、入队、出队、判断队空、
判断队满、取队头
a0 a1 a2 an-1
front rear
队头入队出队队尾
队列的抽象数据类型定义见教材
队列的存储结构为 链队 或 顺序队 （常用循环顺序队）
插入元素称为 入队 ；删除元素称为 出队 。
1,定 义
4.3.1 队列的结构特点和操作与同线性表相同，仍为一对一关系。
顺序队 或 链队,以循环顺序队更常见。
只能在队首和队尾运算，且访问结点时依照先进先出 （ FIFO） 的原则。
关键是掌握 入队 和 出队 操作，具体实现依顺序队或链队的不同而不同。
基本操作有入队或出队，建空队列，判队空或队满等操作。
3,存储结构
4,运算规则
5,实现方式
2,逻辑结构只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （ 头删尾插 ）
例如：队列 Q = ( a1,a2,a3,……….,an-1,an )
队头 队尾队列的进队和出队原则
进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位臵加入。
出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
队满时再进队将 溢出出错 ；
队空时再出队将 队空处理 。
解决办法之一,将队列元素存放数组首尾相接,
形成 循环 (环形 )队列 。
队列的进队和出队示例
front rear 空队列 front rear A进队
A
front rear B进队
A B
front rear C,D进队
A B C D
front rear A退队
B C D
front rear B退队
C D
front rear E,F,G进队
C D E F G C D E F G
front rear H进队,溢出队列的基本操作
InitQueue(&Q)
操作结果,构造一个空队列 Q。
DestroyQueue(&Q)
初始条件,队列 Q已存在。
操作结果,队列 Q被销毁，不再存在。
QueueEmpty(Q)
初始条件,队列 Q已存在。
操作结果,若 Q为空队列，则返回 TRUE，否则返回 FALSE。
QueueLength(Q)
初始条件,队列 Q已存在。
操作结果,返回 Q的元素个数，即队列的长度。
ClearQueue(&Q)
初始条件,队列 Q已存在。
操作结果,将 Q清为空队列。
a1 a2 an… …
GetHead(Q,&e)
初始条件,Q为非空队列。
操作结果,用 e返回 Q的队头元素。
EnQueue(&Q,e)
初始条件,队列 Q已存在。
操作结果,插入元素 e为 Q的新的队尾元素。
a1 a2 an e … …
DeQueue(&Q,&e)
初始条件,Q为非空队列。
操作结果,删除 Q的队头元素，并用 e返回其值。
a1 a2 an… …
链队列,基本操作的实现
无队满问题 (除非分配不出内存 ),空间可扩充
引入头结点 (一定需要吗？ )
a1 a2 an ^
Q.front
Q.rear
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
队头在链头，队尾在链尾。
链式队列在进队时无队满问题,但 有队空问题 。
队空条件为,front == NULL
4.3.2 队列的表示和操作实现
Q.front
Q.rear
∧
空队列
Q.front
Q.rear
Q.front
Q.rear
Q.front
Q.rear
X ∧
Y ∧X
Y ∧X
元素 X入队列元素 Y入队列元素 X出队列链队列讨论讨论：
① 空队列的特征？
(队尾 )(队首 )
front
a1 a2 a3 ^
rear
p
front
^
rear
③ 怎样实现入队和出队操作？
入队（尾部插入）,rear->next=S; rear=S;
出队（头部删除）,front->next=p->next;
② 队列会满吗？
front=rear
一般不会，因为删除时有 free动作。除非内存不足！
Typedef LinkList QuencePtr;
typedef struct { // 链队列类型
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue;
a1 ∧an…Q.front
Q.front
Q.rear ∧空队列
Q.rear
队列 –链队列的表示与实现
void InitQueue_L( LinkQueue &Q )
{ // 构造一个空队列 Q
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
}
void DestroyQuence_L( LinkQueue &Q )
{ // 销毁链队列结构 Q
while ( Q,front ) {
Q.rear = Q,front->next;
delete Q.front;
Q,front = Q.rear;
}
}
void EnQueue_L( LinkQueue &Q,QElemType e )
{ // 插入元素 e为 Q的新的队尾元素
p = new QNode;
p->data = e; p->next = NULL;
Q.rear->next = p; Q.rear = p;
}
a1 ∧anQ.front
Q.rear
∧e
p
bool DeQueue_L( LinkQueue &Q,QElemType &e )
{
//若队列不空，则删除 Q的队头元素，用 e 返回其值，并返回 TRUE；
//否则返回 FALSE
if (Q.front == Q.rear) return FALSE;
p = Q.front->next; e = p->data;
Q.front->next = p->next;
delete (p);
return OK;
}
if ( Q.rear == p ) Q.rear = Q.front;
null
*q
q.rear x null
q.front
p
存储池循环队列队列的顺序存储约定与类型定义,Q.front和 Q.rear的含义删除,避免大量的移动 ->头指针增 1
问题,假上溢?首尾相接的环（ 钟 ）
队头
Q.front
入队出队
a1 a2 a3 … … an
Q.rear
队尾
2、循环队列基本操作的实现初始化空队,Q.front=Q.rear=0;
入队,判断是否队满；非队满时,Q.rear位置放新插入的元素,Q.rear++
出队,判断是否队空，非队空时,Q.front位置为待删除的元素,Q.front++
队空条件,Q.front == Q.rear
队满条件,Q.rear == MAXQSIZE
问题,假上溢 ()
Q.front
入队出队
a1 a2 a3 … … an
Q.rear
队尾循环队列实现：用一维数组实现 sq[M]
front=-1
rear=-1
1
2
3
4
5
0
队空
1
2
3
4
5
0
front J
1,J1,J3入队
J1
J2
J3rear
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
设两个指针 front,rear,约定：
rear指示队尾元素；
front指示队头元素前一位臵初值 front=rear=-1
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
front
front
front
循环队列当 J6 入队后,队尾指针 Q.rear越界,不可能再插入新的队尾元素,但是另一方面,
队列的实际可用空间并未占满。一个巧妙的办法是,将顺序队列设想为首尾相连的环状空间,当 Q.rear 值超出队列空间的最大位臵时,令 Q.rear= 0,使队列空间能
“循环”使用。这种循环使用空间的队列称为循环队列。
J6
J4
J5
Q.rear
Q.front 3 1
2
4 05
循环队列图示
5
4
3
2
1
0
Q.rear
Q.front
J6
J5
J4
存在问题,设数组维数为 M,则,队首固定，每次出队剩余元素向下移动 ——浪费时间解决方案,循环队列基本思想,把队列 设想成环形,让 sq[0]接在 sq[M-1]之后,
若 rear+1==M,则令 rear=0;
0
M-1
1
front
rear
实现,利用“模”运算入队,rear=(rear+1)%M; sq[rear]=x;
出队,front=(front+1)%M; x=sq[front];
队满、队空判定条件循环队列假上溢的解决办法把顺序队列看成首尾相接的环 (钟表 )-循环队列基本操作的实现
– 入队,Q.rear = ( Q.rear+1)%MAXQSIZE
– 出队,Q.front = ( Q.front+1)%MAXQSIZE
– 队空条件,Q.front == Q.rear
由于出队 Q.front追上了 Q.rear
– 队满条件,Q.front == Q.rear
由于入队 Q.rear追上了 Q.front
问题,队空和队满的判断条件一样循环队列
0
123
4 5
rear
front
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
J4
J5
J6
0
123
4 5
rear
front
初始状态队空,front==rear
队满,front==rear
解决方案：
1,另外 设一个标志 以区别队空、队满
2,少用一个元素空间,
队空,front==rear
队满,(rear+1)%M==front
新问题,在循环队列中，空队特征是 front=rear； 队满时也会有
front=rear； 判决条件将出现二义性！
解决方案有三：
① 加设标志位，让删除动作使其为 1,插入动作使其为 0,则可识别当前 front=rear
② 使用一个计数器记录队列中元素个数（即队列长度）；
③ 人为浪费一个单元，令 队满特征为 front=(rear+1)%N；
循环队列讨论
② 队列会满吗？
很可能会，因为数组前端空间无法释放。因此 数组应当有长度限制。
① 空队列的特征？
约定,front=rear
入队 (尾部插入 ),v[rear]=e; rear++;
出队 (头部删除 ),x=v[front]; front++;
讨论：
假溢出有缺陷
③ 怎样实现入队和出队操作？
J2 J3
J1 J4
J5
front
rear
问 2,在具有 n个单元的循环队列中，
队满时共有多少个元素？ n-1个
6 问 1：上图中队列长度 L=？
队列存放数组被当作首尾相接的表处理。
队头、队尾指针 加 1时从 maxSize -1直接进到 0，可用语言的取模 (余数 )运算实现。
队头指针出,front = (front+1) % maxSize;
队尾指针进,rear = (rear+1) % maxSize;
队列初始化,front = rear = 0;
队空条件,front == rear;
队满条件,(rear+1) % maxSize == front
4,循环队列 (Circular Queue)
队空,Q.front =Q,rear
队满,Q.front =(Q.rear + 1) % maxSize
入队,Q.rear = (Q.rear + 1) % maxSize
出队,Q.front = (front + 1) % maxSize;
求队长,(Q.rear-Q.front+maxSize)%maxSize
#define MAXQSIZE 100 //最大队列长度
const QUENCE_INIT_SIZE = 100;
Const QUENCEINCREMENTSIZE = 10;
typedef struct {
QElemType *elem; // 动态分配存储空间
int front; //头指针,若队列不空,指向队列头元素
int rear; //尾指针,若队列不空,指向队列尾元素 的下一个位置
int queuesize;
int incrementsize;
} SqQueue;
循环队列
void InitQueue_Sq(SqQueue &Q,int maxsize=QUENCE_INIT_SIZE,
int incresize = QUENCEINCREMENT) {
//构造一个最大存储空间为 maxsize 的空循环队列 Q
Q.elem = new QElemType[maxsize+1];
Q.queuesize = maxsize;
Q.incrementsize = incresize;
Q.front = Q.rear = 0;
}
int QuenceLength(SqQueue Q)
{
//返回 Q的元素个数，即队列的长度
return (Q.rear-Q.front+Q.quencesize)%Q.quencesize;
}
Status DeQueue (SqQueue &Q,QElemType &e) {
// 若队列不空，则删除 Q的队头元素，
// 用 e返回其值，并返回 TRUE; 否则返回 FALSE
if (Q.front == Q.rear) return FALSE;
e = Q.elem[Q.front];
Q.front = (Q.front+1) % Q.queuesize;
return TRUE;
}
void EnQueue (SqQueue &Q,QElemType e)
{
// 插入元素 e为 Q的新的队尾元素
if ((Q.rear+1) % Q.queuesize == Q.front)
incrementQuencesize(Q);
Q.elem[Q.rear] = e;
Q.rear = (Q.rear+1) % Q.queuesize;
return OK;
}
J6 J5
J7
J8 J9
例：一循环队列如下图所示，若先删除 4个元素，接着再插入 4个元素，请问队头和队尾指针分别指向哪个位置?
J2 J3
J1 J4
J5
front
rear
解,由图可知，队头和队尾指针的初态分别为 front=1和 rear=6。
front
rear
删除 4个元素后 front=5；再插入 4个元素后,r=(6+4)%6=4
front front
front
front
问：什么叫,假溢出,？如何解决？
答,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位臵，这就叫,假溢出,。
解决假溢出的途径 —采用循环队列例：数组Ｑ [n]用来表示一个循环队列,f 为当前队列头元素的前一位置,r 为队尾元素的位置。假定队列中元素的个数小于 n，计算队列中元素的公式为,
（Ａ） r－ f （Ｂ）（ n＋ f－ r） % n
（Ｃ） n＋ r－ f （Ｄ） （ n＋ r－ f） % n
4种公式哪种合理？
当 r ≥f时 （ A） 合理；
当 r < f 时 （ C） 合理；
分析：
综合 2种情况，以（ D）的表达最为合理例,在一个循环队列中，若约定队首指针指向队首元素的 前一个位置。那么，从循环队列中删除一个元素时，其操作是先,后 。移动队首指针 取出元素
√
问,为什么要设计队列？它有什么独特用途？
1,离散事件的模拟（模拟事件发生的先后顺序）；
2,操作系统中多道作业的处理（一个 CPU执行多个作业）；
3,简化程序设计。
答：
第 1 行 1 1
第 2 行 1 2 1
第 3 行 1 3 3 1
第 4 行 1 4 6 4 1
二项式系数值（杨辉三角）
设第 i-1行的值,(a[0]=0) a[1]..a[i] (a[i+1]=0)
则第 i 行的值,b[j] = a[j-1]+a[j],j=1,2,…,i+1
1、计算 n 行杨辉三角的值
4.4 队列应用举例利用循环队列计算二项式的过程：
假设只计算三行，则队列的最大容量为 5。
1 1 00
q.front q.rear
1 1 00 1
q.frontq.rear
1 1 02 1
q.frontq.rear
1 1 02 1
q.frontq.rear
1 0 02 1
q.frontq.rear
1 0 12 1
q.frontq.rear
1 0 12 1
q.frontq.rear
1 0 12 3
q.frontq.rear
1 0 13 3
q.frontq.rear
1 0 13 3
q.frontq.rear
do {
DeQueue(Q,s);
GetHead(Q,e);
if (e!=0) printf (“%d”,e);
EnQueue(Q,s+e);
} while (e!=0);
void yanghui( int n )
{
SqQuence Q;
for ( i=1; i<=n; i++ ) cout <<;
cout <<?1? << endl;
InitQuence_Sq( Q,n+1 );
EnQuence_Sq( Q,0 ); EnQuence_Sq( Q,1 ); EnQuence_Sq( Q,1 );
k = 1;
while ( k<n ) {
for ( i=1; i<=n-k; i++ ) cout <<;
EnQuence_Sq( Q,0 );
do {
DeQuence_Sq( Q,s ); GetHead)Sq( Q,e );
if ( e ) cout << e <<; else cout << endl;
EnQuence_Sq( Q,s+e );
} while ( e!=0 );
k++
}
DeQuence_Sq( Q,e );
while ( !QuenceEmpty(Q) ) { DeQuence_Sq( Q,e ); cout << e <<; }
}
算法某运动会设立 N个比赛项目,每个运动员可以参加一至三个项目 。 试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行,又使总的竞赛日程最短 。
若将此问题抽象成数学模型，则归属于,划分子集,问题。 N
个比赛项目构成一个大小为 n 的集合，有同一运动员参加的项目则抽象为,冲突,关系。
2,,划分无冲突子集问题,求解例如：某运动会设有 9 个项目,A = { 0,1,2,3,4,5,6,7,8 }，
七名运动员报名参加的项目分别为：
(1,4,8),(1,7),(8,3),(1,0,5),(3,4),(5,6,2),(6,4)
它们之间的冲突关系为,
R = { (1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4) }
将集合 A划分成 k个互不相交的子集
A1,A2,…,Ak（ k≤n ）,
使同一子集中的元素均无冲突关系,并要求划分的子集数目尽可能地少 。
“划分子集,问题即为,
对前述例子而言，问题即为,同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。
可利用,过筛,的方法来解决划分子集问题。从第一个元素考虑起,凡不和第一个元素发生冲突的元素都可以和它分在同一子集中,然后再,过筛,出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止
。为了减少重复察看 R 数组的时间，可另设一个数组 clash[n] 记录和当前已入组元素发生冲突的元素的信息。每次新开辟一组时，
令 clash 数组各分量的值均为,0”，当序号为,i”的元素入组时，
将和该元素发生冲突的信息记入 clash 数组。
0 1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0 0 0
1 1 0 0 0 1 1 0 1 1
2 0 0 0 0 0 1 1 0 0
3 0 0 0 0 1 0 0 0 1
4 0 1 0 1 0 0 1 0 1
5 1 1 1 0 0 0 1 0 0
6 0 0 1 0 1 1 0 0 0
7 0 1 0 0 0 0 0 0 0
8 0 1 0 1 1 0 0 0 0
012345678
14568
458
8
1 2 11 12
pre (前一个出队列的元素序号 ) = n; 组号 = 0;
全体元素入队列 ;
while ( 队列不空 ) {
队头元素 i出队列 ;
if ( i < pre ) // 开辟新的组
{ 组号 ++; clash 数组初始化 ; }
if ( i 能入组 ) {
i 入组,记下序号为 i 的元素所属组号 ;
修改 clash 数组 ;
}
else i 重新入队列 ;
pre = i;
}
划分子集算法的基本思想问题描述,已知集合 A={a1,a2,……a n},及集合上的关系
R={ (ai,aj) | ai,aj?A,i?j},其中 (ai,aj)表示 ai与 aj间存在冲突关系。
要求将 A划分成 互不相交 的子集 A1,A2,……Ak,(k?n),使任何子集中的元素均无冲突关系，同时要求 分子集个数尽可能少例 A={1,2,3,4,5,6,7,8,9}
R={ (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),
(3,7),(6,3) }
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
划分子集问题所用数据结构
–冲突关系矩阵,r[i][j]=1,i,j有冲突
r[i][j]=0,i,j无冲突
–循环队列 cq[n]
–数组 result[n]存放每个元素分组号
–工作数组 newr[n]
算法思想,利用 循环筛选 。从第一个元素开始，
凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组划分子集问题工作过程
1,初始状态,A中元素放于 cq中,result和 newr数组清零，组号 group=1
2,第一个元素出队，将 r矩阵中第一行,1”拷入 newr
中对应位臵，这样，凡与第一个元素有冲突的元素在 newr中对应位臵处均为,1”,下一个元素出队
3,若其在 newr中对应位臵为,1”，有冲突，重新插入 cq队尾，参加下一次分组
4,若其在 newr中对应位臵为,0”,无冲突，可划归本组；再将 r矩阵中该元素对应行中的,1”拷入 newr
中
5,如此反复，直到 9个元素依次出队，由 newr中为,0”
的单元对应的元素构成第 1组,将组号 group值,1”
写入 result对应单元中
6,令 group=2,newr清零，对 cq中元素重复上述操作，
直到 cq中 front==rear,即队空,运算结束。
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
初始
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 0 1 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 0 1 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
2 5 6 7 8 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 0 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
2 5 6 7 9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 0 1 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 0 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
5 6 7 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
6 7 9 5
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
7 9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 0 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 0 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 5 6
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
5 6 9
0 1 2 3 4 5 6 7 8
cq
f r
1 0 1 0 1 1 0 1 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 0 0 2 1 0
0 1 2 3 4 5 6 7 8
result
6 9
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
9 6
0 1 2 3 4 5 6 7 8
cq
f r
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
9 6
0 1 2 3 4 5 6 7 8
cq
fr
0 1 0 1 0 1 1 0 1
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 0 2 1 0
0 1 2 3 4 5 6 7 8
result
9
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 0 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 0
0 1 2 3 4 5 6 7 8
result
R = { (2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3) }
0 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0 1
0 1 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 1 1
R=
0 1 2 3 4 5 6 7 8
cq
fr
0 1 1 1 1 0 1 0 0
0 1 2 3 4 5 6 7 8
newr
1 2 1 1 3 4 2 1 4
0 1 2 3 4 5 6 7 8
result
可行的子集划分为：
A1={ 1,3,4,8 }
A2={ 2,7 }
A3={ 5 }
A4={ 6,9 }
void division ( int R[ ][ ],int n,int result [ ] ) {
// 已知 R[n][n] 是编号为 0 至 n-1 的 n 个元素的关系矩阵，子集划分的
//结果记入 result 数组,result[k] 的值是编号为 k 的元素所属组号
pre = n; group = 0;
InitQueue_Sq ( Q,n ); // 设置最大容量为 n 的空队列
for ( e = 0; e < n; e++ ) EnQueue_Sq ( Q,e,0 );
while ( !QueueEmpty ( Q ) ) {
DeQueue_Sq ( Q,i );
if ( i < pre ) {
group ++; // 增加一个新的组
for ( j = 0; j < n; j ++ ) clash[j] = 0;
}
if ( clash[i] == 0 ) {
result[i] = group; // 编号为 i 的元素入 group 组
for ( j = 0; j < n; j ++ ) clash[j] += R[i][j]; // 添加和 i冲突的信息
}
else EnQueue ( Q,i,0 ); // 编号为 i 的元素不能入当前组
pre = i;
} // while
} // division
讨论线性表、栈与队的异同点相同点,逻辑结构相同,都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表,即受限的线性表 （ 只是对插入,删除运算加以限制 ） 。
不同点：
① 运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入和删除运算,因而是后进先出表 LIFO；
队列是只允许在一端进行插入,另一端进行删除运算,
因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调用、
递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。
1,掌握栈和队列类型的特点,并能在相应的应用问题中正确选用它们 。
2,熟练掌握栈类型的两种实现方法,特别应注意栈满和栈空的条件以及它们的描述方法 。
3,熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法 。
4,理解递归算法执行过程中栈的状态变化过程 。
总结
