1、栈的定义
栈就是只能在一端插入和删除数据的链表，这个端就叫做栈顶（top），最后一个添加的数据第一个被删除。因此，这也叫后进先出（LAST IN FIRST OUT）链表或是先进后出链表（FIRST IN LAST OUT）。
栈储存的图像表示：
2、栈的基本操作
对于栈有两种操作：
- 进栈指令（PUSH）：在栈中现有元素顶部添加一个元素，新加入的元素变为最顶端的元素。
- 出栈指令（POP）：取出栈顶元素，删除栈中的这个元素。
3、栈的基础经典算法
1．进栈（PUSH）算法
①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②置TOP=TOP+1（栈指针加1，指向进栈地址）；
③S(TOP)=X，结束（X为新进栈的元素）；
2．退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S(TOP)，（退栈后的元素赋给X）：
③TOP=TOP-1，结束（栈指针减1，指向栈顶）。
顺序栈的储存实现
#include <iostream>
#define MAXSIZE 100 //定义最大空间
#define ElemType int //定义数据类型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1
using namespace std;
typedef struct SNode *Stack;
struct SNode{
ElemType Data[MAXSIZE]; //定义栈的空间
int top; //指示栈顶的位置
};顺序栈的入栈实现
void Push(Stack Ptrs, ElemType item){
if(Ptrs->top == MAXSIZE-1) //栈满
cout << "Data overflow";
else{
Ptrs->Data[++(Ptrs->top)] = item; //先使top上移一位，再赋值
//也可以写成
//Ptrs->top++;
//Ptrs->Data[Ptrs->top] = item;
}
}顺序栈的出栈实现
ElemType Pop(Stack Ptrs){
if(Ptrs->top == -1){ //栈空
cout << "No data";
return ERROR;
}
else{
return (Ptrs->Data[Ptrs->top--]); //先抛出top的值，再使top-1
}
}4、共享栈——一个数组存放两个栈
这是一种合理使用空间的方法，使数组空间不被浪费太多
共享栈的定义：
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
其图示为：
（图片来自网络，侵删）
共享栈的储存实现
#include <iostream>
#define MAXSIZE 100 //定义最大空间
#define ElemType int //定义数据类型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1
using namespace std;
typedef struct DoubleStack DS
struct DoubleStack{
ElemType Data[MAXSIZE];
int top1; //定义第一个栈的头位置
int top2; //定义第二个栈的头位置
};
DS->top1 = -1;
DS->top2 = MAXSIZE; 共享栈的入栈实现
void Push(DS Ptrs, ElemType item, int flag){
//flag用于区分栈1和栈2
if(Ptrs->top1 - Ptrs->top2 == 1) //栈满
cout << "Data overflow";
if(flag == 1) //向栈1输入
Ptrs->Data[++(Ptrs->top1)] = item;
else if(flag == 2) //向栈2输入
Ptrs->Data[--(Ptrs->top2)] = item;
}
共享栈的出栈实现
ElemType Pop(DS Ptrs, int flag){
if(flag == 1){ //判断为栈1
if(Ptrs->top1 == -1){ //栈空
cout << "No data";
return nullptr;
}
else
return Ptrs->Data[(Ptrs->top1)--];
}
else if(flag == 2){ //判断为栈2
if(Ptrs->top2 == MAXSIZE){ //栈空
cout << "No data";
return nullptr;
}
else
return Ptrs->Data[(Ptrs->top1)++];
}
}5、链式栈
链式栈不需要预先分配容量，也无需增加容量，但是需要链表的首位作为top（栈的顶端元素）
其图示为：
（图片来自网络，侵删）
链式栈的储存实现
#include <iostream>
#define MAXSIZE 100 //定义最大空间
#define ElemType int //定义数据类型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1
using namespace std;
typedef struct LinkStack *LS;
struct LinkStack{
ElemType Data;
LinkStack *Next;
};创建一个空的链式栈
LS CreateStack(){
LS s;
s = new(LinkStack); //申请空间
s->Next = nullptr;
return s;
}链式栈的入栈实现
void Push(ElemType X, LS s){
LS ssr = s;
ssr = new(LinkStack);
ssr->Data = X; //插入值X
ssr->Next = s->Next; //插入
s->Next = ssr;
}链式栈的出栈实现
ElemType Pop(LS s){
LS FirstCell;
ElemType Top;
if(s->Next == nullptr) //判断是否为空栈
cout << "No data";
else{
FirstCell = s->Next;
s->Next = FirstCell->Next;
Top = FirstCell->Data;;
delete FirstCell; //释放空间，防止内存泄漏
return Top;
}
}6、栈的简单应用
中缀表达式
基本策略：
将中缀表达式转化成后缀表达式，然后求值
将中缀表达式转化成后缀表达式的方法：
