文章目录
栈的定义栈的存储栈上的基本操作初始化判空操作进栈操作出栈操作读栈顶元素遍历栈销毁栈
完整代码及实例共享栈
栈的定义
栈（Stack）是只允许在一端进行插入或删除操作的线性表。
栈的示意图：
栈顶Top：线性表允许插入和删除的那一端。栈底Bottom：固定的，不允许进行插入和删除的另一端。
假设某个栈S={a1,a2, … ,an}，如上图所示，则a1为栈底元素，an为栈顶元素。由于只能在栈顶进行插入和删除操作，故进栈顺序为a1,a2, … ,an，出栈顺序为an, … ,a2,a1。故栈的操作特性是后进先出LIFO（Last In First Out），称为后进先出的线性表。
空栈：不含任何元素的空表。
栈的存储
栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。 栈的顺序存储类型描述：
#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{
int data[MaxSize]; //存放栈中的元素
int top; //栈顶指针
}SqStack;
采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作，关于链栈的实现与单链表类似，可以参考单链表的定义及其基本操作。
栈的链式存储类型描述：
typedef struct LinkNode{
int data; //数据域
struct LinkNode *next; //指针域
}*LiStack; //栈类型定义
栈上的基本操作
栈的基本操作包括：
初始化InitStack(&S);判空Empty(S);进栈Push(&S, x);出栈Pop(&S, &x);读栈顶元素GetTop(S);遍历栈PrintStack(&S);销毁栈DestroyStack(&S);
[注]以上操作均采用顺序栈来实现。
初始化
初始时设置S.top = -1。
//初始化
void InitStack(SqStack &S){
S.top = -1;
}
判空操作
栈空条件：S.top == -1; 栈满条件：S.top ==MaxSize-1。
//判栈空
bool Empty(SqStack S){
if(S.top == -1){
return true;
}else{
return false;
}
}
进栈操作
由于初始设置S.top=-1，故栈顶指针先加一，再入栈。
//入栈
void Push(SqStack &S, int x){
if(S.top == MaxSize-1){
cout<<"栈满"< return; } S.data[++S.top] = x; //指针先加一，再入栈 } 出栈操作 先出栈，指针再减一。 //出栈 void Pop(SqStack &S, int &x){ if(S.top == -1){ cout<<"栈空"< return; } x = S.data[S.top--]; //先出栈，指针再减一 } 读栈顶元素 //读栈顶元素 int GetTop(SqStack S){ if(S.top == -1){ cout<<"栈空"< return -1; }else{ return S.data[S.top]; } } 遍历栈 当栈不为空时，循环输出当前栈顶元素。 //遍历栈 void PrintStack(SqStack S){ while(S.top != -1){ cout< } cout< } 销毁栈 栈的销毁令S.top = -1即可。 //销毁栈 void DestroyStack(SqStack &S){ S.top = -1; } 完整代码及实例 完整代码及实例： #include using namespace std; #define MaxSize 100 //定义栈中元素的最大个数 typedef struct SqStack{ int data[MaxSize]; //存放栈中的元素 int top; //栈顶指针 }SqStack; //初始化 void InitStack(SqStack &S){ S.top = -1; } //判栈空 bool Empty(SqStack S){ if(S.top == -1){ return true; }else{ return false; } } //入栈 void Push(SqStack &S, int x){ if(S.top == MaxSize-1){ cout<<"栈满"< return; } S.data[++S.top] = x; } //出栈 void Pop(SqStack &S, int &x){ if(S.top == -1){ cout<<"栈空"< return; } x = S.data[S.top--]; } //读栈顶元素 int GetTop(SqStack S){ if(S.top == -1){ cout<<"栈空"< return -1; }else{ return S.data[S.top]; } } //遍历栈 void PrintStack(SqStack S){ while(S.top != -1){ cout< } cout< } //销毁栈 void DestroyStack(SqStack &S){ S.top = -1; } int main(){ SqStack S; InitStack(S); Push(S,1);//入栈 Push(S,2); Push(S,3); Push(S,4); cout<<"栈顶元素为："< cout<<"出栈顺序为："; PrintStack(S); int x; Pop(S,x); cout< cout<<"栈中剩余元素："; PrintStack(S); Pop(S,x); cout< cout<<"栈中剩余元素："; PrintStack(S); if(!Empty(S)){ cout<<"当前栈不为空"< }else{ cout<<"当前栈为空"< } return 0; } 运行结果： 共享栈 利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。如下图所示： 两个栈的栈顶指针都指向栈顶元素。 判空：top0 = -1 时0号栈为空， top1 = MaxSize-1 时1号栈为空。 栈满：当且仅当两个栈顶指针相邻，即top1 - top0 = 1 时栈满。 进栈：0号栈进栈时，top0先加一再赋值， 1号栈进栈时top1先减一再赋值。 出栈：0号栈出栈时，先出栈top0再减一， 1号栈出栈时先出栈top1再加一。