顺序栈（数组模拟）

栈是一种比较常用的数据结果，其特性是先进后出，常用于某些递归问题非递归求解，单调栈等，顺序栈实际上就是数组模拟栈。

前置知识：

        realloc函数

//realloc()函数适用于对地址内存的二次申请
//使用方法如下：
int *a;
a=(int*)realloc(a,5*sizeof(int));
//即对a的内存重新申请为5*sizeof(int)

使用结构体定义一个SqStack数据类型来表示顺序栈

#define StackInitSize 100 	//顺序栈的初始大小，当数据超出这个大小我们称其为爆栈
#define StackIncrement 10 	//顺序栈存储空间增量
#define SElemType int		//自定义栈内数据类型
typedef struct {
	SElemType *base;		//数组模拟顺序栈
	int top;				//栈顶指针，即数组末尾下标
	int stacksize;			//顺序栈的存储空间大小
} SqStack;					//定义顺序栈的数据类型

---

栈操作：

        栈操作基本分为六个，初始化栈，判断栈空，求栈的长度，入栈，出栈，取栈顶元素。

初始化栈：

        建立一个空栈，top指针为0，栈的容量stacksize为定义的初始StackInitSize。

void InitStack(SqStack &S) { //初始化栈
	//初始时，栈空，top=0
	S.base = (SElemType*)malloc(StackInitSize * sizeof(SElemType));
	//申请StackInitSize个SElemType类型的内存
	if (S.base == NULL)				//申请内存失败时，S.base==NULL
		return ;					//函数停止，不进行以下操作
	S.top = 0;
	S.stacksize = StackInitSize;	//初始化栈的top指针和大小
}

判断栈空：

        由于是数组模拟栈，我们用到的top下标指针实际上也象征这栈的长度，当长度为0时，栈内无元素，即栈空。

bool StackEmpty(SqStack &S) { //判断栈空
	if (S.top == 0)
		return true;//1
	return false;//0
}

求栈的长度：

        我们已经分析了top下标指针实际上也象征这栈的长度。

int StackLength(SqStack &S) { //求栈的长度
	return S.top;
}

入栈：

        将元素入栈，top下标指针++偏移一位。

void Push(SqStack &S, SElemType e) { //e入栈S
	if (S.top >= S.stacksize) {
		//当栈满时，为栈额外申请StackIncrement个SElemtype的内存
		S.base = (SElemType*)realloc(S.base, (S.stacksize + StackIncrement) * sizeof(SElemType));
		if (S.base == NULL)				//申请内存失败时
			return ;					//停止函数，不再进行下列操作
		S.stacksize += StackIncrement;	//栈的大小增加
	} else {                            //栈不满时，直接入栈
		S.base[S.top++] = e;
		/*
		相当于
		S.base[S.top]=e;将e存入数组
		S.top++;		栈top指针偏移
		*/
	}
}

出栈：

        栈顶元素一定是最后进栈的，由栈后进先出的性质，出栈元素为栈顶元素

void Pop(SqStack &S, SElemType &e) {
	//使用&可以直接改变e的值，这种方法叫做引用
	if (S.top == 0) //StackEmpty(S)
		return ;
	//栈非空时，指针top--，可看作对栈顶出栈
	e = S.base[--S.top];
	/*--i与i--的区别
	S.top--;
	e=S.base[S.top];
	*/
}

取栈顶元素：

void GetTop(SqStack &S, SElemType &e) {
	//得到栈顶元素赋给e
	if (S.top == 0)
		return;
	e = S.base[S.top - 1];
	//GetTop()与Pop()之间的差别在于是否有出栈操作
}

---

对顺序栈的使用：

#include<bits/stdc++.h>
using namespace std;
 
#define StackInitSize 100 	//顺序栈的初始大小，当数据超出这个大小我们称其为爆栈
#define StackIncrement 10 	//顺序栈存储空间增量
#define SElemType int		//自定义栈内数据类型
typedef struct {
	SElemType *base;		//数组模拟顺序栈
	int top;				//栈顶指针，即数组末尾下标
	int stacksize;			//顺序栈的存储空间大小
} SqStack;					//定义顺序栈的数据类型
 
void InitStack(SqStack &S) { //初始化栈
	//初始时，栈空，top=0
	S.base = (SElemType*)malloc(StackInitSize * sizeof(SElemType));
	//申请StackInitSize个SElemType类型的内存
	if (S.base == NULL)				//申请内存失败时，S.base==NULL
		return ;					//函数停止，不进行以下操作
	S.top = 0;
	S.stacksize = StackInitSize;	//初始化栈的top指针和大小
}
bool StackEmpty(SqStack &S) { //判断栈空
	if (S.top == 0)
		return true;//1
	return false;//0
}
int StackLength(SqStack &S) { //求栈的长度
	return S.top;
}
void Push(SqStack &S, SElemType e) { //e入栈S
	if (S.top >= S.stacksize) {
		//当栈满时，为栈额外申请StackIncrement个SElemtype的内存
		S.base = (SElemType*)realloc(S.base, (S.stacksize + StackIncrement) * sizeof(SElemType));
		if (S.base == NULL)				//申请内存失败时
			return ;					//停止函数，不再进行下列操作
		S.stacksize += StackIncrement;	//栈的大小增加
	} else { //栈不满时，直接入栈
		S.base[S.top++] = e;
		/*
		相当于
		S.base[S.top]=e;将e存入数组
		S.top++;		栈top指针偏移
		*/
	}
}
void Pop(SqStack &S, SElemType &e) {
	//使用&可以直接改变e的值，这种方法叫做引用
	if (S.top == 0) //StackEmpty(S)
		return ;
	//栈非空时，指针top--，可看作对栈顶出栈
	e = S.base[--S.top];
	/*--i与i--的区别
	S.top--;
	e=S.base[S.top];
	*/
}
void GetTop(SqStack &S, SElemType &e) {
	//得到栈顶元素赋给e
	if (S.top == 0)
		return;
	e = S.base[S.top - 1];
	//GetTop()与Pop()之间的差别在于是否有出栈操作
}
 
int main() {
	SqStack st;
	InitStack(st);
	if (StackEmpty(st)) {
		cout << "初始时栈空\n";
	}
	Push(st, 1); //1入栈
	Push(st, 2); //2入栈
	Push(st, 3); //3入栈
	cout << "此时栈的长度：" << StackLength(st) << "\n";
	SElemType tmp;
	GetTop(st, tmp); //获取栈顶元素
	cout << "栈顶元素为：" << tmp << "\n";
 
	//清栈操作
	while (!StackEmpty(st)) {	//只要栈不空
		Pop(st, tmp);		//就执行一次出栈操作
		cout << tmp << "出栈\n";
	}
}

运行结果：

---

最后提一下共享存储空间的顺序栈，其实质是两个栈和在一起，一个栈顶指针从0开始，一个栈顶指针从n开始（n为栈初始长度），大部分操作与单顺序栈没有太大区别，稍作了解即可。