第 3章 栈和队列
数据结构（ C++描述）
3。 1 栈
3。 2 队列
退出
目录
3.1 栈
3.1.1 栈的定义
栈 (stack)是限制线性表中元素的插入和删除只能
在线性表的同一端进行的一种特殊线性表 。 允
许插入和删除的一端, 为变化的一端, 称为栈
顶 (Top), 另一端为固定的一端, 称为栈底
(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最
后放入的元素在栈顶，而删除元素刚好相反，最后
放入的元素最先删除，最先放入的元素最后删除。
也就是说, 栈是一种后进先出 (Last In First Out)的
线性表, 简称为 LIFO表 。
3.1.2栈的运算
1.初始化栈,INISTACK(&S)
将栈 S置为一个空栈 (不含任何元素 )。
2.进栈,PUSH(&S,X)
将元素 X插入到栈 S中, 也称为, 入栈,,, 插入,,, 压
入, 。
3.出栈,POP(&S)
删除栈 S中的栈顶元素, 也称为, 退栈,,, 删除,,
,弹出, 。
4.取栈顶元素,GETTOP(S)
取栈 S中栈顶元素 。
5.判栈空,EMPTY(S)
判断栈 S是否为空, 若为空, 返回值为 1,否则返回值为 0。
3.1.3栈的抽象数据类型描述
ADT Stack is Data：
含有 n个元素 a1,a2,a3,…,an,按 LIFO规则存放, 每个元素的
类型都为 elemtype。
Operation：
Void inistack(&s) //将栈 S置为一个空栈 (不含任何元素 )
Void Push(&s,x) //将元素 X插入到栈 S中, 也称为, 入
栈,,, 插入,,, 压入,
Void Pop(&s) //删除栈 S中的栈顶元素, 也称为, 退
栈,,, 删除,,, 弹出,
Elemtype gettop(s) //取栈 S中栈顶元素
Int empty(s) //判断栈 S是否为空, 若为空, 返回值为 1，
否则返回值为 0
End stack
3.1.4顺序栈
1.顺序栈的数据类型
CONST int maxsize=maxlen; //定义栈的最大容量为
maxlen
Struct seqstack
{ elemtype stack[maxsize]; //将栈中元素定义
为 elemtype类型
int top; //:指向栈顶位置的指针
}
2,栈的五种运算
（ 1） 初始化栈
void inistack(seqstack &s)
{
s.top=0;
}
（ ２ ） 进栈
void push(seqstack &s,elemtype x)
{
if (s.top==maxsize-1} cout<<”overflow”;
else
{
s.top++;
s.stack[s.top]=x;
}
}
（ ３ ） 退栈
void pop(seqstack &s)
{
if (s.top= =0) cout<<”underflow”;
else
s.top--;
}
（ ４ ） 取栈顶元素
elemtype gettop(seqstack s)
{
if (s.top= =0) {cout<<”underflow”;return 0;}
else return s.stack[s.top];
}
（ 5） 判栈空否
int empty(seqstack s)
{
if (s.top= =0) return 1;else return 0;
}
3,栈的共享存储单元
有时, 一个程序设计中, 需要使用多个同一类型的栈,
这时候, 可能会产生一个栈空间过小, 容量发生溢出,
而另一个栈空间过大, 造成大量存储单元浪费的现象 。
为了充分利用各个栈的存储空间, 这时可以采用多个
栈共享存储单元, 即给多个栈分配一个足够大的存储
空间, 让多个栈实现存储空间优势互补 。
栈 1 顶 栈 2 顶
栈 1 底 栈 2 底
图 3 - 3 两个栈共享存储单元示意图
两个栈共享存储单元可用如下 C++语句描述：
CONST int maxsize=maxlen; //maxlen为共享单元
的最大长度
Struct duseqstack
{ elemtype stack[maxsize];
int top[2] ; //两个栈的栈顶指针
………
};
（ 1） 两个栈共享存储单元的进栈算法
void dupush(duseqstack &s,elemtype x,int k)
//将元素 x进入到以 S为栈空间的第 k个栈中
{
if (s.top[0]+1==s.top[1]) cout<<“overflow”
else if (k==0) { s.top[0]++;s.stack[s.top[0]]=x;}
else {s.top[1]--; s.stack[s.top[1]]=x;}
}
（ 2） 两个栈共享存储单元的退栈算法
void pop(duseqstack &s,int k)
//将以 s为栈空间的栈中第 k个栈进行退栈
{
if ((k==0)&&(s.top[0]==0)) cout<<”underflow”;
else if ((k==1)&&(s.top[1]==maxsize)
cout<<”underflow”;
else if(k==0) s.top[0]--;
else s.top[1]++;
}
3.1.5链栈
1,链栈结构及数据类型
栈的链式存贮结构,也称为链栈, 它是一种限制运算
的链表, 即规定链表中的扦入和删除运算只能在链表
开头进行 。 链栈结构见图 3-5。
头
a 1
a 2
to p
栈顶 栈底
…… a n ^
图 3 - 5 链栈结构示意图
2,链栈的五种栈运算
（ 1） 栈初始化
void inistack(link *top)
{ top->next=NULL;}
（ 2） 进栈运算
void push(link *top,int x)
{ link *s;
s=new link;
s->data=x;
s->next=top->next;
top->next=s; }
（ 3） 退栈运算
void pop(link *top)
{
link *s;
s=top->next;
if(s!=NULL)
{
top->next=s->next;
delete(s);
}
}
（ 4） 取栈顶元素
elemtype gettop(link *top)
{
if(top->next!=NULL)
return(top->next->data);
else
return(NULL);
}
（ 5） 判栈空
int empty(link *top)
{
if(top->next==NULL)
return(1);
else
return(0);
}
3.1.6 栈的应用
栈在日常生活中和计算机程序设计中有着许多应用,
下面仅介绍栈在计算机中的应用 。
1.算术表达式的求值
算术表达式中包含了算术运算符和算术量 (常量、变量、
函数 )，而运算符之间又存在着优先级，不能简单地进
行从左到右运算，编译程序在求值时，不能简单从左
到右运算，必须先算运算级别高的，再算运算级别低
的，同一级运算才从左到右 (C++中有些从右到左 )。
因此, 要实现表达式求值, 必须设置两个栈, 一个栈
存放运算符, 另一个栈存放操作数 （ 算术量 ）, 在进
行表达式求值时, 编译程序从左到右扫描, 遇到操作
数, 一律进入操作数栈, 遇到运算符, 则应与运算符
栈的栈顶比较, 若运算符优先级高于栈顶则进栈, 否
则退栈, 退栈后, 在操作数栈中退出两个元素 (先退出
在运算符右, 后退出在运算符左 ),然后用运算符栈中
退出的栈顶元素进行运算, 运算的结果存入操作数栈
中, 直到扫描完毕 。 这时运算符栈为空, 操作数栈中
只有一个元素, 即为运算的结果 。
例求表达式 1+2*3-4/2的值，栈的变化如下。
步骤 操作数栈 运算符栈 说明
开始 两栈均为空
1 1 1进入操作数栈
+进入运算符栈
2进入操作数栈
*进入运算符栈
3进入操作数栈
退栈
2*3进入操作数栈
退栈
1+6进入操作数栈
2
3
4
5
6
7
8
9
1 +
1 2 +
1 2 +
1
1
1
7
+
*
2 3
6
+ *
+
步骤 操作数栈 运算符栈 说明
10 7 -进入运算符栈
4进入操作数栈
/进入运算符栈
2进入操作数栈
退栈
4/2进入操作数栈
退栈
7-2进入操作数栈
11
12
13
14
15
16
17
7 4 -
7 4 - /
7 4 2 - /
7
7 2 -
-
-
5
当然，算术表达式除了简单求值外，还会涉及到算术
表达式的两种表示方法，即中缀表示法和后缀表示法。
刚才的例 3-3中的表达式就是中缀表达式，中缀表达式
求值较麻烦（须考虑运算符的优先级，甚至还要考虑
圆括号），而后缀表达式求值较方便（无须考虑运算
符的优先级及圆括号）。下面将介绍算术表达式的中
缀表示和后缀表示及它们的求值规律，
例如, 对于下列各中缀表达式,（ 1） 3/5+8
（ 2） 18-9*(4+3)
（ 3） (25+x)*(a*(a+b)+b)
对应的后缀表达式为：
(1)3 5 / 8 +
(2)18 9 4 3 + * -
(3)25 x + a a b + * b + *
2,中缀表达式变成等价的后缀表达式
将中缀表达式变成等价的后缀表达式, 表达式中操作数次
序不变, 运算符次序发生变化, 同时去掉了圆括号 。 转换
规则是：设立一个栈, 存放运算符, 首先栈为空, 编译程
序从左到右扫描中缀表达式, 若遇到操作数, 直接输出,
并输出一个空格作为两个操作数的分隔符；若遇到运算符,
则必须与栈顶比较, 运算符级别比栈顶级别高则进栈, 否
则退出栈顶元素并输出, 然后输出一个空格作分隔符；若
遇到左括号, 进栈；若遇到右括号, 则一直退栈输出, 直
到退到左括号止 。 当栈变成空时, 输出的结果即为后缀表
达式 。
将中缀表达式 (1+2)*((8-2)/(7-4))变成等价的后缀表达式 。
现在用栈来实现该运算, 栈的变化及输出结果如 下
步骤 栈中元素 输出结果 说明
1 ( （进栈
2 ( 1 输出 1
3 ( + 1 +进栈
4 ( + 1 2 输出 2
5 1 2 + +退栈输出，退栈到（
止
6 * 1 2 + *进栈
7 * ( 1 2 + （进栈
8 * ( ( 1 2 + （进栈
9 * ( ( 1 2 + 8 输出 8
10 * ( ( - 1 2 + 8 - 进栈
11 * ( ( - 1 2 + 8 2 输出 2
12 * ( 1 2 + 8 2 - -退栈输出，退栈到
（止
13 * ( / 1 2 + 8 2 - / 进栈
14 * ( / ( 1 2 + 8 2 - （ 进栈
15 * ( / ( 1 2 + 8 2 - 7 输出 7
16 * ( / ( - 1 2 + 8 2 - 7 - 进栈
17 * ( / ( - 1 2 + 8 2 - 7 4 输出 4
18 * ( / 1 2 + 8 2 - 7 4 - -退栈输出，退栈到
（止
19 * 1 2 + 8 2 - 7 4 - / /退栈输出，退栈到
（止
20 1 2 + 8 2 - 7 4 - / * *退栈并输出
步骤 栈中元素 输出结果 说明
3,后缀表达式的求值
将中缀表达式转换成等价的后缀表达式后, 求值时,
不需要再考虑运算符的优先级, 只需从左到右扫描一
遍后缀表达式即可 。 具体求值步骤为：设置一个栈,
开始时, 栈为空, 然后从左到右扫描后缀表达式, 若
遇操作数, 则进栈；若遇运算符, 则从栈中退出两个
元素, 先退出的放到运算符的右边, 后退出的放到运
算符左边, 运算后的结果再进栈, 直到后缀表达式扫
描完毕 。 此时, 栈中仅有一个元素, 即为运算的结果 。
例, 求后缀表达式,1 2 + 8 2 - 7 4 - / *的值,
栈的变化情如下：
步骤 栈中元素 说明
1 1 1进栈
2 1 2 2进栈
3 遇 +号退栈 2和 1
4 3 1+2=3的结果 3进栈
5 3 8 8进栈
6 3 8 2 2进栈
7 3 遇 -号退栈 2和 8
8 3 6 8-2=6的结果 6进栈
9 3 6 7 7进栈
10 3 6 7 4 4进栈
步骤 栈中元素 说明
11 3 6 遇 -号退栈 4和 7
12 3 6 3 7-4=3的结果 3进栈
13 3 遇 /号退栈 3和 6
14 3 2 6/3=2的结果 2进栈
15 遇 *号退栈 2和 3
16 6 3*2=6进栈
17 6 扫描完毕，运算结束
从上可知, 最后求得的后缀表达式之值为 6,与用中
缀表达式求得的结果一致, 但后缀式求值要简单得
多 。
4．函数的嵌套调用
在函数嵌套调用中，一个函数的执行没有结束，又开
始另一个函数的执行，因此必须用栈来保存函数中中
断的地址，以便调用返回时能从断点继续往下执行。
例 设有一个主程序, 它调用函数 a,函数 a又调用函数 b，
函数 b又调用函数 c,（ 见下页 ）, 其中 r,s,t分别表
示中断地址, 我们可以用一个栈来描述调用情况 （ 见
下页 ） 。
主程序调用函数 a,留下一个断点地址 r进栈, 然后主函
数处于挂起状态, 进入函数 a中执行, 函数 a中再调用函
数 b,留下一个断点地址 s进栈, 然后函数 a处于挂起状
态, 进入函数 b中执行, 函数 b中调用函数 c,留下一个
断点地址 t进栈, 然后函数 b处于挂起状态, 进入函数 c
中执行, 函数 c执行完后, 要返回断点处继续执行, 但
返回到那一个断点呢?根据栈顶元素来决定 。 返回时,
执行退栈操作, 先退出 t,故返回 t断点继续执行, 接着
退栈退出 s,故返回 s断点继续执行, 接着退栈退出 r,返
回 r断点继续执行, 最后栈为空, 算法结束 。
主函数 a 函数 b 函数 c 函数
r s t
函数的嵌套调用与返回
s
r
t
s
r
r
( a ) 调用 a 函数,r 进栈 ( b ) 调用 b 函数,s 进栈 ( c) 调用 c 函数,t 进栈
r
s
r
( d) 返回 b 函数,t 退栈 ( e) 返回 a 函数,s 退栈 ( f ) 返回主程序,r 退栈
函数嵌套调用栈变化示意图
5,函数的递归调用
函数的递归调用也是一种嵌套,故也必须用栈来
保存断点信息, 但递归调用相当于同一个函数的嵌
套调用, 故除了保存断点信息外, 还必须保存每一
层的参数, 局部变量等 。
例 3-7 求 n! 可用递归函数描述如下：
1 n=0
n! ＝
n*(n-1)! n>0
4*3!
3*2!
4*3!
2*1!
3*2!
4*3!
1*0!
2*1!
3*2!
4*3!
(a) (b) (c) (d) (e)
1*1
2*1!
3*2!
4*3!
2*1
3*2!
4*3!
3*2
4*3!
4*6
( f ) ( g) ( h) ( i)
递归调用中栈变化示意图
a 1 a 2 ….,a n 入队
队头 队尾
出队
图 3 - 9 队 列示意图
3.2 队列
3.2.1队列的定义
仅允许在一端进行插入，另一端进行删除的线性表，称为队列
(queue)。允许插入的一端称为队尾 (rear)，允许删除的一端称为
队头（ frort）。
队列是一种先进先出 （ First In First Out） 的特殊线性表, 或称 FIFO
表 。
若队列中没有任何元素，则称为空队列，否则称为非空队列。
队列的描述可以用如图 3-9的方式所描述 。
3.2.2 队列的基本运算
队列可定义如下五种基本运算：
1,初始化队列 INIQUEUE(&Q)
将队列 Q设置成一个空队列 。
2,入队列 ENQUEUE(&Q,X)
将元素 X插入到队尾中, 也称, 进队,,, 插入, 。
3,出队列 DLQUEUE(&Q)
将队列 Q的队头元素删除, 也称, 退队,,, 删除, 。
4,取队头元素 GETHEAD(Q)
得到队列 Q的队头元素之值 。
5,判队空 EMPTY(Q)
判断队列 Q是否为空, 若为空返回 1,否则返回 0。
3.2.3 队列的抽象数据类型描述
队列的抽象数据类型可描述为,ADT QUEUE IS
DATA：含有 n个元素 a1,a2,a3,… an,按 FIFO规则存放, 每个元
素的类型为 elemtype
Operation：
Void INIQUEUE(&Q) //将队列 Q设置成一个空队列 。
Void ENQUEUE(&Q,X)//将元素 X插入到队尾中, 也称, 进
队,,, 插入, 。
Void DLQUEUE(&Q) //将队列 Q的队头元素删除, 也称
,退队,,, 删除, 。
Elemtype GETHEAD(Q) //得到队列 Q的队头元素之值 。
int EMPTY(Q) 判断队列 Q是否为空, 若为空返回 1，
否则返回 0。
End queue
3.2.4 循环队列
1,队列的顺序存储数据类型描述
CONST int maxsize= maxlen; //定义队列的最大容量为
maxlen
struct seqqueue
{
elemtype queue[maxsize]; //将队列中元素定为数组型, 元
素类型为 elemtype
int front; //队头指针
int rear; //队尾指针
};
2,顺序队列
将队列中元素全部存入一个一维数组中,数组的低下标
一端为队头,高下标一端为队尾，将这样的队列看成是
顺序队列
若一维数组中所有位置上都被元素装满，称为队满，
即尾指针 rear指向一维数组最后,而头指针指向一维数组
开头，称为队满。
但有可能出现这样情况, 尾指针指向一维数组最后,
但前面有很多元素已经出队, 即空出很多位置, 这时
要插入元素, 仍然会发生溢出 。 例如, 在图 3-13(d)中,
若队列的最大容量 maxsize=6,此时, front=rear=6,再
进队时将发生溢出 。 我们将这种溢出称为, 假溢出, 。
要克服, 假溢出,, 可以将整个队列中元素向前移动,
直到头指针 front为零, 或者每次出队时, 都将队列中
元素前移一个位置 。 因此, 顺序队列的队满判定条件
为 rear=maxsize。 但是, 在顺序队列中, 这些克服假溢
出的方法都会引起大量元素的移动, 花费大量的时间,
所以在实际应用中很少采用, 一般采用下面的循环队
列形式 。
3,循环队列
为了克服顺序队列中假溢出, 通常将一维数组
queue[0]到 q[maxsize-1]看成是一个首尾相接的圆环,
即 queue[0]与 queue[maxsize-1]相接在一起 。 将这种
形式的顺序队列称为循环队列, 见图 3-11。
队头
队尾
a
n - 1
a
3
a
2
a
1
a
n
a
i
……
……
图 3 - 11 循环队列示意图
在循环队列中, 若 front=rear,则称为队空, 若
(rear+1)%maxsize=front,则称为队满, 这时, 循环队列
中能装入的元素个数为 maxsize-1,即浪费一个存储单元,
但是这样可以给操作带来较大方便 。
4,循环队列上五种运算实现
（ 1） 队列初始化
Void INIQUEUE(seqqueue &q )
{ q.front=q.rear=maxsize-1;
}
(2) 进队列
Void enqueue (seqqueue &q,elemtype x)
{
if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”;
else { q.rear=(q.rear+1)%maxsize;
q.queue[q.rear]=x;
}
}
(3) 出队列
Void dlqueue(seqqueue &q )
{
if (q.rear= =q.front) cout<<”underflow”;
else
q.front =(q.front+1)%maxsize;
}
(4) 取队头元素 （ 注意得到的应为头指针后面一个位置
值 ）
elemtype gethead(seqqueue q )
{ if (q.rear= =q.front)
{ cout<<”underflow”； return NULL;}
else return q.queue[(q.front+1)%maxsize];
}
(5) 判队列空否
int empty(seqqueue q )
{ if (q.rear= =q.front) reurn 1;
else return 0; }
3.2.5 链队列
1 。 链队列的数据类型描述
队列的链式存储，称为链队列，与前面介绍的单链表
类似，但为了使头指针，尾指针统一起来，另外定义
一种数据类型如下。
Struct link //定义单链表数据类型
{ elemtype data;
link *next;};
struct linkqueue //定义链队列数据类型
{ link *front,*rear; //定义头指针和尾指针
};
r e a r
头 ^
f r o n t
a n ^ 头
f r o n t
a 1 …… a 2
r e a r
（ a ）空链队列 ( b ) 非空链队
链队列示意图
2 。 链队列上的基本运算
同样，链队列上也可以给出五种运算如下：
（ 1） 链队列上的初始化
void INIQUEUE(linkqueue( &s)
{ link *p;
p=new link;
p->next=NULL;
s.front=p;
s.rear=p;
}
(2) 入队列
void push(linkqueue &s,elemtype x)
{
link *p;
p=new link;
p->data=x;
p->next=s.rear->next;
s.rear->next=p;
s.rear=p;
}
(3) 判队空
int empty(linkqueue s)
{ if (s.front= =s.rear) return 1;
else return 0;
}
(4) 取队头元素
elemtype gethead(linkqueue s)
{ if (s.front= =s.rear) return NULL;
else retuen s.front->next->data;
}
(5) 出队列
void pop(linkqueue &s)
{ link *p;
p=s.front->next;
if (p->next= =NULL) //链队列中只有一个队头元素,
无其它元素
{s.front->next=NULL;
s.rear=s.front;}
else
s.front->next =p->next;
delete (p);}
从上述出队列算法中可知, 若链队列中只有一个元素
时, 需作特殊处理 (用 if语句判断 ),修改队尾指针 。 为
了避免修改队尾指针, 我们可以采用一种改进的出队
列算法 。 其基本思想是：出队列时, 修改头指针, 删
除头结点而非队头结点, 这时, 将队头结点成为新的
头结点, 队列中第二个结点成为队头结点 。 这时, 不
管队列中有多少个元素, 都不需作特殊处理 （ 不需用 if
语句来判断 ）, 这种改进的算法如下：
void pop(linkqueue &s)
{ link *p;
p=s.front;
s.front=p->next;
delete (p);}
3.2.6 队列的应用
队列在日常生活中和计算机程序设计中, 有着非常重要
的作用, 在此, 仅举出两个方面例子来说明它, 其它应
用在后面章节中将会遇到 。
第一个例子就是 CPU资源的竞争问题 。 在具有多个终端的
计算机系统中, 有多个用户需要使用 CPU各自运行自己的
程序, 它们分别通过各自终端向操作系统提出使用 CPU的
请求, 操作系统按照每个请求在时间上的先后顺序, 将其
排成一个队列, 每次把 CPU分配给队头用户使用, 当相应
的程序运行结束, 则令其出队, 再把 CPU分配给新的队头
用户, 直到所有用户任务处理完毕 。
第二个例子就是主机与外部设备之间速度不匹配的问
题 。 以主机和打印机为例来说明, 主机输出数据给打
印机打印, 主机输出数据的速度比打印机打印的速度
要快得多, 若直接把输出的数据送给打印机打印, 由
于速度不匹配, 显然是不行的 。 所以解决的方法是设
置一个打印数据缓冲区, 主机把要打印输出的数据依
此写如到这个缓冲区中, 写满后就暂停输出, 继而去
做其它的事情, 打印机就从缓冲区中按照先进先出的
原则依次取出数据并打印, 打印完后再向主机发出请
求, 主机接到请求后再向缓冲区写入打印数据, 这样
利用队列既保证了打印数据的正确, 又使主机提高了
效率 。
数据结构（ C++描述）
3。 1 栈
3。 2 队列
退出
目录
3.1 栈
3.1.1 栈的定义
栈 (stack)是限制线性表中元素的插入和删除只能
在线性表的同一端进行的一种特殊线性表 。 允
许插入和删除的一端, 为变化的一端, 称为栈
顶 (Top), 另一端为固定的一端, 称为栈底
(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最
后放入的元素在栈顶，而删除元素刚好相反，最后
放入的元素最先删除，最先放入的元素最后删除。
也就是说, 栈是一种后进先出 (Last In First Out)的
线性表, 简称为 LIFO表 。
3.1.2栈的运算
1.初始化栈,INISTACK(&S)
将栈 S置为一个空栈 (不含任何元素 )。
2.进栈,PUSH(&S,X)
将元素 X插入到栈 S中, 也称为, 入栈,,, 插入,,, 压
入, 。
3.出栈,POP(&S)
删除栈 S中的栈顶元素, 也称为, 退栈,,, 删除,,
,弹出, 。
4.取栈顶元素,GETTOP(S)
取栈 S中栈顶元素 。
5.判栈空,EMPTY(S)
判断栈 S是否为空, 若为空, 返回值为 1,否则返回值为 0。
3.1.3栈的抽象数据类型描述
ADT Stack is Data：
含有 n个元素 a1,a2,a3,…,an,按 LIFO规则存放, 每个元素的
类型都为 elemtype。
Operation：
Void inistack(&s) //将栈 S置为一个空栈 (不含任何元素 )
Void Push(&s,x) //将元素 X插入到栈 S中, 也称为, 入
栈,,, 插入,,, 压入,
Void Pop(&s) //删除栈 S中的栈顶元素, 也称为, 退
栈,,, 删除,,, 弹出,
Elemtype gettop(s) //取栈 S中栈顶元素
Int empty(s) //判断栈 S是否为空, 若为空, 返回值为 1，
否则返回值为 0
End stack
3.1.4顺序栈
1.顺序栈的数据类型
CONST int maxsize=maxlen; //定义栈的最大容量为
maxlen
Struct seqstack
{ elemtype stack[maxsize]; //将栈中元素定义
为 elemtype类型
int top; //:指向栈顶位置的指针
}
2,栈的五种运算
（ 1） 初始化栈
void inistack(seqstack &s)
{
s.top=0;
}
（ ２ ） 进栈
void push(seqstack &s,elemtype x)
{
if (s.top==maxsize-1} cout<<”overflow”;
else
{
s.top++;
s.stack[s.top]=x;
}
}
（ ３ ） 退栈
void pop(seqstack &s)
{
if (s.top= =0) cout<<”underflow”;
else
s.top--;
}
（ ４ ） 取栈顶元素
elemtype gettop(seqstack s)
{
if (s.top= =0) {cout<<”underflow”;return 0;}
else return s.stack[s.top];
}
（ 5） 判栈空否
int empty(seqstack s)
{
if (s.top= =0) return 1;else return 0;
}
3,栈的共享存储单元
有时, 一个程序设计中, 需要使用多个同一类型的栈,
这时候, 可能会产生一个栈空间过小, 容量发生溢出,
而另一个栈空间过大, 造成大量存储单元浪费的现象 。
为了充分利用各个栈的存储空间, 这时可以采用多个
栈共享存储单元, 即给多个栈分配一个足够大的存储
空间, 让多个栈实现存储空间优势互补 。
栈 1 顶 栈 2 顶
栈 1 底 栈 2 底
图 3 - 3 两个栈共享存储单元示意图
两个栈共享存储单元可用如下 C++语句描述：
CONST int maxsize=maxlen; //maxlen为共享单元
的最大长度
Struct duseqstack
{ elemtype stack[maxsize];
int top[2] ; //两个栈的栈顶指针
………
};
（ 1） 两个栈共享存储单元的进栈算法
void dupush(duseqstack &s,elemtype x,int k)
//将元素 x进入到以 S为栈空间的第 k个栈中
{
if (s.top[0]+1==s.top[1]) cout<<“overflow”
else if (k==0) { s.top[0]++;s.stack[s.top[0]]=x;}
else {s.top[1]--; s.stack[s.top[1]]=x;}
}
（ 2） 两个栈共享存储单元的退栈算法
void pop(duseqstack &s,int k)
//将以 s为栈空间的栈中第 k个栈进行退栈
{
if ((k==0)&&(s.top[0]==0)) cout<<”underflow”;
else if ((k==1)&&(s.top[1]==maxsize)
cout<<”underflow”;
else if(k==0) s.top[0]--;
else s.top[1]++;
}
3.1.5链栈
1,链栈结构及数据类型
栈的链式存贮结构,也称为链栈, 它是一种限制运算
的链表, 即规定链表中的扦入和删除运算只能在链表
开头进行 。 链栈结构见图 3-5。
头
a 1
a 2
to p
栈顶 栈底
…… a n ^
图 3 - 5 链栈结构示意图
2,链栈的五种栈运算
（ 1） 栈初始化
void inistack(link *top)
{ top->next=NULL;}
（ 2） 进栈运算
void push(link *top,int x)
{ link *s;
s=new link;
s->data=x;
s->next=top->next;
top->next=s; }
（ 3） 退栈运算
void pop(link *top)
{
link *s;
s=top->next;
if(s!=NULL)
{
top->next=s->next;
delete(s);
}
}
（ 4） 取栈顶元素
elemtype gettop(link *top)
{
if(top->next!=NULL)
return(top->next->data);
else
return(NULL);
}
（ 5） 判栈空
int empty(link *top)
{
if(top->next==NULL)
return(1);
else
return(0);
}
3.1.6 栈的应用
栈在日常生活中和计算机程序设计中有着许多应用,
下面仅介绍栈在计算机中的应用 。
1.算术表达式的求值
算术表达式中包含了算术运算符和算术量 (常量、变量、
函数 )，而运算符之间又存在着优先级，不能简单地进
行从左到右运算，编译程序在求值时，不能简单从左
到右运算，必须先算运算级别高的，再算运算级别低
的，同一级运算才从左到右 (C++中有些从右到左 )。
因此, 要实现表达式求值, 必须设置两个栈, 一个栈
存放运算符, 另一个栈存放操作数 （ 算术量 ）, 在进
行表达式求值时, 编译程序从左到右扫描, 遇到操作
数, 一律进入操作数栈, 遇到运算符, 则应与运算符
栈的栈顶比较, 若运算符优先级高于栈顶则进栈, 否
则退栈, 退栈后, 在操作数栈中退出两个元素 (先退出
在运算符右, 后退出在运算符左 ),然后用运算符栈中
退出的栈顶元素进行运算, 运算的结果存入操作数栈
中, 直到扫描完毕 。 这时运算符栈为空, 操作数栈中
只有一个元素, 即为运算的结果 。
例求表达式 1+2*3-4/2的值，栈的变化如下。
步骤 操作数栈 运算符栈 说明
开始 两栈均为空
1 1 1进入操作数栈
+进入运算符栈
2进入操作数栈
*进入运算符栈
3进入操作数栈
退栈
2*3进入操作数栈
退栈
1+6进入操作数栈
2
3
4
5
6
7
8
9
1 +
1 2 +
1 2 +
1
1
1
7
+
*
2 3
6
+ *
+
步骤 操作数栈 运算符栈 说明
10 7 -进入运算符栈
4进入操作数栈
/进入运算符栈
2进入操作数栈
退栈
4/2进入操作数栈
退栈
7-2进入操作数栈
11
12
13
14
15
16
17
7 4 -
7 4 - /
7 4 2 - /
7
7 2 -
-
-
5
当然，算术表达式除了简单求值外，还会涉及到算术
表达式的两种表示方法，即中缀表示法和后缀表示法。
刚才的例 3-3中的表达式就是中缀表达式，中缀表达式
求值较麻烦（须考虑运算符的优先级，甚至还要考虑
圆括号），而后缀表达式求值较方便（无须考虑运算
符的优先级及圆括号）。下面将介绍算术表达式的中
缀表示和后缀表示及它们的求值规律，
例如, 对于下列各中缀表达式,（ 1） 3/5+8
（ 2） 18-9*(4+3)
（ 3） (25+x)*(a*(a+b)+b)
对应的后缀表达式为：
(1)3 5 / 8 +
(2)18 9 4 3 + * -
(3)25 x + a a b + * b + *
2,中缀表达式变成等价的后缀表达式
将中缀表达式变成等价的后缀表达式, 表达式中操作数次
序不变, 运算符次序发生变化, 同时去掉了圆括号 。 转换
规则是：设立一个栈, 存放运算符, 首先栈为空, 编译程
序从左到右扫描中缀表达式, 若遇到操作数, 直接输出,
并输出一个空格作为两个操作数的分隔符；若遇到运算符,
则必须与栈顶比较, 运算符级别比栈顶级别高则进栈, 否
则退出栈顶元素并输出, 然后输出一个空格作分隔符；若
遇到左括号, 进栈；若遇到右括号, 则一直退栈输出, 直
到退到左括号止 。 当栈变成空时, 输出的结果即为后缀表
达式 。
将中缀表达式 (1+2)*((8-2)/(7-4))变成等价的后缀表达式 。
现在用栈来实现该运算, 栈的变化及输出结果如 下
步骤 栈中元素 输出结果 说明
1 ( （进栈
2 ( 1 输出 1
3 ( + 1 +进栈
4 ( + 1 2 输出 2
5 1 2 + +退栈输出，退栈到（
止
6 * 1 2 + *进栈
7 * ( 1 2 + （进栈
8 * ( ( 1 2 + （进栈
9 * ( ( 1 2 + 8 输出 8
10 * ( ( - 1 2 + 8 - 进栈
11 * ( ( - 1 2 + 8 2 输出 2
12 * ( 1 2 + 8 2 - -退栈输出，退栈到
（止
13 * ( / 1 2 + 8 2 - / 进栈
14 * ( / ( 1 2 + 8 2 - （ 进栈
15 * ( / ( 1 2 + 8 2 - 7 输出 7
16 * ( / ( - 1 2 + 8 2 - 7 - 进栈
17 * ( / ( - 1 2 + 8 2 - 7 4 输出 4
18 * ( / 1 2 + 8 2 - 7 4 - -退栈输出，退栈到
（止
19 * 1 2 + 8 2 - 7 4 - / /退栈输出，退栈到
（止
20 1 2 + 8 2 - 7 4 - / * *退栈并输出
步骤 栈中元素 输出结果 说明
3,后缀表达式的求值
将中缀表达式转换成等价的后缀表达式后, 求值时,
不需要再考虑运算符的优先级, 只需从左到右扫描一
遍后缀表达式即可 。 具体求值步骤为：设置一个栈,
开始时, 栈为空, 然后从左到右扫描后缀表达式, 若
遇操作数, 则进栈；若遇运算符, 则从栈中退出两个
元素, 先退出的放到运算符的右边, 后退出的放到运
算符左边, 运算后的结果再进栈, 直到后缀表达式扫
描完毕 。 此时, 栈中仅有一个元素, 即为运算的结果 。
例, 求后缀表达式,1 2 + 8 2 - 7 4 - / *的值,
栈的变化情如下：
步骤 栈中元素 说明
1 1 1进栈
2 1 2 2进栈
3 遇 +号退栈 2和 1
4 3 1+2=3的结果 3进栈
5 3 8 8进栈
6 3 8 2 2进栈
7 3 遇 -号退栈 2和 8
8 3 6 8-2=6的结果 6进栈
9 3 6 7 7进栈
10 3 6 7 4 4进栈
步骤 栈中元素 说明
11 3 6 遇 -号退栈 4和 7
12 3 6 3 7-4=3的结果 3进栈
13 3 遇 /号退栈 3和 6
14 3 2 6/3=2的结果 2进栈
15 遇 *号退栈 2和 3
16 6 3*2=6进栈
17 6 扫描完毕，运算结束
从上可知, 最后求得的后缀表达式之值为 6,与用中
缀表达式求得的结果一致, 但后缀式求值要简单得
多 。
4．函数的嵌套调用
在函数嵌套调用中，一个函数的执行没有结束，又开
始另一个函数的执行，因此必须用栈来保存函数中中
断的地址，以便调用返回时能从断点继续往下执行。
例 设有一个主程序, 它调用函数 a,函数 a又调用函数 b，
函数 b又调用函数 c,（ 见下页 ）, 其中 r,s,t分别表
示中断地址, 我们可以用一个栈来描述调用情况 （ 见
下页 ） 。
主程序调用函数 a,留下一个断点地址 r进栈, 然后主函
数处于挂起状态, 进入函数 a中执行, 函数 a中再调用函
数 b,留下一个断点地址 s进栈, 然后函数 a处于挂起状
态, 进入函数 b中执行, 函数 b中调用函数 c,留下一个
断点地址 t进栈, 然后函数 b处于挂起状态, 进入函数 c
中执行, 函数 c执行完后, 要返回断点处继续执行, 但
返回到那一个断点呢?根据栈顶元素来决定 。 返回时,
执行退栈操作, 先退出 t,故返回 t断点继续执行, 接着
退栈退出 s,故返回 s断点继续执行, 接着退栈退出 r,返
回 r断点继续执行, 最后栈为空, 算法结束 。
主函数 a 函数 b 函数 c 函数
r s t
函数的嵌套调用与返回
s
r
t
s
r
r
( a ) 调用 a 函数,r 进栈 ( b ) 调用 b 函数,s 进栈 ( c) 调用 c 函数,t 进栈
r
s
r
( d) 返回 b 函数,t 退栈 ( e) 返回 a 函数,s 退栈 ( f ) 返回主程序,r 退栈
函数嵌套调用栈变化示意图
5,函数的递归调用
函数的递归调用也是一种嵌套,故也必须用栈来
保存断点信息, 但递归调用相当于同一个函数的嵌
套调用, 故除了保存断点信息外, 还必须保存每一
层的参数, 局部变量等 。
例 3-7 求 n! 可用递归函数描述如下：
1 n=0
n! ＝
n*(n-1)! n>0
4*3!
3*2!
4*3!
2*1!
3*2!
4*3!
1*0!
2*1!
3*2!
4*3!
(a) (b) (c) (d) (e)
1*1
2*1!
3*2!
4*3!
2*1
3*2!
4*3!
3*2
4*3!
4*6
( f ) ( g) ( h) ( i)
递归调用中栈变化示意图
a 1 a 2 ….,a n 入队
队头 队尾
出队
图 3 - 9 队 列示意图
3.2 队列
3.2.1队列的定义
仅允许在一端进行插入，另一端进行删除的线性表，称为队列
(queue)。允许插入的一端称为队尾 (rear)，允许删除的一端称为
队头（ frort）。
队列是一种先进先出 （ First In First Out） 的特殊线性表, 或称 FIFO
表 。
若队列中没有任何元素，则称为空队列，否则称为非空队列。
队列的描述可以用如图 3-9的方式所描述 。
3.2.2 队列的基本运算
队列可定义如下五种基本运算：
1,初始化队列 INIQUEUE(&Q)
将队列 Q设置成一个空队列 。
2,入队列 ENQUEUE(&Q,X)
将元素 X插入到队尾中, 也称, 进队,,, 插入, 。
3,出队列 DLQUEUE(&Q)
将队列 Q的队头元素删除, 也称, 退队,,, 删除, 。
4,取队头元素 GETHEAD(Q)
得到队列 Q的队头元素之值 。
5,判队空 EMPTY(Q)
判断队列 Q是否为空, 若为空返回 1,否则返回 0。
3.2.3 队列的抽象数据类型描述
队列的抽象数据类型可描述为,ADT QUEUE IS
DATA：含有 n个元素 a1,a2,a3,… an,按 FIFO规则存放, 每个元
素的类型为 elemtype
Operation：
Void INIQUEUE(&Q) //将队列 Q设置成一个空队列 。
Void ENQUEUE(&Q,X)//将元素 X插入到队尾中, 也称, 进
队,,, 插入, 。
Void DLQUEUE(&Q) //将队列 Q的队头元素删除, 也称
,退队,,, 删除, 。
Elemtype GETHEAD(Q) //得到队列 Q的队头元素之值 。
int EMPTY(Q) 判断队列 Q是否为空, 若为空返回 1，
否则返回 0。
End queue
3.2.4 循环队列
1,队列的顺序存储数据类型描述
CONST int maxsize= maxlen; //定义队列的最大容量为
maxlen
struct seqqueue
{
elemtype queue[maxsize]; //将队列中元素定为数组型, 元
素类型为 elemtype
int front; //队头指针
int rear; //队尾指针
};
2,顺序队列
将队列中元素全部存入一个一维数组中,数组的低下标
一端为队头,高下标一端为队尾，将这样的队列看成是
顺序队列
若一维数组中所有位置上都被元素装满，称为队满，
即尾指针 rear指向一维数组最后,而头指针指向一维数组
开头，称为队满。
但有可能出现这样情况, 尾指针指向一维数组最后,
但前面有很多元素已经出队, 即空出很多位置, 这时
要插入元素, 仍然会发生溢出 。 例如, 在图 3-13(d)中,
若队列的最大容量 maxsize=6,此时, front=rear=6,再
进队时将发生溢出 。 我们将这种溢出称为, 假溢出, 。
要克服, 假溢出,, 可以将整个队列中元素向前移动,
直到头指针 front为零, 或者每次出队时, 都将队列中
元素前移一个位置 。 因此, 顺序队列的队满判定条件
为 rear=maxsize。 但是, 在顺序队列中, 这些克服假溢
出的方法都会引起大量元素的移动, 花费大量的时间,
所以在实际应用中很少采用, 一般采用下面的循环队
列形式 。
3,循环队列
为了克服顺序队列中假溢出, 通常将一维数组
queue[0]到 q[maxsize-1]看成是一个首尾相接的圆环,
即 queue[0]与 queue[maxsize-1]相接在一起 。 将这种
形式的顺序队列称为循环队列, 见图 3-11。
队头
队尾
a
n - 1
a
3
a
2
a
1
a
n
a
i
……
……
图 3 - 11 循环队列示意图
在循环队列中, 若 front=rear,则称为队空, 若
(rear+1)%maxsize=front,则称为队满, 这时, 循环队列
中能装入的元素个数为 maxsize-1,即浪费一个存储单元,
但是这样可以给操作带来较大方便 。
4,循环队列上五种运算实现
（ 1） 队列初始化
Void INIQUEUE(seqqueue &q )
{ q.front=q.rear=maxsize-1;
}
(2) 进队列
Void enqueue (seqqueue &q,elemtype x)
{
if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”;
else { q.rear=(q.rear+1)%maxsize;
q.queue[q.rear]=x;
}
}
(3) 出队列
Void dlqueue(seqqueue &q )
{
if (q.rear= =q.front) cout<<”underflow”;
else
q.front =(q.front+1)%maxsize;
}
(4) 取队头元素 （ 注意得到的应为头指针后面一个位置
值 ）
elemtype gethead(seqqueue q )
{ if (q.rear= =q.front)
{ cout<<”underflow”； return NULL;}
else return q.queue[(q.front+1)%maxsize];
}
(5) 判队列空否
int empty(seqqueue q )
{ if (q.rear= =q.front) reurn 1;
else return 0; }
3.2.5 链队列
1 。 链队列的数据类型描述
队列的链式存储，称为链队列，与前面介绍的单链表
类似，但为了使头指针，尾指针统一起来，另外定义
一种数据类型如下。
Struct link //定义单链表数据类型
{ elemtype data;
link *next;};
struct linkqueue //定义链队列数据类型
{ link *front,*rear; //定义头指针和尾指针
};
r e a r
头 ^
f r o n t
a n ^ 头
f r o n t
a 1 …… a 2
r e a r
（ a ）空链队列 ( b ) 非空链队
链队列示意图
2 。 链队列上的基本运算
同样，链队列上也可以给出五种运算如下：
（ 1） 链队列上的初始化
void INIQUEUE(linkqueue( &s)
{ link *p;
p=new link;
p->next=NULL;
s.front=p;
s.rear=p;
}
(2) 入队列
void push(linkqueue &s,elemtype x)
{
link *p;
p=new link;
p->data=x;
p->next=s.rear->next;
s.rear->next=p;
s.rear=p;
}
(3) 判队空
int empty(linkqueue s)
{ if (s.front= =s.rear) return 1;
else return 0;
}
(4) 取队头元素
elemtype gethead(linkqueue s)
{ if (s.front= =s.rear) return NULL;
else retuen s.front->next->data;
}
(5) 出队列
void pop(linkqueue &s)
{ link *p;
p=s.front->next;
if (p->next= =NULL) //链队列中只有一个队头元素,
无其它元素
{s.front->next=NULL;
s.rear=s.front;}
else
s.front->next =p->next;
delete (p);}
从上述出队列算法中可知, 若链队列中只有一个元素
时, 需作特殊处理 (用 if语句判断 ),修改队尾指针 。 为
了避免修改队尾指针, 我们可以采用一种改进的出队
列算法 。 其基本思想是：出队列时, 修改头指针, 删
除头结点而非队头结点, 这时, 将队头结点成为新的
头结点, 队列中第二个结点成为队头结点 。 这时, 不
管队列中有多少个元素, 都不需作特殊处理 （ 不需用 if
语句来判断 ）, 这种改进的算法如下：
void pop(linkqueue &s)
{ link *p;
p=s.front;
s.front=p->next;
delete (p);}
3.2.6 队列的应用
队列在日常生活中和计算机程序设计中, 有着非常重要
的作用, 在此, 仅举出两个方面例子来说明它, 其它应
用在后面章节中将会遇到 。
第一个例子就是 CPU资源的竞争问题 。 在具有多个终端的
计算机系统中, 有多个用户需要使用 CPU各自运行自己的
程序, 它们分别通过各自终端向操作系统提出使用 CPU的
请求, 操作系统按照每个请求在时间上的先后顺序, 将其
排成一个队列, 每次把 CPU分配给队头用户使用, 当相应
的程序运行结束, 则令其出队, 再把 CPU分配给新的队头
用户, 直到所有用户任务处理完毕 。
第二个例子就是主机与外部设备之间速度不匹配的问
题 。 以主机和打印机为例来说明, 主机输出数据给打
印机打印, 主机输出数据的速度比打印机打印的速度
要快得多, 若直接把输出的数据送给打印机打印, 由
于速度不匹配, 显然是不行的 。 所以解决的方法是设
置一个打印数据缓冲区, 主机把要打印输出的数据依
此写如到这个缓冲区中, 写满后就暂停输出, 继而去
做其它的事情, 打印机就从缓冲区中按照先进先出的
原则依次取出数据并打印, 打印完后再向主机发出请
求, 主机接到请求后再向缓冲区写入打印数据, 这样
利用队列既保证了打印数据的正确, 又使主机提高了
效率 。
