顺序栈
栈的顺序存储结构简称为顺序栈 它是运算受限的顺序表
顺序栈的类型定义
#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(S x)
{
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/ ┐的向量空间比较 前者发生上溢的概率比后者要小得多
lishixinzhi/Article/program/sjjg/201311/23931