栈的概念栈的存储结构栈的操作算法栈的应用队列的概念队列的存储结构与操作算法队列的操作算法队列的应用3.1 栈 ( Stack )的概念只允许
在一端插入和删除的表允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom)特点 后进先出 (LI
FO)进栈示例 出栈示例例:假定有4个元素A，B，C，D，按所列次序进栈，试写出所有可能的出栈序列。注意，每一个元素进栈后
都允许出栈，如ACDB就是一种出栈序列。解：可能的出栈序列有ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，
BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。栈的基本操作1、初始化2、进栈PUSH3、出栈POP4、取栈
顶元素GetTop5、判栈是否非空3.2 栈的存储结构顺序存储------顺序栈链式存储-------链栈template ass T, int MaxSize > class SeqStack{ T data[MaxSize];
//存放栈元素 int top; //栈顶指针public: SeqStack(
) ; //构造函数 void Push(T x); //入栈 T Po
p( ); //出栈 T Top( ); //取栈顶元素 bool
Empty( ); //判断栈是否为空}; 链式栈的存储链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链
式栈的栈顶在链头template class LinkStack{ Node top;
//栈顶指针public: LinkStack( ); //构造函数 ~Lin
kStack( ); //析构函数 void Push(T x); //入栈
T Pop( ); //出栈 T Top( ); //
取栈顶元素 bool Empty( ); //判断链栈是否为空栈};3.3 栈的操作算法 1. 顺序栈的操作
算法2. 链式栈的操作算法1 顺序栈的操作算法顺序栈的初始化 template Se
qStack::SeqStack( ){ top=-1;}(2) 顺序栈的入栈操作 template lass T,int MaxSize> void SeqStack::Push(T x){ if (t
op== MaxSize-1) {cerr<<"上溢"; exit(1);} top++; data[to
p]=x;} (3) 顺序栈的出栈操作template T SeqStack axSize>::Pop( ){ if (top==-1) {cerr<<"下溢"; exit(1);} x=data
[top]; top--; return x;}(4) 取栈顶元素操作 template MaxSize> T SeqStack::Top( ){ if (top==-1) {cerr<<"下
溢"; exit(1);} return data[top];}(5) 判断顺序栈是否为空 template int MaxSize> bool SeqStack::Empty( ){ return top==-1;}
2 链栈的操作算法(6) 链栈初始化 template LinkStack::LinkStack(
){ top=NULL; } 链栈入栈操作 template void LinkStack::Push( T x) {
s=new Node; s->data=x; s->next=top; top=s; } (8)
链栈出栈操作template T LinkStack::Pop( ){ if (top==NUL
L) {cerr<<"下溢"; exit(1);} x=top->data; p=top; top=t
op->next; delete p; return x;}(9) 取栈顶元素操作 template s T> T LinkStack::Top( ){ if (top==NULL) {cerr<<"下溢"; exit(1
);} return top->data;}(10) 判断链栈是否为空 template bool Link
Stack::Empty( ){ return top==NULL;} (11) 链栈的析构函数template ss T>LinkStack::~LinkStack( ){ p=top; while (p) { q=p; p=p->n
ext; delete q; } top=NULL;}思考：两个栈共享同一段内容空间，为了使得空间利用率最高，应如何分配栈空间？
--------两个堆栈共享空间0maxsize-1lefttoprighttop3.4 栈的应用举例1. 栈的应用之一:
递归调用例: Hanoi塔问题. void Hanoi(int n, char a, char b, char c) {
if (n==1) Move (a, c); else { Hanoi(n-1,a,c,b); Move(a,c);
Hanoi(n-1,b,a,c); } } 一定要搞清执行过程2. 栈的应用之二: 算术表达式求值
表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观的算法，即“算符优先法”。
输入包含+、－、、/、圆括号和正整数组成的中缀算术表达式，以“@”作为表达式结束符。计算该表达式的运算结果。 运算优先级当
前运算符栈顶运算符算法思想： 为实现算符优先算法，使用两个工作栈。 1.运算符OPTR栈, 用以寄存运算符；
2.操作数OPND栈, 用以寄存操作数 或运
算结果。（1）首先置操作数栈OPND为空栈，表达式起始符“@”为运算符的栈底元素；（2）从左到右扫描，依次读入中缀表达式中的每个字
符，依次读入表达式中每个字符, 若是操作数,则进OPND栈，若是运算符，则与OPTR栈的栈顶运算符进行比较，作相应操作，直至整个表
达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“@”）。若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）
进行比较，会出现以下三种情况：① 若pre_op 读入下一个字符；③ 若pre_op>c，则pre_op出栈，并在操作数栈中退栈2次，依次得到操作数b和a，然后进行a pre_op
b运算，并将运算的结果压入操作数栈中。 (举例)算法描述double Expression_Eval() { SeqSt
ack OPTR; // 运算符栈 SeqStack OPND;
// 运算数栈 OPTR.Push(''@''); ch=getchar(); while (ch!=''@'' || OPTR.To
p( )!=''@''){ if (!InOPTR(ch,OP)) { OPND.Push(ch); ch=getcha
r( ); } //读到的是操作数则入栈 else //读到的是操作符 { pre_op=OPT
R.Top( ); switch (Precede(pre_op,ch)) { ca
se ''<'': //情况① OPTR.Push(ch); ch=getchar();
break;case ''='': //情况② OPTR.Pop( ); ch=getchar( ); break;
case ''>'': //情况③ b=OPND.Pop( ); a=OPND.Pop( ); pre_op=
OPTR.Pop( ); OPND.Push(Operate(a, pre_op, b)); break; } } }
return OPND.Top( ); } ▲ 后缀表达式求值中缀表达式?后缀表达式?求值将中缀表达式变成等价的后缀表达式时，
表达式中操作数次序不变，而操作符次序会发生变化，同时去掉圆括号。因此设置一个栈OPTR用以存放操作符。中缀表达式转换为后缀表达式的
基本思路: 从左到右扫描中缀表达式，依次读入表达式中的每个字符，对于不同类型的字符按不情况进行处理。 ① 若读到的是操作
数，则输出该操作数，并读入下一个字符。② 若读到的是左括号，则把它压入到OPTR栈中，并读入下一个字符。③ 若读到的是右括号，则表
明括号内的中缀表达式已经扫描完毕，将OPTR栈从栈顶顶直到左括号之前的操作符依次出栈并输出，然后将左括号也出栈，并读入下一个字符。
④ 若读到的是操作符（c），则应与操作符栈的栈顶元素（pre_op）进行比较：若c>pre_op，则将c入栈，并读下一个字符;若c
<= pre_op，则将pre_op出栈并输出。按照以上过程扫描到中缀表达式结束符@时，把栈中剩余的操作符依次出栈并输出，就得到了
转换后的后缀表达式。书中例子:后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一遍后缀表达式即可。可设置一个栈OPN
D用以存放操作数。后缀表达式求值算法的基本思路：从左到右扫描，依次读入表达式中的每个字符，直至表达式结束。① 若读到的是操作数，则
入栈OPND。② 若读到的是操作符，则在OPND栈中退出2个元素（先退出的在操作符右，后退出的在操作符左），然后用该操作符进行运算
，并将运算结果压入OPND栈中。后缀表达式扫描完毕时，OPND栈中仅有一个元素，即为运算的结果。书中例子:3.5 队列 ( Que
ue )的概念定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rea
r)。特性先进先出(FIFO, First In First Out)队列的基本操作1、构造一个队列2、进队操作-----将新元素
插入队尾3、出队操作------队列头元素出队4、取队列头元素5、判定队列是否为空3.6 队列的存储结构顺序存储------循
环队列链式存储------链队思考: 为什么要构造循环队列? template ze > class SeqQueue{ T data[ MaxSize]; //存放队列
元素 int front, rear; //队头和队尾指针public: SeqQueue(
); //构造函数，置空队 void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队 T GetQueue( );
//取队头元素 bool Empty( ); //判断队列是否为空};1．队列的顺序存储结构 进
队时队尾指针 rear = rear + 1，将新元素按 rear 指示位置加入。 出队时队头指针 front = front
+ 1，再将下标为 front 的元素取出。 思考：上图中，元素再进队，将如何？出现“假上溢”现象 解决办法:将存储数据元素的一维
数组看成是头尾相接的循环结构即循环队列 循环队列的进队和出队队头指针: front = (front + 1) % maxSiz
e;队尾指针: rear = (rear + 1) % maxSize;队列初始化：front = rear = 0;循环队列的
队空队满问题为了方便起见，约定：初始化建空队时，令front=rear=0, 当队空时：front==rear 当队满时：fr
ont==rear 亦成立 因此，只凭等式front=rear 无法判断队空还是队满。 有三种方法处理上述问题： ① 浪费
一个单元。当使用MaxSize-1个单元时即认为是队满, 此时 (rear+1) % MaxSize==fro
nt② 设置一个布尔变量flag。当flag==flase时为空，当flag==true时为满。③ 使用一个计数器记录队列中元素的
个数。如num，当num==0时队空， 当num==MaxSize时队满。2．队列的链式存储结构
template class LinkQueue{ private: Node front, r
ear; public: LinkQueue( ); //构造函数 ~LinkQueue( );
//析构函数 void EnQueue(T x); //将元素x入队 T DeQueue( ); //
将队头元素出队 T GetQueue( ); //取链队列的队头元素 bool Empty( );
//判断链队列是否为空};3.7 队列的操作算法 1．循环队列的操作 2．链队列的操作1．循环队
列的操作（1）循环队列的初始化template SeqQueue >:: SeqQueue (){ front=rear=0;}（2）循环队列的入队操作template t MaxSize> void SeqQueue::
EnQueue(T x){ if ((rear+1) % MaxSize ==front)
{ cerr<<"上溢"; exit(1);} rear=(rear+1) % MaxSize; data[rear
]=x; 队尾处插入元素}（3）循环队列的出队操作template T SeqQueu
e::DeQueue( ){ if (rear==front) { cerr<<"下溢"; exi
t(1);} front=(front+1) % MaxSize; return data[front];}（4）判断循环队列是
否为空template bool SeqQueue::Empty
( ){ return rear==front; }2．链队列的操作 (1) 链队列的初始化 templat
e LinkQueue::LinkQueue( ){ s=new Node; s->next=NUL
L; front=rear=s;}（2）链队列入队操作template void LinkQueue::
EnQueue(T x){ s=new Node; s->data=x; s->next=NULL; rear->next
=s; //将结点s插入到队尾 rear=s; //将队尾指针指向结点s} (3) 链队列
的出队操作 template T LinkQueue::DeQueue(){ if (rear==
front) {cerr<<"下溢"; exit(1);} p=front->next; x=p->data;
front->next=p->next; if (p->next==N
ULL) rear=front; delete p; return x;} 3.8 队列的应用示例 （1）问题描述设
有n个人排成一列，从前往后“0，1”连续报数。凡是报到“0”的人出列，凡是报到“1”的人立即站到队伍的最后。反复进行报数，直到所有
人均出列为止。要求给出这n个人的出列顺序。例如，n=5时，初始序列为1、2、3、4、5， 出队序列为1、3、5、
4、2。（2）数据结构的设计 将n个人排成的队伍用队列模拟。 采用链队列存储结构。 （3）算法的设计 实质上是一个反复出队和入队的问题，即凡是报到“0”的人出列，凡是报到“1”的人入队，直至队列为空。 算法的基本思想是： 反复执行以下步骤，直至队列为空。① 将队头元素出队，并输出其编号。② 若队列不空，则再出队一个元素，并将该元素再次入队。void Number(){ LinkQueue linkq; for (i=1;i<=n;i++) linkq.EnQueue(i); while (!linkq.Empty()) { x=linkq.DeQueue( ); cout<
|
|
