第3章栈和队列1.doc
文本预览下载声明
第3章 栈和队列
栈和队列是两种重要的线性结构。它们的共同特点是：操作受限（插入元素和删除元素只能在端点处进行）的线性表。
3.1 栈
3.1.1 抽象数据类型栈的定义
什么是栈（Stack）：栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊的含义，称为栈顶（Top），相应地，表头端称为栈底（Bottom）。不含元素的栈称为空栈。
栈在生活中的例子：蒸小茏包，先放下去的最后才拿出来。
栈：是先进后出（First In Last Out，FILO）的线性表，也可称为后进先出（Last in First Out，LIFO）。对应的一个名词：先进先出First In First Out（FIFO）。通常栈可用下图来表示：
假设插入元素的序列为：49,27,36,57,63,89,16，这个过程称为入栈。其过程为：将元素放到当前栈顶指向的空间，然后，栈顶移动一个位置。
出栈：就是将元素从栈顶元素处删除。其过程为：先将栈顶向下移动一个位置，再将该元素拷贝出来。
典型的题目：如果有4个元素：a b c d，依次入栈，其中又陆续出栈，问有哪些合法的出栈顺序？
1）a b c d ？可以
2）a b d c ？可以
3）c b d a ？可以
4）c a d b ？不可能
抽象数据类型的定义：
ADT Stack{
数据对象：
数据关系：
基本操作：
1）InitStack，初始化栈
2）DestroyStack，销毁栈，栈的空间释放了
3）ClearStack，将一个栈清空，栈的空间还在
4）StackEmpty，判断一个栈是否是空栈，返回True或False
5）StackLength，求栈的长度，也就是求栈中还有几个元素
6）GetTop，返回栈顶元素，但该元素还在栈中
7）Push，元素入栈
8）Pop，栈顶元素出栈
9）遍历：StackTraverse，从栈底到栈顶元素，依个进行访问。
3.1.2 栈的表示和实现
栈有两种表示：顺序表示（顺序栈）、链式表示（链表栈）。
所谓顺序栈，就是用一个顺序表（数组）来存储栈的元素。显然，我们需要这些数据：存储元素的空间的首地址、栈顶指针、栈的空间总大小。就得到下列结构体：
1、顺序栈的第一种实现：
typedef struct{
SElemType *base; //存储元素的空间的首地址，可用malloc函数申请空间，将地址赋给它
SElemType *top; //栈顶指针，指的是当前栈顶元素的上面的那个位置，初始时，top指向base
int stacksize; //当前栈的最大空间大小，用来判断栈是否已经满了，从而可以采取必要的措施。
}SqStack;
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
SqStack S; //定义一个栈的变量S
1）初始化栈函数
Status InitSqStack( SqStack S)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); //申请100个空间
if(!S.base) exit(-1); //申请空间失败，直接退出程序
S.top=S.base;
S.stacksize= STACK_INIT_SIZE;
return OK;
}
2）判断一个栈是否是空栈
Status SqStackEmpty( SqStack S )
{
if( S.top==S.base )
return TRUE;
else
return FALSE;
}
3）清空一个栈
Status ClearSqStack( SqStack S )
{
S.top=S.base;
return OK;
}
4）销毁一个栈
Status DestroySqStack( SqStack S )
{
free( S.base );
S.base=S.top=NULL;
S.stacksize=0;
return OK;
}
5）求栈的长度
int SqStackLength( SqStack S )
{
return S.top-S.base;
}
6）入栈
Status PushSqStack( SqStack S, SElemType e )
{
if( S.top-S.base=S.stacksize ) //栈的空间满了
{
S.base=(SElemType*)realloc( S.base, (S.stacksize+10)*s
显示全部