顺序栈（数组模拟）

编程入门行业动态更新时间:2024-10-25 22:27:38

顺序栈（<a href=https://www.elefans.com/category/jswz/34/1771288.html style= 数组模拟）"/>

顺序栈（数组模拟）

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

前置知识：

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=0S.base = (SElemType*)malloc(StackInitSize * sizeof(SElemType));//申请StackInitSize个SElemType类型的内存if (S.base == NULL)				//申请内存失败时，S.base==NULLreturn ;					//函数停止，不进行以下操作S.top = 0;S.stacksize = StackInitSize;	//初始化栈的top指针和大小
}

判断栈空：

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

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

求栈的长度：

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

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

入栈：

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

void Push(SqStack &S, SElemType e) { //e入栈Sif (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) {//得到栈顶元素赋给eif (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=0S.base = (SElemType*)malloc(StackInitSize * sizeof(SElemType));//申请StackInitSize个SElemType类型的内存if (S.base == NULL)				//申请内存失败时，S.base==NULLreturn ;					//函数停止，不进行以下操作S.top = 0;S.stacksize = StackInitSize;	//初始化栈的top指针和大小
}
bool StackEmpty(SqStack &S) { //判断栈空if (S.top == 0)return true;//1return false;//0
}
int StackLength(SqStack &S) { //求栈的长度return S.top;
}
void Push(SqStack &S, SElemType e) { //e入栈Sif (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) {//得到栈顶元素赋给eif (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";}
}