5 《数据结构》学习记录：顺序栈

一、概念 1、栈

一种只能在一端进行插入或删除操作的线性表。
【5 《数据结构》学习记录：顺序栈】栈的主要特点是“后进先出” ，即后进栈的元素先出栈。

2、栈的几个概念

允许进行插入、删除操作的一端称为栈顶。
另一端称为栈底。
当栈中没有数据元素时，称为空栈。
栈的插入操作通常称为进栈或入栈。
栈的删除操作通常称为退栈或出栈。

3、顺序栈

利用顺序存储结构实现的栈。

二、顺序栈的基本操作 1、定义栈
#define elemType charconst int MaxSize = 5;struct SqStack{elemType data[MaxSize];int top;//栈顶指针};
2、初始化栈
void InitStack(SqStack *&s){s = new SqStack;s->top = -1;} 3、判断栈是否为空
bool StackEmpty(SqStack *s){return s->top == -1;} 4、进栈

bool Push(SqStack *&s, elemType e){if (s->top== MaxSize - 1)//栈满的情况 ， 即栈上溢出return false;s->top++;//栈顶指针增1s->data[s->top] = e;//元素e放在栈顶指针处return true;}

5、出栈

bool Pop(SqStack *&s, elemType &e){if (s->top == -1)	//栈为空的情况 ， 即栈下溢出return false;e = s->data[s->top];	//取栈顶指针元素的元素s->top--;//栈顶指针减1return true;}

6、取栈顶元素

bool GetTop(SqStack *s, elemType &e){if (s->top == -1)	//栈为空的情况 ， 即栈下溢出return false;e = s->data[s->top];	//取栈顶指针元素的元素return true;}

三、一个例子

bool symmetry(elemType str[]){int i;elemType e;SqStack * st;InitStack(st);//初始化栈for (i = 0;str[i] != '\0';i++)	//将串所有元素进栈Push(st,str[i]);//元素进栈for (i = 0;str[i] != '\0';i++){Pop(st,e);//退栈元素eif (str[i] != e)//若e与当前串元素不同则不是对称串{delete st;	//销毁栈return false;}}delete st;//销毁栈return true;}

四、共享栈