1. 顺序栈- 即栈的顺序实现。
2. 栈容量- 栈中可存放的最大元素个数。
3. 栈顶指针 top-指示当前栈顶元素在栈中的位置。
4. 栈空-栈中无元素时,表示栈空;
5. 栈满-数组空间已被占满时,称栈满;
6. 下溢-当栈空时,再要求作出栈运算,则称“下溢”;
7. 上溢-当栈满时,再要求作进栈运算,则称“上溢”。
const int maxsize=6;
typedef struct seqstack {
DataType data[maxsize];
int top;
}SeqStk;
// 定义一个顺序栈
SeqStk *s
s->top==0 代表顺序栈s为空;
s->top==maxsize-1 代表顺序栈s为满 ;
1. 初始化
int Initstack(SeqStk *stk){
stk->top=0;
return 1;
}
2. 判断栈空
int EmptyStack(SeqStk *stk){
if(stk->top == 0){
return 1;
} else{
return 0;
}
}
3. 进栈
int Push(SeqStk *stk, DataType x){
// 判是否上溢
if(stk->top==maxsize -1) {
error(“栈满”);
return 0;
} else {
// 修改栈顶指针,指向新栈顶
stk->top++;
// 元素x插入新栈顶中
stk->data[sq->top]=x;
return 1;
}
}
4. 出栈
int Pop(SeqStk *stk){
// 判是否下溢
if(stk->top==0) {
error(“栈空”);
return 0;
} else {
// 修改栈顶指针,指向新栈顶
stk->top--;
return 1;
}
}
5. 取栈顶元素
DataType GetTop(SeqStk *stk){
if(EmptyStack(stk)){
return NULLData;
}else{
return stk->data[stk->top];
}
}
在某些应用中,为了节省空间,让两个数据元素类型一致的栈共享一维数组空间data[max],成为双栈,两个栈的栈底分别设在数组两端,让两个栈彼此迎面“增长”,两个栈的栈顶变量分别为top1,top2,仅当两个栈顶位置在中间相遇时才会发生“上溢”,即top1+1=top2