数组模拟)"/>
顺序栈(数组模拟)
栈是一种比较常用的数据结果,其特性是先进后出,常用于某些递归问题非递归求解,单调栈等,顺序栈实际上就是数组模拟栈。
前置知识:
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";}
}
运行结果:
最后提一下共享存储空间的顺序栈,其实质是两个栈和在一起,一个栈顶指针从0开始,一个栈顶指针从n开始(n为栈初始长度),大部分操作与单顺序栈没有太大区别,稍作了解即可。
更多推荐
顺序栈(数组模拟)
发布评论