一、栈
1. 栈的定义
栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅答应在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则为进栈；射击时子弹总是从顶部一个接一个地被射出，此为子弹出栈。
由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表(Last In First Out, 简称LIFO)。
例如，假定一个栈S为（a,b,c），其中字符c的一端为栈顶，字符c为栈顶元素。若向S压入一个元素d，则S变为（a,b,c,d），此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d，接着删除的使元素c，栈S变为（a,b），栈顶元素为b。
2. 栈的存储结构 栈既然是一种线性表，所以线性表的顺序存储和链接存储结构同样适用于栈。 (1) 栈的顺序存储结构 栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。假定栈数组用stack[StackMaxSize]表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储类型可定义为： ElemType stack[StackMaxSize]; int top; 其中，StackMaxSize为一个整型全局常量，需事先通过const语句定义，由它确定顺序栈（即顺序存储的栈）的最大深度，又称为长度，即栈最多能够存储的元素个数；由于top用来指示栈顶元素的位置，所以把它称为栈顶指针。 栈的顺序存储结构同样可以定义在一个记录类型中，假定该记录类型用Stack表示，则定义为： struct Stack { ElemType stack[StackMaxSize]; int top; }; 在顺序存储的栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指示前一个元素成为新的栈顶元素。由此可知，对顺序栈的插入和删除运算相当于是在顺序表（即顺序存储的线性表）的表尾进行的，其时间复杂度为O(1)。 设一个栈S为（a,b,c,d,e），对应的顺序存储结构如图4-1(a)所示。若向S中插入一个元素f，则对应如图4-1(b)所示。若接着执行两次出栈操作后，则栈S对应如图4-1(c)所示。若依次使栈S中的所有元素出栈，则s变为空，如图4-1(d)所示。在图4-1中栈是垂直画出的，并且使下标编号向上递增，这样可以形象地表示出栈顶在上，栈底在下。
图4-1 栈的顺序存储结构及操作过程
在一个顺序栈中，若top已经指向了StackMaxSize-1的位置，则表示栈满，若top的值已经等于-1，则表示栈空。向一个满栈插入元素和从一个空栈删除元素都是不答应的，应该停止程序运行或进行非凡处理。
(2) 栈的链接存储结构
栈的链接存储结构与线性表的链接存储结构相同，是通过由结点构成的单链表实现的，此时表头指针被称为栈顶指针，由栈顶指针指向的表头结点被称为栈顶结点，整个单链表被称为链栈，即链接存储的栈。当向一个链栈插入元素时，是把该元素插入到栈顶，即使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则修改为指向该元素结点，使该结点成为新的栈顶结点。当从一个链栈中删除元素时，是把栈顶元素结点删除掉，即取出栈顶元素后，使栈顶指针指向原栈顶结点的后继结点。由此可知，对链栈的插入和删除操作是在单链表的表头进行的，其时间复杂度为O(1)。
设一个栈为（a,b,c），当采用链接存储时，对应的存储结构示意图如图4-2(a)所示，其中HS表示栈顶指针，其值为存储元素c结点的地址。当向这个栈插入一个元素d后，对应如图4-2(b)所示。当从这个栈依次删除两个元素后，对应如图4-2(c)所示。当链栈中的所有元素全部出栈后，栈顶指针HS的值为空，即常量NULL所表示的数值0。
图4-2 栈的链接存储结构及操作过程
3. 栈的抽象数据类型
栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一种存储结构实现；操作部分包括元素进栈、出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义。
ADT STACK is
Data:
采用顺序或链接方式存储的栈，假定其存储类型用StackType
标识符表示。
Operation:
void InitStack(StackType& S);
// 初始化栈S，即把它置为空
void ClearStack(StackType& S);
// 清除栈S中的所有元素，使之成为一个空栈
int StackEmpty(StackType& S);
// 判定S是否为空，若是则返回1，否则返回0
ElemType Peek(StackType& S)
// 返回S的栈顶元素，但不移动栈顶指针
void Push(StackType& S, const ElemType& item)
// 元素item进栈，即插入到栈顶
ElemType Pop(StackType& S)
// 删除栈顶元素并返回之
int StackFull(Stack& S)
// 若栈已满则返回1，否则返回0，此函数为顺
// 序存储的栈所特有
end STACK
对于判定栈是否为空和返回栈顶元素的两种操作，由于它们不改变栈的状态，所以可在参数类型说明前使用常量定义符const。
假定栈a的元素类型为int，下面给出调用上述栈操作的一些例子。
(1) InitStack(a); // 把栈a置空
(2) Push(a,35); // 元素35进栈
(3) int x=48; Push(a,x); // 48进栈
(4) Push(a,x/2); // x除以2的值24进栈
(5) x=Pop(a); // 栈顶元素24退栈并赋给x
(6) x=Peek(a); // 读取栈顶元素48并赋给x
(7) Pop(a); // 栈顶元素48退栈
(8) StackEmpty(a); // 因栈非空，应返回0
(9) cout<<Pop(a)<<endl; // 栈顶元素35退栈并输出
(10) x=StackEmpty(a); // 因栈为空，应返回1，然后赋给x
4. 栈运算的实现
栈运算（操作）的具体实现取决于栈的存储结构，存储结构不同，其算法描述也不同。下面分别给出栈的运算在顺序存储结构和链接存储结构上实现的具体算法。
(a) 栈的操作在顺序存储结构上的实现
假定采用顺序存储结构定义的栈用标识符S 表示，其类型为已经给出过的Stack记录类型。
(1) 初始化栈
void InitStack(Stack& S)
// 初始化栈S，即把它置为空
{
S.top=-1;
}
(2) 把一个栈清除为空
在顺序存储方式下，同初始化栈的算法相同。
void ClearStack(Stack& S)
// 清除栈S中的所有元素，使之成为一个空栈
{
S.top=-1;
}
(3) 检查一个栈是否为空
int StackEmpty(Stack& S)
// 判定S是否为空，若是则返回1，否则返回0
{
return S.top==-1;
}
(5) 读取栈顶元素
ElemType Peek(StackType& S)
// 返回S的栈顶元素，但不移动栈顶指针
{
// 若栈为空则终止程序运行
if(S.top==-1) {
cerr<<"Stack is empty!"<<endl;
exit(1);
}
// 返回栈顶元素的值
return S.stack[S.top];
}
(5) 向栈中插入元素
void Push(Stack& S, const ElemType& item)
// 元素item进栈，即插入到栈顶
{
// 若栈已满则终止程序运行
if(S.top==StackMaxSize-1) {
cerr<<"Stack overflow!"<<endl;
exit(1);
}
// 将栈顶指针后移一个位置
S.top++;
// 将item的值赋给新的栈顶位置
S.stack[S.top]=item;
}
(6) 从栈中删除元素
ElemType Pop(StackType& S)
// 删除栈顶元素并返回之
{
// 若栈为空则终止程序运行
if(S.top==-1) {
cerr<<"Stack is empty!"<<endl;
exit(1);
}
// 暂存栈顶元素以便返回
ElemType temp=S.stack[S.top];
// 栈顶指针前移一个位置
S.top--;
// 返回原栈顶元素的值
return temp;
}
从出栈算法可以看出，原栈顶元素的值没有被改变，所以可以不使用临时变量保存它，返回语句中返回S.stack[S.top+1]的值即可。
(7) 检查栈是否已满
int StackFull(Stack& S)
// 若栈已满则返回1，否则返回0，此函数为顺序栈所特有
{
return S.top==StackMaxSize-1;
}
(b) 栈的操作在链接存储结构上的实现
假定链栈中的结点仍采用在第二章中已经定义的LNode结点类型，并假定栈顶指针用HS表示，下面给出对由HS所指向的链栈进行每一种栈操作的算法。
(1) 初始化链栈
void InitStack(LNode*& HS)
{
HS=NULL; // 将链栈置空。
}
(2) 清除链栈为空
void ClearStack(LNode*& HS)
{
LNode *cp, *np;
// 用cp作为指向待删除的结点，np指向cp的后继结点。
cp=HS; // 给cp指针赋初值，使之指向栈顶结点。
while(cp!=NULL)
{ // 从栈顶到栈底依次删除每个结点
np=cp->next;
delete cp;
cp=np;
}
HS=NULL; // 置链栈为空
}
(3) 检查链栈是否为空
int StackEmpty(LNode* HS)
// HS为值参或引用形参均可
{
return HS==NULL;
}
(4) 读取栈顶元素
ElemType Peek(LNode* HS) // HS为值参或引用形参均可
{
if(HS==NULL) {
cerr<<"Linked stack is empty!"<<endl;
exit(1);
}
return HS->data;
}
(5) 向链栈中插入一个元素
void Push(LNode*& HS, const ElemType& item)
{
// 为插入元素获取动态结点
LNode* newptr= new LNode;
if(newptr==NULL) {
cerr<<"Memory allocation failare!"<<endl;
exit(1);
}
// 给新分配的结点赋值
newptr->data=item;
// 向栈顶插入新结点
newptr->next=HS;
HS=newptr;
}
(6) 从链栈中删除一个元素
ElemType Pop(LNode*& HS)
{
if(HS==NULL) {
cerr<<"Linked stack is empty!"<<endl;
exit(1);
}
LNode* p=HS; // 暂存栈顶结点
HS=HS->next; // 使栈顶指针指向其后继结点
ElemType temp=p->data; // 暂存原栈顶元素
delete p; // 回收原栈顶结点
return temp; // 返回原栈顶元素
}
5. 栈的简单应用举例
例1. 从键盘上输入一批整数，然后按照相反的次序打印出来。
根据题意可知，后输入的整数将先被打印出来，这正好符合栈的后进先出的特点。所以此题很轻易用栈来解决。参考程序如下：
#include<iostream.h>
#include<stdlib.h>
const int StackMaxSize=30;
typedef int ElemType; // 定义元素类型为整型
struct Stack {
ElemType stack[StackMaxSize];
int top;
};
#include"stack.h"
// 假定对顺序栈操作的算法已经存于"stack.h"头文件中
void main()
{
Stack a;
InitStack(a);
int x;
cin>>x;
while(x!=-1) {
// 假定用-1作为终止键盘输入的标志，输入的整数个数
// 不能超过StackMaxSize所规定的值
Push(a,x);
cin>>x;
}
while(!StackEmpty(a)) // 栈不为空时依次退栈打印出来
cout<<Pop(a)<<" ";
cout<<endl;
}
假定从键盘上输入为：
78 63 45 82 91 34 -1
则输出为：
34 91 82 45 63 78
例2. 堆栈在计算机语言的编译过程中用来进行语法检查，试编写一个算法，用来检查一个C++语言程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。
在这个算法中，需要扫描待检查程序中的每一个字符，当扫描到每个花、中、圆左括号时，令其进栈，当扫描到每个花、中、圆右括号时，则检查栈顶是否为相应的左括号，若是则作退栈处理，若不是则表明出现了语法错误，应返回0。当扫描到程序文件结尾后，若栈为空则表明没有发现括号配对错误，应返回1，否则表明栈中还有未配对的括号，应返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。
根据分析，编写出算法如下：
int BracketsCheck(char* fname)
// 对由fname所指字符串为文件名的文件进行括号配对检查
{
ifstream ifstr(fname, ios::in|ios::nocreate);
// 用文件输入流对象ifstr打开以fname所指字符串为文件名的文件
if(!ifstr) {
cerr<<"File"<<"\'"<<fname<<"\'"<<"not found!"<<endl;
exit(1);
}
Stack a; // 定义一个顺序栈
InitStack(a); // 栈a初始化
char ch;
while(ifstr>>ch) // 顺序扫描文件中的每一个字符
{
if(ch==39) { // 单引号内的字符不参与配对比较
while(ifstr>>ch)
if(ch==39) // 39为单引号的ASCII值
break;
if(!ifstr)
return 0;
}
else if(ch==34) { // 双引号内的字符不参与配对比较
while(ifstr>>ch)
if(ch==34) // 34为双引号的ASCII值
break;
if(!ifstr)
return 0;
}
switch (ch)
{
case '{':
case '[':
case '(':
Push(a,ch); // 出现以上三种左括号则进栈
break;
case '}':
if(Peek(a)=='{')
Pop(a); // 栈顶的左花括号出栈
else
return 0;
break;
case ']':
if(Peek(a)=='[')
Pop(a); // 栈顶的左中括号出栈
else
return 0;
break;
case ')':
if(Peek(a)=='(')
Pop(a); // 栈顶的左圆括号出栈
else
return 0;
}
}
if(StackEmpty(a))
return 1;
else
return 0;
}
例3. 把十进制整数转换为二至九之间的任一进制数输出。
由计算机基础知识可知，把一个十进制整数x转换为任一种r进制数得到的是一个r进制的整数，假定为y，转换方法是逐次除基数r取余法。具体叙述为：首先用十进制整数x除以基数r，得到的整余数是r进制数y的最低位y0，接着以x除以r的整数商作为被除数，用它除以r得到的整余数是y的次最低位y1，依次类推，直到商为0时得到的整余数是y的最高位ym，假定y共有m+1位。这样得到的y与x等值，y的按权展开式为：
y=y0+y1.r+y2.r2+...+ym.rm
例如，若十进制整数为3425，把它转换为八进制数的过程如图4-3所示。
图4-3 十进制整数3425转换为八进制数的过程
最后得到的八进制数为(6541)8，对应的十进制数为6×83+5×82+4×8+1=3425，即为被转换的十进制数，证实转换过程是正确的。
从十进制整数转换为r进制数的过程中，由低到高依次得到r进制数中的每一位数字，而输出时又需要由高到低依次输出每一位。所以此问题适合利用栈来解决，具体算法描述为：
void Transform(long num, int r)
// 把一个长整型数num转换为一个r进制数输出
{
Stack a; // 利用栈a存储转换后得到的每一位数字
InitStack(a); // 初始化栈
while(num!=0)
{ // 由低到高求出r进制数的每一位并入栈
int k=num % r;
Push(a,k);
num/=r;
}
while(!StackEmpty(a)) // 由高到低输出r进制数的每一位
cout<<Pop(a);
cout<<endl;
}
假定用下面的主程序调用Transform过程。
void main()
{
cout<<"3425的八进制数为：";
Transform(3425,8);
cout<<"3425的六进制数为：";
Transform(3425,6);
cout<<"3425的四进制数为：";
Transform(3425,4);
cout<<"3425的二进制数为：";
Transform(3425,2);
}
则得到的运行结果如下：
3425的八进制数为：6541
3425的六进制数为：23505
3425的四进制数为：311201
3425的二进制数为：110101100001
二、算术表达式的计算
在计算机中进行算术表达式的计算是通过栈来实现的。这一节首先讨论算术表达式的两种表示方法，即中缀表示法和后缀表示法，接着讨论后缀表达式求值的算法，最后讨论中缀表达式转换为后缀表达式的算法。
1. 算术表达式的两种表示
通常书写的算术表达式是由操作数(又叫运算对象或运算量)和运算符以及改变运算次序的圆括号连接而成的式子。操作数可以是常量、变量和函数，同时还可以是表达式。运算符包括单目运算符和双目运算符两类，单目运算符只要求一个操作数，并被放在该操作数的前面，双目运算符要求有两个操作数，并被放在这两个操作数的中间。单目运算符为取正’+’和取负’-’，双目运算符有加’+’,减’-’,乘’*’和除’/’等。为了简便起见，在我们的讨论中只考虑双目运算符。
如对于一个算术表达式2+5*6，乘法运算符’*’的两个操作数是它两边的5和6；对于加法运算符’+’的两个操作数，一个是它前面的2，另一个是它后面的5*6的结果即30。我们把双目运算符出现在两个操作数中间的这种习惯表示叫做算术表达式的中缀表示，这种算术表达式被称为中缀算术表达式或中缀表达式。
中缀表达式的计算比较复杂，它必须遵守以下三条规则：
(1) 先计算括号内，后计算括号外；
(2) 在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；
(3) 同一优先级运算，从左向右依次进行。
从这三条规则可以看出，在中缀表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。因此，各运算符实际的运算次序往往同它们在表达式中出现的先后次序是不一致的，是不可猜测的。当然凭直观判别一个中缀表达式中哪个运算符最先算，哪个次之，……，哪个最后算并不困难，但通过计算机处理就比较困难了，因为计算机只能一个字符一个字符地扫描，要想得到哪一个运算符先算，就必须对整个中缀表达式扫描一遍，一个中缀表达式中有多少个运算符，原则上就得扫描多少遍才能计算完毕，这样就太浪费时间了，显然是不可取的。
那么，能否把中缀算术表达式转换成另一种形式的算术表达式，使计算简单化呢? 回答是肯定的。波兰科学家卢卡谢维奇(Lukasiewicz)很早就提出了算术表达式的另一种表示，即后缀表示，又称逆波兰式，其定义是把运算符放在两个运算对象的后面。采用后缀表示的算术表达式被称为后缀算术表达式或后缀表达式。在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。例如，对于后缀表达式12!4!-!5!/，其中’!’字符表示成分之间的空格，因减法运算符在前，除法运算符在后，所以应先做减法，后做除法；减法的两个操作数是它前面的12和4，其中第一个数12是被减数，第二个数4是减数；除法的两个操作数是它前面的12减4的差(即8)和5，其中8是被除数，5是除数。
中缀算术表达式转换成对应的后缀算术表达式的规则是：把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。
例如，对于下列各中缀表达式：
(1) 3/5+6
(2) 16-9*(4+3)
(3) 2*(x+y)/(1-x)
(4) (25+x)*(a*(a+b)+b)
对应的后缀表达式分别为：
(1) 3!5!/!6!+
(2) 16!9!4!3!+!*!-
(3) 2!x!y!+!*!1!x!-!/
(4) 25!x!+!a!a!b!+!*!b!+!*
2. 后缀表达式求值的算法
后缀表达式的求值比较简单，扫描一遍即可完成。它需要使用一个栈，假定用S表示，其元素类型应为操作数的类型，假定为浮点型float，用此栈存储后缀表达式中的操作数、计算过程中的中间结果以及最后结果。假定一个后缀算术表达式以字符’@’作为结束符，并且以一个字符串的方式提供。后缀表达式求值算法的基本思路是：把包含后缀算术表达式的字符串定义为一个输入字符串流对象，每次从中读入一个字符（空格作为数据之间的分隔符，不会被作为字符读入）时，若它是运算符，则表明它的两个操作数已经在栈S中，其中栈顶元素为运算符的后一个操作数，栈顶元素的下一个元素为运算符的前一个操作数，把它们弹出后进行相应运算即可，然后把运算结果再压入栈S中；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈S中。依次扫描每一个字符（对于浮点数只需扫描它的最高位并一次输入整个浮点数）并进行上述处理，直到碰到结束符’@’为止，表明后缀表达式计算完毕，最终结果保存在栈中，并且栈中仅存这一个值，把它弹出返回即可。具体算法描述为：
float Compute(char* str)
// 计算由str字符串所表示的后缀表达式的值，
// 表达式要以'@'字符结束。
{
Stack S; // 用S栈存储操作数和中间计算结果
InitStack(S); // 初始化栈
istrstream ins(str); // 把str定义为输入字符串流对象ins
char ch; // 用于输入字符
float x; // 用于输入浮点数
ins>>ch; // 从ins流对象(即str字符串)中顺序读入一个字符
while(ch!='@')
{ // 扫描每一个字符并进行相应处理
switch(ch)
{
case '+':
x=Pop(S)+Pop(S);
break;
case '-':
x=Pop(S); // Pop(S)弹出减数
x=Pop(S)-x; // Pop(S)弹出的是被减数
break;
case '*':
x=Pop(S)*Pop(S);
break;
case '/':
x=Pop(S); // Pop(S)弹出除数
if(x!=0.0)
x=Pop(S)/x; // Pop(S)弹出的是被除数
else { // 除数为0时终止运行
cerr<<"Divide by 0!"<<endl;
exit(1);
}
break;
default: // 读入的必为一个浮点数的最高位数字
ins.putback(ch); // 把它重新回送到输入流中
ins>>x; // 从字符串输入流中读入一个浮点数
}
Push(S,x); // 把读入的一个浮点数或进行相应运算
// 的结果压入到S栈中
ins>>ch; // 输入下一个字符，以便进行下一轮循环处理
}
if(!StackEmpty(S))
{ // 若栈中仅有一个元素，则它是后缀表达式的值，否则为出错
x=Pop(S);
if(StackEmpty(S))
return x;
else {
cerr<<"expression error!"<<endl;
exit(1);
}
}
else { // 若最后栈为空，则终止运行
cerr<<"Stack is empty!"<<endl;
exit(1);
}
}
此算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把’@’也看作为一个非凡运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。
假定一个字符串a为：
char a[30]="12 3 20 4 / * 8 - 6 * +@";
对应的中缀算术表达式为12+(3*(20/4)-8)*6@，则使用如下语句调用上述函数得到的输出结果为54。
cout<<Compute(a)<<endl;
在进行这个后缀算术表达式求值的过程中，从第四个操作数入栈开始，每处理一个操作数或运算符后，栈S中保存的操作数和中间结果的情况如图4-4所示。
图4-4 栈S中数据的变化
视频教程列表
文章教程搜索
C语言程序设计推荐教程
C语言程序设计热门教程
|
QQ：2693987339(点击联系)购买教程光盘
:
