|
顺序栈 栈的顺序存储结构简称为顺序栈它是运算受限的顺序表 顺序栈的类型定义 #define StackSize //假定预分配的栈空间最多为个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{ DataType data[StackSize]; int top; }SeqStack; 注意 ①顺序栈中元素用向量存放 ②栈底位置是固定不变的可设置在向量两端的任意一个端点 ③栈顶位置是随着进栈和退栈操作而变化的用一个整型量top(通常称top为栈顶指针)来指示当前栈顶位置 顺序栈的基本操作 前提条件 设S是SeqStack类型的指针变量若栈底位置在向量的低端即S>data[]是栈底元素 () 进栈操作 进栈时需要将S>top加 注意 ①S>top==StackSize表示栈满 ② 上溢 现象当栈满时再做进栈运算产生空间溢出的现象 上溢是一种出错状态应设法避免 () 退栈操作 退栈时需将S>top减 注意 ①S>top<表示空栈 ② 下溢 现象——当栈空时做退栈运算产生的溢出现象 下溢是正常现象常用作程序控制转移的条件 顺序栈在进栈和退栈操作时的具体变化情况 顺序栈的基本运算 () 置栈空 void InitStack(SeqStack *S) {//将顺序栈置空 S>top=; } () 判栈空 int StackEmpty(SeqStack *S) { return S>top==; } () 判栈满 int StackFull(SeqStack *SS) { return S>top==StackSize; } () 进栈 void Push(Sx) { if (StackFull(S)) Error(Stack overflow); //上溢退出运行 S>data[++S>top]=x;//栈顶指针加后将x入栈 } () 退栈 DataType Pop(S) { if(StackEmpty(S)) Error(Stack underflow); //下溢退出运行 return S>data[S>top];//栈顶元素返回后将栈顶指针减 } () 取栈顶元素 DataType StackTop(S) { if(StackEmpty(S)) Error(Stack is empty); return S>data[S>top]; } 两个栈共享同一存储空间 当程序中同时使用两个栈时可以将两个栈的栈底设在向量空间的两端让两个栈各自向中间延伸当一个栈里的元素较多超 过向量空间的一半时只要另一个栈的元素不多那么前者就可以占用后者的部分存储空间 只有当整个向量空间被两个栈占满(即两个栈顶相遇)时才会发生上溢因此两个栈共享一个长度为m的向量空间和两个栈分别 占用两个长度为 └ m/┘ 和┌m/┐的向量空间比较前者发生上溢的概率比后者要小得多 |
