​ 栈是数据结构中学习的第一个较为特殊的结构，首要特点就是先进后出，就好像一个细细长长的管子，你一个一个往里面放小球（这个小球刚好能放进去），你每次放只能放在顶部，每次拿也只能拿取顶部的。

栈的顺序存储

定义

1
2
3
4
5
#define MaxSize 10
typedef struct{		//定义栈中元素的最大个数
	ElemType data[MaxSize];		//静态数组存放栈中元素	
	int top;		//栈顶指针	
} SqStack;

初始化

1
2
3
4
//初始化栈
void InitStack(SqStack &S){
	S.top=-1;//初始化栈顶指针
}

也可以直接指向栈顶，不同的是判断栈已满的条件不同了

入栈操作

1
2
3
4
5
6
7
bool Push(SqStack &S,ElemType x){//新元素入栈
    if(S.top==MaxSize-1)//栈满，报错
    	return false;
    S.top = S.top+ 1;//指针先加1
    S.data[S.top]=x;//新元素入栈
    return true;
}

出栈操作

1
2
3
4
5
6
7
8
//出栈操作
bool Pop(SqStacK &S,ElemType &x){
    if(S.top==-1)//栈空，报错
		return false;
	x=S.data[S.topl; //栈顶元素先出栈
	S.top=S.top-1; //指针再减l
	return true;
}

读取栈顶元素

1
2
3
4
5
6
bool GetTop(SqStack S,ElemType &x){
	if(S.top==-1)//栈空，报错
		return false;
	x=S.data[S.topl;//x记录栈顶元素
	return true;
}

​ 此外还有一个特殊的栈——共享栈，即两个栈共享同一片空间，就是一个连续空间中，一个栈从头开始存储，一个从尾部开始存储。

栈的链式存储

​ 本质就是一个单链表，限制其只能在一端进行操作。限制进出栈的操作只能在头节点/指针进行，同样也有带头结点和不带头结点的两个实现版本。链栈。