定义
- 栈（stack）是限定仅在表尾进行插入和删除操作的线性表
- 我们把进行插入和删除操作的一端称作栈顶，另一端称作栈底
- 不含任何数据元素的栈称为空栈
- 栈具有后进先出的特性
如何理解
- 是具有限制条件的线性表，仍然满足线性表的基本性质即前驱后继关系
- 仅在表尾进行操作中的表尾是指栈顶而不是栈底
- 栈的插入操作叫做进栈也称入栈、压栈
- 栈的删除操作叫做出栈，也有的叫做弹栈
栈的结构定义与操作：
#define MAXSIZE 20;
typedef int SElementType //根据实际情况确定栈内元素的数据类型，此处以int类型为例子
typedef strcut {
SElementType data [MAXSIZE];
int top //栈顶指针用于指示栈顶位置，因为在数组中下标以0开始，所以我们常用-1表示空栈
}SqStack
//进栈操作即将数据压入栈内
int Push(SqStack * S,ElementType e){
//判断是否栈满
if(S->top == MAXSIZE - 1){
return 0;
}
S->top ++;
S->data[S->top] = e;
return 1;
}
//e用来存储栈弹出的数据
int Pop(SqStack *S, *e){
//判断是否空栈
if(S->top == -1){
return 0
}
*e = S->data[S->top];
S->top --;
return 1;
}
两栈共享空间
解决的问题:两个相同类型的栈，一个栈已经满了，但是另一个栈还有很多空闲的空间为利用。
适合的场景：当两个栈的空间需求相反
//共享栈的空间结构
typedef struct{
ElementType data[MAXSIZE];
int top1;//从数组首段开始
int top2;//从数组尾端开始
}SqDoubleStack
//插入元素时与普通栈的区别：需要考虑插入的栈是哪个栈
int Push(SqDoubleStack *S,ElementType e,int StackNumber){
//栈满
if(S->top1 + 1 == S->top2){
return 0;
}
if(StackNumber == 1){
S->top1 ++ ;
S->data[S->top1] = e;
}
if(StackNumber == 2){
S->top2--;
S->data[S->top2] = e;
}
return 1;
}
//出栈
int Pop(SqDoubleStack *S,ElementType *e,int StackNumber ){
if(StackNumber == 1){
//空栈判断
if(S->top1 == -1){
return 0;
}
*e = S-data[S->top1];
S->top1--;
}
if(StackNumber == 2){
if(S->top2 == MASIZE){
return 0;
}
*e = S->data[S->top2];
S->top2++;
}
}
