栈的顺序存储(顺序栈的实现、基本运算以及共享栈)和链式存储
1. 栈的顺序存储结构
1) 顺序栈的实现
栈的顺序存储称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据 元素,同时附设一个指针(top)指示当前栈顶的位置。栈的顺序存储类型可描述为:
#define MaxSize 50 //定义栈中元素的最大个数 typedef struct{ Elemtype data[MaxSize]; //存放找中元素 int top; // 栈顶指针 }SqStack;
栈顶指针:S.top,初始时设置S.top=-1;栈顶元素:S.data[S.top]。
进栈操作:栈不满时,栈顶指针先加1,再送值到栈顶元素。
出栈操作:栈非空时,先取栈顶元素值,再将栈顶指针减1。
栈空条件:S.top=-1;栈满条件:S.top==MaxSize-1;栈长:S.top+1。
由于顺序栈的入栈操作受数组上界的约束,当对栈的最大使用空间估计不足时,有可能 发生栈上溢,此时应及时向用户报告消息,以便及时处理,避免出错。
图3-2 栈顶指针和栈中元素之间的关系
2) 顺序栈的基本运算
栈操作的示意图如图3-2所示,图3-2 (a)是空栈,图3-2 (c)是A、B、C、D、E共5 个元素依次入栈后的结果,图3-2 (d)是在图3-2 (c)之后E、D、C相继出栈,此时栈中还 有2个元素,或许最近出栈的元素C、D、E仍在原先的单元存储着,但top指针已经指向了 新的栈顶,则元素C、D、E已不在栈中了,读者应通过该示意图深刻理解栈顶指针的作用。 下面是顺序桟上常用的基本运算的实现。1) 初始化
void InitStack(&S){ s.top=-1; //初始化栈顶指针 }
2) 判栈空
bool StackEmpty(S){ if(s.top==-1) //栈空 return true; else //不空 return false; }
3) 进栈
bool Push(SqStack &S, ElemType x) { if(S.top==MaxSize-1) //栈满,报错 return false; S.data[++S.top] = x; //指针先加 1,再入栈 return true; }
4) 出栈
bool Pop(SqStack &S, ElemType &x){ if(S.top==-1) // 栈空,报错 return false; x=S.data [S.top--]; //先出栈,指针再减1 return true; }
5) 读栈顶元素
bool GetTop(SqStack S,ElemType &x){ if (S.top==-1) //找空,报错 return false; x=S.data[S.top]; //x记录栈顶元素 return true; }
注意:这里栈顶指针指向的就是栈顶元素,所以进栈时的操作是S.data[++S.top]=x,出 栈时的操作是x=S.data[S.top--]。如果栈顶指针初始化为S.top=0,即栈顶指针指向栈顶元素 的下一个位置,则入栈操作变为S.data[S.top++]=x,出栈操作变为x=S.data[--S.top]。相应的 栈空、栈满条件也会发生变化。请读者仔细体会其中的不同之处,做题时也应灵活应变。
3) 共享栈
利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的 栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸,如图3-3所示。图3-3 两个顺序栈共享存储空间
两个栈的栈顶指针都指向栈顶元素,top0=-1 时0号桟为空,top1=MaxSize时1号栈为 空;仅当两个栈顶指针相邻(top1-top0=1) 时,判断为栈满。当0号栈进栈时top0先加1 再赋值,1号栈进栈时top1先减1再赋值;出栈时则刚好相反。
共享栈是为了更有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被 占满时才发生上溢。其存取数据的时间复杂度均为0(1),所以对存取效率没有什么影响。
2. 栈的链式存储结构
釆用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且 不存在栈满上溢的情况。通常釆用单链表实现,并规定所有操作都是在单链表的表头进行的。 这里规定链栈没有头结点,Lhead指向栈顶元素,如图3-4所示。图3-4 栈的链式存储
栈的链式存储类型可描述为
typedef struct Linknode{ ElemType data; //数据域 struct Linknode *next; //指针域 } *LiStack; //栈类型定义
釆用链式存储,便于结点的插入与删除。链栈的操作与链表类似,在此不做详细讨论。 读者需要注意的是,对于带头结点和不带头结点的链栈,在具体的实现方面有所不同。