数据结构——栈

目录

一、栈的定义与特性

（1）定义

（2）特性

二、栈的基本操作

三、顺序栈（栈的顺序存储结构）

1、顺序栈的类型定义

2、顺序栈基本操作的实现

四、栈的应用

一、栈的定义与特性

（1）定义

栈是一种插入操作与删除操作限制在同一端进行的特殊线性表

栈顶（top）：进行插入与删除操作的一端

栈底（bottom）：另一端

空栈：不含任意元素的栈

（2）特性

后进先出(LIFO—Last In First Out)    

先进后出(FILO—First In Last Out)

二、栈的基本操作

设栈抽象数据类型为Stack，常用的基本操作有：

	操作函数	初始条件	操作结果
初始化操作	InitStack(&S)	栈 S 不存在	构造一个初始空栈 S
销毁操作	destroyStack(&S)	栈 S 已存在	将栈 S 销毁，释放栈的存储空间
判空操作	stackIsEmpty(S)	栈 S 已存在	判断栈 S 是否为空；若栈为空则返回TURE， 否则返回 FALSE
清空操作	clearStack(&S)	栈 S 已存在	将栈 S 清空，变为空栈
入栈操作	Push(&S, e)	栈 S 已存在，e 为给定数据元素值	将给定值为 e 的元素入栈，即将 e 在栈 S 的栈顶端插入
出栈操作	Pop(&S, &e)	栈 S 已存在且非空	将栈 S 的栈顶元素出栈，即将栈顶元素删除，并通过 参数 e 返回出栈元素的值
取栈顶操作	getTop(S, &e)	栈 S 已存在且非空	取栈 S 的栈顶元素的值，将其值通过参数 e 返回
求栈长操作	stackLength(S)	栈 S 已存在	求栈 S 的长度，即栈中的元素个数；当栈 S非空时， 函数返回该栈的长度；而当栈 S为空时则返回 0
遍历操作	stackTraverse(S, visit())	栈 S 已存在； visit()为元素的访问函数	依照从栈底到栈顶的顺序依次访问栈 S 的元素，且每个元素只被访问一次

三、顺序栈（栈的顺序存储结构）

1、顺序栈的类型定义

#define StackSpaceIncr 20                    

struct{      

        SElemType *base;

         int top;                              

         int stackSize;            

}SqStack ; 

2、顺序栈基本操作的实现

（1）初始化操作  InitSqStack(&S, InitSize)

Status InitSqStack(SqStack &S, int InitSize)
{S.base = (SElemType *)malloc(InitSize * sizeof(SElemType) );if(!S.base) return OVERFLOW;    S.stackSize = InitSize;S.top = 0;return OK;}

（2）判空操作、清空操作与求栈长操作

Status stackIsEmpty(SqStack S)
{if( !S.top ) return TRUE;else return FALSE;}void clearStack(SqStack &S)
{S.top=0;}int stackLength(SqStack S)
{return S.top;}

（3）入栈操作 Push(&S, e)

Status Push(SqStack &S, SElemType e)
{SElemType *newBase;if( S.top==S.stackSize ){   newBase=(SElemType*)realloc( S.base,    (S.stackSize+StackSpaceIncr)* sizeof(SElemType) );if(!newBase) return OVERFLOW;  S.base=newBase;S.stackSize+=StackSpaceIncr;         }S.base[S.top] = e;               S.top++;                            return OK;}

（4）出栈操作 Pop(&S, &e)

Status Pop(SqStack &S, SElemType &e)
{if( !S.top ) return ERROR;    S.top-- ;    e=S.base[S.top];                       return OK;}

四、栈的应用

1.简单的行编辑程序  

2.迷宫问题