? 栈
? 表达式求值
? 队列
? 优先队列
? 只允许在一端插入和删除的线性表
? 允许插入和删除
的一端称为 栈顶
(top)，另一端称
为 栈底 (bottom)
? 特点
后进先出 (LIFO)
栈 ( Stack )
退栈 进栈
a0
an-1
an-2
?
top
bottom
template <class Type> class Stack {
public:
Stack ( int = 10 ); //构造函数
void Push ( Type& item); //进栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ); //置空栈
int IsEmpty ( ) const; //判栈空否
int IsFull ( ) const; //判栈满否
}
栈的抽象数据类型
#include <assert.h>
template <class Type> class Stack {
private:
int top; //栈顶指针
Type *elements; //栈元素数组
int maxSize; //栈最大容量
public:
Stack ( int = 10 ); //构造函数
~Stack ( ) { delete [ ] elements; }
void Push ( Type & item ); //进栈
栈的数组表示 — 顺序栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶
void MakeEmpty ( ) { top = -1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
int IsFull ( ) const
{ return top == maxSize-1; }
}
template <class Type> Stack<Type>,:
Stack ( int s ), top (-1),maxSize (s) {
elements = new Type[maxSize];
assert ( elements != NULL ); //断言
}
top 空栈
top top
toptop
top
a 进栈 b 进栈
a ab
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e
e 退栈
c
top
c 退栈 b 退栈
ab
a
a 退栈 空 栈
top
ab
d
d 退栈
c
top
ab
c
top
top
template <class Type> void Stack<Type>,:
Push ( Type & item ) {
assert ( !IsFull ( ) ); //先决条件断言
elements[++top] = item; //加入新元素
}
template <class Type> int stack<Type>,:
Pop ( ) {
if ( IsEmpty ( ) ) return 0; //栈空不退栈
top--; return 1; //退出栈顶元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top]; //取出栈顶元素
}
双栈共享一个栈空间
b[0] t[0] t[1] b[1]
0 maxSize-1
V
栈的链接表示 — 链式栈
? 链式栈无栈满问题，空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
top
template <class Type> class Stack;
template <class Type> class StackNode {
friend class Stack<Type>;
private,
Type data; //结点数据
StackNode<Type> *link; //结点链指针
public:
StackNode ( Type d = 0,StackNode<Type>
*l = NULL ), data ( d ),link ( l ) { }
};
链式栈 (LinkedStack)类的定义
template <class Type> class Stack {
private:
StackNode<Type> *top; //栈顶指针
public:
Stack ( ), top ( NULL ) { }
~Stack ( );
void Push ( const Type & item); //进栈
int Pop ( ); //退栈
Type *GetTop ( ); //读取栈顶元素
void MakeEmpty ( ); //实现与 ~Stack( )同
int IsEmpty ( ) { return top == NULL; }
}
template <class Type> Stack<Type>,:
~Stack ( ) {
StackNode<Type> *p;
while ( top != NULL ) //逐结点回收
{ p = top; top = top->link; delete p; }
}
template <class Type> void Stack<Type>,:
Push ( const Type &item ) {
top = new StackNode<Type> ( item,top );
//新结点链入 *top之前,并成为新栈顶
}
template <class Type> int Stack<Type>,:
Pop ( ) {
if ( IsEmpty ( ) ) return 0;
StackNode<Type> *p = top;
top = top->link; //修改栈顶指针
delete p; return 1; //释放
}
template <class Type> Type Stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) );
return top->data;
}
表达式求值
? 一个表达式由 操作数 (亦称运算对象 ),操
作符 (亦称运算符 )和 分界符 组成 。
? 算术表达式有三种表示：
? 中缀 (infix)表示
<操作数 > <操作符 > <操作数 >,如 A+B；
? 前缀 (prefix)表示
<操作符 > <操作数 > <操作数 >,如 +AB；
? 后缀 (postfix)表示
<操作数 > <操作数 > <操作符 >,如 AB+；
表达式的中缀表示
a + b * ( c - d ) - e ^ f / g
? 表达式中相邻两个操作符的计算次序为：
? 优先级高的先计算 ；
? 优先级相同的自左向右计算 ；
? 当使用括号时从最内层括号开始计算 。
rst1
rst2
rst3
rst4
rst5
rst6
C++中操作符的优先级
优先级 操作符
1 单目 -、！
2 *,/,%
3 +,-
4 <,<=,>,>=
5 ==,!=
6 &&
7 ||
? 一般表达式的操作符有 4种类型,
1 算术操作符 如双目操作符（ +,-、
*,/ 和 %）以及单目操作符（ -）。
2 关系操作符 包括 <,<=,==,!=、
>=,>。这些操作符主要用于比较。
3 逻辑操作符 如与 (&&)、或 (||)、非
(!)。
4 括号‘ (?和‘ )? 它们的作用是改变
运算顺序。
应用后缀表示计算表达式的值
? 从左向右顺序地扫描表达式, 并用一个
栈 暂存扫描到的 操作数 或 计算结果 。
? 在后缀表达式的计算顺序中已 隐含了加
括号的优先次序, 括号在后缀表达式中
不出现 。
? 计算例 a b c d - * + e f ^ g / -
rst1
rst2
rst3
rst4
rst5
rst6
通过后缀表示计算表达式值的过程
? 顺序扫描表达式的每一项，根据它的类
型做如下相应操作：
? 若该项是 操作数,则将其 压栈 ；
? 若该项是 操作符 <op>，则 连续从栈中
退出两个操作数 Y和 X,形成运算指令
X<op>Y，并将计算结果重新 压栈 。
? 当表达式的所有项都扫描并处理完后，
栈顶存放的就是最后的计算结果。
步 输入 类 型 动 作 栈内容
1 置空栈 空
2 A 操作数 进栈 A
3 B 操作数 进栈 AB
4 C 操作数 进栈 A B C
5 D 操作数 进栈 A B C D
6 - 操作符 D, C 退栈,计算
C - D,结果 r1 进栈
A B r 1
7 * 操作符 r1, B 退栈,计算
B* r 1,结果 r2 进栈
A r 2
8 + 操作符 r2, A 退栈,计算
A * r 2,结果 r3 进栈
r3
步 输入 类 型 动 作 栈内容
9 E 操作数 进栈 r 3 E
10 F 操作数 进栈 r 3 E F
11 ^ 操作符 F, E 退栈,计算
E ^ F,结果 r4 进栈
r 3 r 4
12 G 操作数 进栈 r 3 r 4 G
13 / 操作符 G, r4 退栈,计算
r 4 / E,结果 r5 进栈
r 3 r 5
14 + 操作符 r5, r3 退栈,计算
r 3 + r 5,结果 r6 进栈
r6
void Calculator,,Run ( ) {
char ch; double newoperand;
while ( cin >> ch,ch != ‘=’ ) {
switch ( ch ) {
case ‘+’, case ‘-’, case ‘*’, case ‘/’,
DoOperator ( ch ); break; //计算
default, cin.putback ( ch );
//将字符放回输入流
cin >> newoperand; //读操作数
AddOperand ( newoperand );
}
}
}
利用栈将中缀表示转换为后缀表示
? 使用栈可将表达式的中缀表示转换成它
的前缀表示和后缀表示 。
? 为了实现这种转换, 需要考虑各操作符
的优先级 。
各个算术操作符的优先级
? isp叫做栈内 (in stack priority)优先数
? icp叫做栈外 (in coming priority)优先数 。
? 操作符优先数相等的情况只出现在 括号
配对 或 栈底的, ;”号与输入流最后的, ;”
号配对 时 。
操作符 ch ; ( ^ *,/,% +,- )
i s p ( 栈内 ) 0 1 7 5 3 8
i c p ( 栈外 ) 0 8 6 4 2 1
中缀表达式转换为后缀表达式的算法
? 操作符栈初始化, 将结束符 ‘ ;?进栈 。 然
后读入中缀表达式字符流的首字符 ch。
? 重复执行以下步骤, 直到 ch = ?;?,同时
栈顶的操作符也是 ‘ ;?,停止循环 。
? 若 ch是 操作数 直接输出, 读入下一个
字符 ch。
? 若 ch是 操作符, 判断 ch的优先级 icp和
位于栈顶 的 操作符 op的优先级 isp：
? 若 icp (ch) > isp (op),令 ch进栈, 读入
下一个字符 ch。
? 若 icp (ch) < isp (op),退栈并输出 。
? 若 icp (ch) == isp (op),退栈但不输出,
若退出的是, (”号读入下一个字符 ch。
? 算法结束，输出序列即为所需的后缀表
达式。
void postfix ( expression e ) {
stack<char> s; char ch,op;
s.Push ( ‘;’ ); cin.Get ( ch );
while ( ! s.IsEmpty( ) && ch != ';' )
if ( isdigit ( ch ) )
{ cout << ch; cin.Get ( ch ); }
else {
if ( isp ( s.GetTop( ) ) < icp ( ch ) )
{ s.Push ( ch ); cin.Get ( ch ); }
else if ( isp ( s.GetTop( ) ) > icp ( ch ) )
{ op = s.GetTop ( ); s.Pop( );
cout << op; }
else { op = s.GetTop ( ); s.Pop( );
if ( op == ‘(’ ) cin.Get ( ch ); }
}
}
中缀算术表达式求值
? 使用两个栈, 操作符栈 OPTR (operator)，
操作数栈 OPND(operand)，
? 对中缀表达式求值的一般规则：
(1) 建立并初始化 OPTR栈和 OPND栈,
然后 在 OPTR栈中压入一个, ;”
(2) 从头扫描中缀表达式, 取一字符送入
ch。
(3) 当 ch !=,;” 时,执行以下工作,否则结
束算法 。 此时在 OPND栈 的栈顶得到
运算结果 。
① 若 ch是 操作数, 进 OPND栈, 从中缀
表达式取下一字符送入 ch；
② 若 ch是 操作符, 比较 icp(ch)的优先级
和 isp(OPTR)的优先级：
? 若 icp(ch) > isp(OPTR),则 ch进 OPTR
栈, 从中缀表达式取下一字符送入 ch；
? 若 icp(ch) < isp(OPTR),则从 OPND栈
退出 a2和 a1,从 OPTR栈 退出 θ,形成运
算指令 (a1)θ(a2),结果进 OPND栈 ；
?若 icp(ch) == isp(OPTR) 且 ch ==,)”，
则从 OPTR栈 退出栈顶的, (”,对消括号,
然后从中缀表达式取下一字符送入 ch；
队列 ( Queue )
? 定义
? 队列是只允许在一端删除，在另一端插
入的顺序表
? 允许删除的一端叫做队头 (front)，允许
插入的一端叫做队尾 (rear)。
? 特性
? 先进先出 (FIFO,First In First Out)
a0 a1 a2 an-1
front rear
??
template <class Type> class Queue {
public,
Queue ( int = 10 ); //构造函数
void EnQueue ( const Type& item); //进队
Type DeQueue ( ); //出队列
Type GetFront ( ); //取队头元素值
void MakeEmpty ( ); //置空队列
int IsEmpty ( ) const ; //判队列空否
int IsFull ( ) const; //判队列满否
}
队列的抽象数据类型
队列的进队和出队
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进 队,溢出
队列的进队和出队原则
? 进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
? 出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
? 队满时再进队将 溢出出错 ；
? 队空时再出队将 队空处理 。
? 解决办法之一：将队列元素存放数组首尾
相接，形成 循环 (环形 )队列 。
? 队列存放数组被当作首尾相接的表处理。
? 队头、队尾指针 加 1时从 maxSize -1直接进
到 0，可用语言的取模 (余数 )运算实现。
?队头指针进 1,front = (front+1) % maxSize;
?队尾指针进 1,rear = (rear+1) % maxSize;
?队列初始化,front = rear = 0;
?队空条件,front == rear;
?队满条件,(rear+1) % maxSize == front
循环队列 (Circular Queue)
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 frontrear
A A
BCrear
rear空队列 A进 队 B,C进 队
0
1
23
4
5
6 7
0
1
23
4
5
6 7
A退 队 B退 队
0
1
23
4
5
6 7
D,E,F,G,H进 队
frontBCrear
A
front
BC
rear front
C
rear
D
E
F G
H
#include <assert.h>
template <class Type> class Queue {
private:
int rear,front; //队尾,队头指针
Type *elements; //队列元素数组
int maxSize; //最大元素个数
public,
Queue ( int = 10 );
~Queue ( ) { delete [ ] elements; }
void EnQueue ( const Type & item); //进队
循环队列的类定义
int DeQueue ( ); //退队
Type *GetFront ( ); //取队头元素
void MakeEmpty ( ) { front = rear = 0; }
int IsEmpty ( ) const
{ return front == rear; }
int IsFull ( ) const
{ return (rear+1) % maxSize == front; }
int Length ( ) const
{ return (rear-front+maxSize) % maxSize;}
}
template <class Type>
Queue<Type>:,Queue ( int sz ),
front (0),rear (0),maxSize (sz) {
elements = new Type[maxSize];
assert ( elements != NULL );
}
template <class Type> void Queue<Type>::
EnQueue ( const Type & item ) {
assert ( !IsFull ( ) );
rear = (rear+1) % MaxSize;
elements[rear] = item;
}
template <class Type>
int Queue<Type>,,DeQueue ( ) {
if ( IsEmpty ( ) ) return 0;
front = ( front+1) % MaxSize;
return 1;
}
template <class Type>
Type Queue<Type>,,GetFront ( ) {
assert ( !IsEmpty ( ) );
return elements[( front+1) % MaxSize];
}
队列的链接表示 — 链式队列
? 队头在链头，队尾在链尾。
? 链式队列在进队时无队满问题，但有队
空问题。
? 队空条件为 front == NULL
front
rear
template <class Type> class Queue;
template <class Type> class QueueNode {
friend class Queue<Type>;
private:
Type data; //队列结点数据
QueueNode<Type> *link; //结点链指针
public:
QueueNode ( Type d=0,QueueNode<Type>
*l = NULL ), data (d),link (l) { }
};
链式队列类的定义
template <class Type> class Queue {
private:
QueueNode<Type> *front,*rear;
//队头、队尾指针指针
public,
Queue ( ), rear ( NULL ),front ( NULL ) { }
~Queue ( );
void EnQueue ( const Type & item );
int DeQueue ( );
Type *GetFront ( );
void MakeEmpty ( ); //实现与 ~Queue( )同
int IsEmpty ( ) const
{ return front == NULL; }
};
template <class Type>
Queue<Type>,,~Queue ( ) {
//队列的析构函数
QueueNode<Type> *p;
while ( front != NULL ) { //逐个结点释放
p = front; front = front->link; delete p;
}
}
template <class Type>
void Queue<Type>,,
EnQueue ( const Type& item ) {
//将新元素 item插入到队列的队尾
if ( front == NULL ) //创建第一个结点
front = rear = new QueueNode
<Type> ( item,NULL );
else //队列不空,插入
rear = rear->link = new QueueNode
<Type> ( item,NULL );
}
template <class Type>
int Queue<Type>,,DeQueue ( ) {
if ( IsEmpty ( ) ) return 0; //判队空
QueueNode<Type> *p = front;
front = front->link; delete p;
return 1;
}
template <class Type>
Type *Queue<Type>,,GetFront ( ) {
if ( IsEmpty( ) ) return NULL;
return & front->data;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列的应用举例 — 逐行打印
二项展开式 (a + b)i 的系数
分析第 i 行元素与第 i+1行元素的关系
从前一行的数据可以计算下一行的数据
i = 2
i = 3
i = 4
0 1 3 3 1 0
1 4 6 4 1
0 1 2 1 0
0 1 1 0
s t
s+t
从第 i 行数据计算并存放第 i+1 行数据
1 2 1 0 1 3 3 1 0 1 4 6
s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1
s+t s=t s=t s=t s=t s=t s=t s=t s=t
s+t s+t s+t s+t s+t s+t s+t s+t
利用队列打印二项展开式系数的程序
#include <stdio.h>
#include <iostream.h>
#include "queue.h"
void YANGVI ( int n ) {
Queue q; //队列初始化
q.MakeEmpty ( );
q.EnQueue (1); q.EnQueue (1);
int s = 0;
for ( int i = 1; i <= n; i++ ) { //逐行计算
cout << endl;
q.EnQueue (0);
for ( int j = 1; j <= i+2; j++ ) { //下一行
int t = q.DeQueue ( );
q.EnQueue ( s + t );
s = t;
if ( j != i+2 ) cout << s << ' ';
}
}
}
任务编号 1 2 3 4 5
优先权 2 0 0 4 0 3 0 1 0
执行顺序 3 1 5 4 2
优先级队列 (Priority Queue)
? 优先级队列 每次从队列中取出的是具
有最高优先权的元素
? 如下表：任务优先权及执行顺序的关系
数字越小，优先权越高
#include <assert.h>
#include <iostream.h>
#include <stdlib.h>
const int maxPQSize = 50; //缺省元素个数
template <class Type> class PQueue {
private:
Type *pqelements; //存放数组
int count; //队列元素计数
public:
优先队列的类定义
PQueue ( );
~PQueue ( ) { delete [ ] pqelements; }
void Insert ( const Type& item );
int RemoveMin ( );
Type * GetFront ();
void MakeEmpty ( ) { count = 0; }
int IsEmpty ( ) const { return count == 0; }
int IsFull ( ) const
{ return count == maxPQSize; }
int Length ( ) const { return count; }
}
template <class Type> PQueue<Type>,:
PQueue ( ), count (0) {
pqelements = new Type[maxPQSize];
assert ( pqelements != NULL );
}
template <class Type>
void PQueue<Type>,:
Insert ( const Type& item ) {
assert ( !IsFull ( ) ); //判队满断言
优先队列部分成员函数的实现
for ( int j = count-1; j >= 0; j-- )
if ( pqelements[j] <= item ) break;
else pqelements[j+1] = pqelements[j];
pqelements[j+1] = item; count++;
}
template <class Type>
int PQueue<Type>,,RemoveMin ( ) {
if ( IsEmpty ( ) ) return 0;
for ( int i = 1; i < count; i++ )
pqelements[i-1] = pqelements[i];
count--; return 1;
}
template <class Type>
Type PQueue<Type>,,GetFront ( ) {
if ( IsEmpty ( ) ) return NULL;
else return pqelements[0];
}
? 表达式求值
? 队列
? 优先队列
? 只允许在一端插入和删除的线性表
? 允许插入和删除
的一端称为 栈顶
(top)，另一端称
为 栈底 (bottom)
? 特点
后进先出 (LIFO)
栈 ( Stack )
退栈 进栈
a0
an-1
an-2
?
top
bottom
template <class Type> class Stack {
public:
Stack ( int = 10 ); //构造函数
void Push ( Type& item); //进栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ); //置空栈
int IsEmpty ( ) const; //判栈空否
int IsFull ( ) const; //判栈满否
}
栈的抽象数据类型
#include <assert.h>
template <class Type> class Stack {
private:
int top; //栈顶指针
Type *elements; //栈元素数组
int maxSize; //栈最大容量
public:
Stack ( int = 10 ); //构造函数
~Stack ( ) { delete [ ] elements; }
void Push ( Type & item ); //进栈
栈的数组表示 — 顺序栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶
void MakeEmpty ( ) { top = -1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
int IsFull ( ) const
{ return top == maxSize-1; }
}
template <class Type> Stack<Type>,:
Stack ( int s ), top (-1),maxSize (s) {
elements = new Type[maxSize];
assert ( elements != NULL ); //断言
}
top 空栈
top top
toptop
top
a 进栈 b 进栈
a ab
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e
e 退栈
c
top
c 退栈 b 退栈
ab
a
a 退栈 空 栈
top
ab
d
d 退栈
c
top
ab
c
top
top
template <class Type> void Stack<Type>,:
Push ( Type & item ) {
assert ( !IsFull ( ) ); //先决条件断言
elements[++top] = item; //加入新元素
}
template <class Type> int stack<Type>,:
Pop ( ) {
if ( IsEmpty ( ) ) return 0; //栈空不退栈
top--; return 1; //退出栈顶元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top]; //取出栈顶元素
}
双栈共享一个栈空间
b[0] t[0] t[1] b[1]
0 maxSize-1
V
栈的链接表示 — 链式栈
? 链式栈无栈满问题，空间可扩充
? 插入与删除仅在栈顶处执行
? 链式栈的栈顶在链头
? 适合于多栈操作
top
template <class Type> class Stack;
template <class Type> class StackNode {
friend class Stack<Type>;
private,
Type data; //结点数据
StackNode<Type> *link; //结点链指针
public:
StackNode ( Type d = 0,StackNode<Type>
*l = NULL ), data ( d ),link ( l ) { }
};
链式栈 (LinkedStack)类的定义
template <class Type> class Stack {
private:
StackNode<Type> *top; //栈顶指针
public:
Stack ( ), top ( NULL ) { }
~Stack ( );
void Push ( const Type & item); //进栈
int Pop ( ); //退栈
Type *GetTop ( ); //读取栈顶元素
void MakeEmpty ( ); //实现与 ~Stack( )同
int IsEmpty ( ) { return top == NULL; }
}
template <class Type> Stack<Type>,:
~Stack ( ) {
StackNode<Type> *p;
while ( top != NULL ) //逐结点回收
{ p = top; top = top->link; delete p; }
}
template <class Type> void Stack<Type>,:
Push ( const Type &item ) {
top = new StackNode<Type> ( item,top );
//新结点链入 *top之前,并成为新栈顶
}
template <class Type> int Stack<Type>,:
Pop ( ) {
if ( IsEmpty ( ) ) return 0;
StackNode<Type> *p = top;
top = top->link; //修改栈顶指针
delete p; return 1; //释放
}
template <class Type> Type Stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) );
return top->data;
}
表达式求值
? 一个表达式由 操作数 (亦称运算对象 ),操
作符 (亦称运算符 )和 分界符 组成 。
? 算术表达式有三种表示：
? 中缀 (infix)表示
<操作数 > <操作符 > <操作数 >,如 A+B；
? 前缀 (prefix)表示
<操作符 > <操作数 > <操作数 >,如 +AB；
? 后缀 (postfix)表示
<操作数 > <操作数 > <操作符 >,如 AB+；
表达式的中缀表示
a + b * ( c - d ) - e ^ f / g
? 表达式中相邻两个操作符的计算次序为：
? 优先级高的先计算 ；
? 优先级相同的自左向右计算 ；
? 当使用括号时从最内层括号开始计算 。
rst1
rst2
rst3
rst4
rst5
rst6
C++中操作符的优先级
优先级 操作符
1 单目 -、！
2 *,/,%
3 +,-
4 <,<=,>,>=
5 ==,!=
6 &&
7 ||
? 一般表达式的操作符有 4种类型,
1 算术操作符 如双目操作符（ +,-、
*,/ 和 %）以及单目操作符（ -）。
2 关系操作符 包括 <,<=,==,!=、
>=,>。这些操作符主要用于比较。
3 逻辑操作符 如与 (&&)、或 (||)、非
(!)。
4 括号‘ (?和‘ )? 它们的作用是改变
运算顺序。
应用后缀表示计算表达式的值
? 从左向右顺序地扫描表达式, 并用一个
栈 暂存扫描到的 操作数 或 计算结果 。
? 在后缀表达式的计算顺序中已 隐含了加
括号的优先次序, 括号在后缀表达式中
不出现 。
? 计算例 a b c d - * + e f ^ g / -
rst1
rst2
rst3
rst4
rst5
rst6
通过后缀表示计算表达式值的过程
? 顺序扫描表达式的每一项，根据它的类
型做如下相应操作：
? 若该项是 操作数,则将其 压栈 ；
? 若该项是 操作符 <op>，则 连续从栈中
退出两个操作数 Y和 X,形成运算指令
X<op>Y，并将计算结果重新 压栈 。
? 当表达式的所有项都扫描并处理完后，
栈顶存放的就是最后的计算结果。
步 输入 类 型 动 作 栈内容
1 置空栈 空
2 A 操作数 进栈 A
3 B 操作数 进栈 AB
4 C 操作数 进栈 A B C
5 D 操作数 进栈 A B C D
6 - 操作符 D, C 退栈,计算
C - D,结果 r1 进栈
A B r 1
7 * 操作符 r1, B 退栈,计算
B* r 1,结果 r2 进栈
A r 2
8 + 操作符 r2, A 退栈,计算
A * r 2,结果 r3 进栈
r3
步 输入 类 型 动 作 栈内容
9 E 操作数 进栈 r 3 E
10 F 操作数 进栈 r 3 E F
11 ^ 操作符 F, E 退栈,计算
E ^ F,结果 r4 进栈
r 3 r 4
12 G 操作数 进栈 r 3 r 4 G
13 / 操作符 G, r4 退栈,计算
r 4 / E,结果 r5 进栈
r 3 r 5
14 + 操作符 r5, r3 退栈,计算
r 3 + r 5,结果 r6 进栈
r6
void Calculator,,Run ( ) {
char ch; double newoperand;
while ( cin >> ch,ch != ‘=’ ) {
switch ( ch ) {
case ‘+’, case ‘-’, case ‘*’, case ‘/’,
DoOperator ( ch ); break; //计算
default, cin.putback ( ch );
//将字符放回输入流
cin >> newoperand; //读操作数
AddOperand ( newoperand );
}
}
}
利用栈将中缀表示转换为后缀表示
? 使用栈可将表达式的中缀表示转换成它
的前缀表示和后缀表示 。
? 为了实现这种转换, 需要考虑各操作符
的优先级 。
各个算术操作符的优先级
? isp叫做栈内 (in stack priority)优先数
? icp叫做栈外 (in coming priority)优先数 。
? 操作符优先数相等的情况只出现在 括号
配对 或 栈底的, ;”号与输入流最后的, ;”
号配对 时 。
操作符 ch ; ( ^ *,/,% +,- )
i s p ( 栈内 ) 0 1 7 5 3 8
i c p ( 栈外 ) 0 8 6 4 2 1
中缀表达式转换为后缀表达式的算法
? 操作符栈初始化, 将结束符 ‘ ;?进栈 。 然
后读入中缀表达式字符流的首字符 ch。
? 重复执行以下步骤, 直到 ch = ?;?,同时
栈顶的操作符也是 ‘ ;?,停止循环 。
? 若 ch是 操作数 直接输出, 读入下一个
字符 ch。
? 若 ch是 操作符, 判断 ch的优先级 icp和
位于栈顶 的 操作符 op的优先级 isp：
? 若 icp (ch) > isp (op),令 ch进栈, 读入
下一个字符 ch。
? 若 icp (ch) < isp (op),退栈并输出 。
? 若 icp (ch) == isp (op),退栈但不输出,
若退出的是, (”号读入下一个字符 ch。
? 算法结束，输出序列即为所需的后缀表
达式。
void postfix ( expression e ) {
stack<char> s; char ch,op;
s.Push ( ‘;’ ); cin.Get ( ch );
while ( ! s.IsEmpty( ) && ch != ';' )
if ( isdigit ( ch ) )
{ cout << ch; cin.Get ( ch ); }
else {
if ( isp ( s.GetTop( ) ) < icp ( ch ) )
{ s.Push ( ch ); cin.Get ( ch ); }
else if ( isp ( s.GetTop( ) ) > icp ( ch ) )
{ op = s.GetTop ( ); s.Pop( );
cout << op; }
else { op = s.GetTop ( ); s.Pop( );
if ( op == ‘(’ ) cin.Get ( ch ); }
}
}
中缀算术表达式求值
? 使用两个栈, 操作符栈 OPTR (operator)，
操作数栈 OPND(operand)，
? 对中缀表达式求值的一般规则：
(1) 建立并初始化 OPTR栈和 OPND栈,
然后 在 OPTR栈中压入一个, ;”
(2) 从头扫描中缀表达式, 取一字符送入
ch。
(3) 当 ch !=,;” 时,执行以下工作,否则结
束算法 。 此时在 OPND栈 的栈顶得到
运算结果 。
① 若 ch是 操作数, 进 OPND栈, 从中缀
表达式取下一字符送入 ch；
② 若 ch是 操作符, 比较 icp(ch)的优先级
和 isp(OPTR)的优先级：
? 若 icp(ch) > isp(OPTR),则 ch进 OPTR
栈, 从中缀表达式取下一字符送入 ch；
? 若 icp(ch) < isp(OPTR),则从 OPND栈
退出 a2和 a1,从 OPTR栈 退出 θ,形成运
算指令 (a1)θ(a2),结果进 OPND栈 ；
?若 icp(ch) == isp(OPTR) 且 ch ==,)”，
则从 OPTR栈 退出栈顶的, (”,对消括号,
然后从中缀表达式取下一字符送入 ch；
队列 ( Queue )
? 定义
? 队列是只允许在一端删除，在另一端插
入的顺序表
? 允许删除的一端叫做队头 (front)，允许
插入的一端叫做队尾 (rear)。
? 特性
? 先进先出 (FIFO,First In First Out)
a0 a1 a2 an-1
front rear
??
template <class Type> class Queue {
public,
Queue ( int = 10 ); //构造函数
void EnQueue ( const Type& item); //进队
Type DeQueue ( ); //出队列
Type GetFront ( ); //取队头元素值
void MakeEmpty ( ); //置空队列
int IsEmpty ( ) const ; //判队列空否
int IsFull ( ) const; //判队列满否
}
队列的抽象数据类型
队列的进队和出队
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进 队,溢出
队列的进队和出队原则
? 进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
? 出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
? 队满时再进队将 溢出出错 ；
? 队空时再出队将 队空处理 。
? 解决办法之一：将队列元素存放数组首尾
相接，形成 循环 (环形 )队列 。
? 队列存放数组被当作首尾相接的表处理。
? 队头、队尾指针 加 1时从 maxSize -1直接进
到 0，可用语言的取模 (余数 )运算实现。
?队头指针进 1,front = (front+1) % maxSize;
?队尾指针进 1,rear = (rear+1) % maxSize;
?队列初始化,front = rear = 0;
?队空条件,front == rear;
?队满条件,(rear+1) % maxSize == front
循环队列 (Circular Queue)
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 front
0
1
23
4
5
6 7 frontrear
A A
BCrear
rear空队列 A进 队 B,C进 队
0
1
23
4
5
6 7
0
1
23
4
5
6 7
A退 队 B退 队
0
1
23
4
5
6 7
D,E,F,G,H进 队
frontBCrear
A
front
BC
rear front
C
rear
D
E
F G
H
#include <assert.h>
template <class Type> class Queue {
private:
int rear,front; //队尾,队头指针
Type *elements; //队列元素数组
int maxSize; //最大元素个数
public,
Queue ( int = 10 );
~Queue ( ) { delete [ ] elements; }
void EnQueue ( const Type & item); //进队
循环队列的类定义
int DeQueue ( ); //退队
Type *GetFront ( ); //取队头元素
void MakeEmpty ( ) { front = rear = 0; }
int IsEmpty ( ) const
{ return front == rear; }
int IsFull ( ) const
{ return (rear+1) % maxSize == front; }
int Length ( ) const
{ return (rear-front+maxSize) % maxSize;}
}
template <class Type>
Queue<Type>:,Queue ( int sz ),
front (0),rear (0),maxSize (sz) {
elements = new Type[maxSize];
assert ( elements != NULL );
}
template <class Type> void Queue<Type>::
EnQueue ( const Type & item ) {
assert ( !IsFull ( ) );
rear = (rear+1) % MaxSize;
elements[rear] = item;
}
template <class Type>
int Queue<Type>,,DeQueue ( ) {
if ( IsEmpty ( ) ) return 0;
front = ( front+1) % MaxSize;
return 1;
}
template <class Type>
Type Queue<Type>,,GetFront ( ) {
assert ( !IsEmpty ( ) );
return elements[( front+1) % MaxSize];
}
队列的链接表示 — 链式队列
? 队头在链头，队尾在链尾。
? 链式队列在进队时无队满问题，但有队
空问题。
? 队空条件为 front == NULL
front
rear
template <class Type> class Queue;
template <class Type> class QueueNode {
friend class Queue<Type>;
private:
Type data; //队列结点数据
QueueNode<Type> *link; //结点链指针
public:
QueueNode ( Type d=0,QueueNode<Type>
*l = NULL ), data (d),link (l) { }
};
链式队列类的定义
template <class Type> class Queue {
private:
QueueNode<Type> *front,*rear;
//队头、队尾指针指针
public,
Queue ( ), rear ( NULL ),front ( NULL ) { }
~Queue ( );
void EnQueue ( const Type & item );
int DeQueue ( );
Type *GetFront ( );
void MakeEmpty ( ); //实现与 ~Queue( )同
int IsEmpty ( ) const
{ return front == NULL; }
};
template <class Type>
Queue<Type>,,~Queue ( ) {
//队列的析构函数
QueueNode<Type> *p;
while ( front != NULL ) { //逐个结点释放
p = front; front = front->link; delete p;
}
}
template <class Type>
void Queue<Type>,,
EnQueue ( const Type& item ) {
//将新元素 item插入到队列的队尾
if ( front == NULL ) //创建第一个结点
front = rear = new QueueNode
<Type> ( item,NULL );
else //队列不空,插入
rear = rear->link = new QueueNode
<Type> ( item,NULL );
}
template <class Type>
int Queue<Type>,,DeQueue ( ) {
if ( IsEmpty ( ) ) return 0; //判队空
QueueNode<Type> *p = front;
front = front->link; delete p;
return 1;
}
template <class Type>
Type *Queue<Type>,,GetFront ( ) {
if ( IsEmpty( ) ) return NULL;
return & front->data;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列的应用举例 — 逐行打印
二项展开式 (a + b)i 的系数
分析第 i 行元素与第 i+1行元素的关系
从前一行的数据可以计算下一行的数据
i = 2
i = 3
i = 4
0 1 3 3 1 0
1 4 6 4 1
0 1 2 1 0
0 1 1 0
s t
s+t
从第 i 行数据计算并存放第 i+1 行数据
1 2 1 0 1 3 3 1 0 1 4 6
s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1
s+t s=t s=t s=t s=t s=t s=t s=t s=t
s+t s+t s+t s+t s+t s+t s+t s+t
利用队列打印二项展开式系数的程序
#include <stdio.h>
#include <iostream.h>
#include "queue.h"
void YANGVI ( int n ) {
Queue q; //队列初始化
q.MakeEmpty ( );
q.EnQueue (1); q.EnQueue (1);
int s = 0;
for ( int i = 1; i <= n; i++ ) { //逐行计算
cout << endl;
q.EnQueue (0);
for ( int j = 1; j <= i+2; j++ ) { //下一行
int t = q.DeQueue ( );
q.EnQueue ( s + t );
s = t;
if ( j != i+2 ) cout << s << ' ';
}
}
}
任务编号 1 2 3 4 5
优先权 2 0 0 4 0 3 0 1 0
执行顺序 3 1 5 4 2
优先级队列 (Priority Queue)
? 优先级队列 每次从队列中取出的是具
有最高优先权的元素
? 如下表：任务优先权及执行顺序的关系
数字越小，优先权越高
#include <assert.h>
#include <iostream.h>
#include <stdlib.h>
const int maxPQSize = 50; //缺省元素个数
template <class Type> class PQueue {
private:
Type *pqelements; //存放数组
int count; //队列元素计数
public:
优先队列的类定义
PQueue ( );
~PQueue ( ) { delete [ ] pqelements; }
void Insert ( const Type& item );
int RemoveMin ( );
Type * GetFront ();
void MakeEmpty ( ) { count = 0; }
int IsEmpty ( ) const { return count == 0; }
int IsFull ( ) const
{ return count == maxPQSize; }
int Length ( ) const { return count; }
}
template <class Type> PQueue<Type>,:
PQueue ( ), count (0) {
pqelements = new Type[maxPQSize];
assert ( pqelements != NULL );
}
template <class Type>
void PQueue<Type>,:
Insert ( const Type& item ) {
assert ( !IsFull ( ) ); //判队满断言
优先队列部分成员函数的实现
for ( int j = count-1; j >= 0; j-- )
if ( pqelements[j] <= item ) break;
else pqelements[j+1] = pqelements[j];
pqelements[j+1] = item; count++;
}
template <class Type>
int PQueue<Type>,,RemoveMin ( ) {
if ( IsEmpty ( ) ) return 0;
for ( int i = 1; i < count; i++ )
pqelements[i-1] = pqelements[i];
count--; return 1;
}
template <class Type>
Type PQueue<Type>,,GetFront ( ) {
if ( IsEmpty ( ) ) return NULL;
else return pqelements[0];
}
