文档介绍：第3章 栈和队列
队列
栈
本章小结
1
栈的基本概念
栈的顺序存储结构
栈的链式存储结构
栈
2
栈是一种特殊的线性表，这种线性表上的插入和删除运算限值top=-1。如果作出栈运算，则会“下溢”。
13
顺序栈进栈和出栈示意图
top
-1
top
top
top
14
顺序栈类型定义如下：
顺序栈被定义为一个结构体类型，它有两个域：data和top。Data为一个一维数组，用于存储栈中元素，ElemType为栈元素的数据类型，可以根据需要而指定为某种具体的类型。top为int型，它的实际取值范围为0 ~ StackSize-1。top=-1表示栈空；top=StackSize-1表示栈满。
const int StackSize=100; //顺序栈的初始分配空间 typedef struct sqst
{
ElemType data[StackSize]；//保存栈中元素
int top； //栈指针
} SqStack；
15
顺序栈的基本运算算法如下:
(1)初始化栈运算算法
此算法主要用于创建一个空栈,并将栈顶下标top初始化为-1。
void InitStack(SqStack &st) //st为引用型参数
{
=-1;
}
16
(2)进栈运算算法
其主要操作是：栈顶下标加1,将进栈元素放进栈顶下标所指的位置上。
int Push(SqStack &st, ElemType x)
{ if (==StackSize-1) //栈满
return 0;
else
{ ++;
[]=x;
return 1;
}
}
17
(3)出栈运算算法
其主要操作是：先将栈顶元素取出，然后将栈顶下标减1。
int Pop(SqStack &st, ElemType &x) //x为引用型参数
{ if (==-1)
return 0;
else
{ x=[];
--;
return 1;
}
}
18
(4)取栈顶元素运算算法
其主要操作是：将栈中top处的元素取出赋给变量x。
int GetTop(SqStack st, ElemType &x)
{
if (==-1) //栈空
return 0;
else
{ x=[];
return 1;
}
}
19
(5)判断栈空运算算法
其主要操作是：若栈为空（top==-1）则返回值1，否则返回0。
int StackEmpty(SqStack st)
{ if (==-1)
return 1;
else
return 0;
}
20
设计一个算法，判断一个表达式中符号“（”与“）”、“[”与“]”、“{”与“}”是否匹配。若匹配，则返回1；否则返回0。
解:设置一个栈st,用i扫描表达式exps：遇到(、[和{时，将其进栈,遇到）、]和}时,判断栈顶是否是匹配的括号。若不是，则退出扫描过程，返回0；否则直到exps扫描完毕为止。若top==0，则返回1。对应算法如下：(以下为完整程序）
#include <>
const int Max=100;
int match(char *exps)
{ char st[Max],top=-1,i=0;
int nomatch=0;
while (exps[i]!=‘\0’&& nomatch==0)
21
{ switch(exps[i])
{ ca