文章目录
- 1.顺序栈
- 1.1初始化
- 1.2判空
- 1.3进栈
- 1.4出栈
- 1.5读取栈顶
- 1.6销毁栈
- ❗1.7顺序栈c++实例
- 2.共享栈
- 2.1初始化
- 2.2判满
1.顺序栈
用顺序存储实现的栈
顺序栈的缺点：栈的大小不可变。
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack; //Sq即sequence：顺序的意思
有的顺序栈结构还有栈的大小stackSize：
typedef struct{
ElemType* base; //栈底指针:base指针不动、top往上移
ElemType* top; //栈顶指针
int stackSize; //当前已分配的存储空间大小,即顺序栈的大小
} SqStack; //顺序栈的结构体定义
顺序存储：给各个数据元素分配连续的存储空间，大小为 MaxSize * sizeof(ElemType)。
1.1初始化
InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct {
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
} SqStack;
//初始化
void InitStack(SqStack &S) {
S.top = -1; //初始化栈顶指针
}
void main() {
SqStack S; //声明一个顺序栈(分配空间)
InitStack(S);
//后续操作...
}
初始化有两种方式：
栈顶指针top指向栈顶元素，一般存储的是数组的下标。（一般初始化时top=-1）
-
初始化时
top=-1，那么元素从0开始。top当前指向的位置就是栈顶。如果有abcde，5个元素，那么满栈top=4。
- 入栈：S.data[++S.top]=x;
- 出栈：x=S.data[S.top-];
- 获得栈顶元素：x=S.data[S.top];
-
初始化时
top=0。top当前指向的位置是栈顶上面的一个没有元素的空位置。- 入栈：S.data[S.top++]=x;
- 出栈：x=S.data[–S.top];
- 获得栈顶元素：x=S.data[S.top-1];
1.2判空
StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。
时间复杂度：O(1)
//判断栈空
bool StackEmpty(SqStack S) {
if(S.top == -1) //栈空
return true;
else //不空
return false;
}
1.3进栈
Push(&S,x)：插入，进栈。若栈S未满，则将x加入使之成为新栈顶。
时间复杂度：O(1)
//新元素入栈
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，然后新元素入栈的两段代码可以等价于：
S.data[++S.top] = x;
注意是++S.top先加再用，而不是S.top++先用再加。
1.4出栈
Pop(&S,&x)：删除，出栈。若栈S非空，则弹出栈顶元素，并用x返回。
时间复杂度：O(1)
//出栈操作
bool Pop(SqStack &S, ElemType &x) {
if(S.top == -1) //栈空，报错
return false;
x = S.data[S.top]; //栈顶元素先出栈
S.top = S.top-1; //指针再减1
return true;
}
注意：这里top-1，数据其实还残留在内存中，只是逻辑上被删除了。
上述代码中也可以等价于：
x = S.data[S.top--];
注意是S.top--先用再减，而不是--S.top先减再用。
1.5读取栈顶
GetTop(S,&x)：读取栈顶元素。若栈S非空，则用x返回线顶元素。
时间复杂度：O(1)
//读栈顶元素
bool GetTop(SqStack S, ElemType &x) {
if(S.top == -1) //栈空，报错
return false;
x = S.data[S.top]; //×记录栈顶元素
return true;
}
读取栈顶元素和出栈操作十分相似，唯一不同是不需要出栈之后top指针-1。
1.6销毁栈
顺序栈是在声明栈时直接分配内存，并没有使用malloc函数，所以不需要手动free，函数运行结束后系统自动回收空间。
但是如果使用了动态分配那么就需要手动释放空间：
//销毁栈、释放栈的内存
void DestroyStack(SqStack& stack){
if(stack.base) { //若栈底指针分配有地址,则释放
delete stack.base; //释放栈底指针的地址
stack.top = -1; //令栈顶位置为0
stack.base = NULL; //将栈底指针指向空
cout << "栈已释放内存！" << endl;
}
}
❗1.7顺序栈c++实例
C++是一门面向对象的高级语言，在我们编写代码中，常常离不开对对象的创建和清理对象资源。而兼容过来的malloc和free并不能很好的满足我们的需求，从而C++将malloc和free封装起来并起了新的名字new和delete，这两个关键字的作用不仅比malloc和free的功能强大，用起来也非常的方便。
new和delete都是运算符，不是库函数，不需要单独添加头文件。
格式：
new
- 类型指针 指针变量名 = new 类型
- 类型指针 指针变量名 = new 类型(初始值)
- 类型指针 指针变量名 = new 类型[元素个数]
delete
- delete 指针变量名
- delete[] 指针变量名
#include<iostream>
#include<Windows.h>
using namespace std;
#define MaxSize 10 //栈最大可以存放的元素个数
typedef int ElemType; //顺序栈存储的数据类型、用int代替ElemType
//创建顺序栈
typedef struct
{
ElemType* base; //栈底指针
int top; //栈顶的位置 如 0、1、2、3、4....MaxSize
} SqStack; //顺序栈的结构体定义
bool InitStack(SqStack& stack); //初始化栈
bool StackEmpty(SqStack stack);//判断是否为空
bool StackFull(SqStack stack); //判断是否已满
int GetStackSize(SqStack& stack);//获取顺序栈中元素个数
bool Push(SqStack& stack, ElemType value);//入栈
bool Pop(SqStack& stack, ElemType& value);//出栈
bool GetTop(SqStack& stack, ElemType& value);//获取栈顶的元素
void DestroyStack(SqStack& stack);//销毁栈、释放栈的内存
//--------------------------------------------------
void CreatStack(SqStack stack){
int number, value = 0;
cout << "请输入需要插入的元素个数:";
cin >> number;
while (number > 0){
cin >> value;
Push(stack, value); //放入栈
number--;
value++;
}
}
int main()
{
SqStack stack; //创建顺序栈
InitStack(stack); //初始化顺序栈
//例如插入
int value = 5; //插入5个元素
while (value > 0){
Push(stack, value); //放入栈
value--;
}
//获取栈顶的元素
GetTop(stack, value);
cout << "当前栈顶的元素是：" << value << endl;
//获取栈的元素个数
cout << "当前栈的元素个数是：" << GetStackSize(stack) << endl;
//出栈
cout << "出栈顺序：" << endl;
while (!StackEmpty(stack)){
Pop(stack, value);
cout << value << " ";
}
cout << endl;
//释放栈的内存
DestroyStack(stack);
system("pause");
return 0;
}
//-----------------------------------------------------------------------
//初始化顺序栈
bool InitStack(SqStack& stack){
//注意:这里使用new进行空间分配,所以在后面摧毁栈的时候需要delete释放空间
//动态分配一个ElemType类型MaxSize长度的空间，将地址给顺序栈Stack的栈底指针
stack.base = new ElemType[MaxSize];
//判断顺序栈的栈底指针(stack.base)是否为空，若无地址，则分配失败
if(!stack.base){
return false;
}
stack.top = -1; //初始化栈顶指针的位置为-1
return true;
}
//判断栈空
bool StackEmpty(SqStack stack){
if (stack.top == -1)
return true;
else
return false;
}
//判断栈满
bool StackFull(SqStack stack){
if (stack.top == MaxSize-1) //top的位置值等于MaxSize-1时栈满,因为是从0开始的
return true;
else
return false;
}
//顺序栈中元素个数
int GetStackSize(SqStack& stack){
return stack.top+1; //栈顶位置即top的数值，就是栈中元素的个数
}
/**
* @brief 顺序栈入栈:
* 开辟一个新的空间,栈顶+1,然后将数据存入stack.base[stack.top]所在的位置.
*
* @param stack
* @param value
* @return true
* @return false
*/
bool Push(SqStack& stack, ElemType value){
if (StackFull(stack)){
cout<<"栈满"<<endl;
return false;
}
//若栈未满，执行入栈操作
stack.top++; //栈顶自增1
stack.base[stack.top] = value; //以栈顶位置作为下标存储数据
return true;
}
/**
* @brief 顺序栈出栈:
* 读取栈顶stack.base[stack.top]的元素,然后使栈顶-1.
*
* @param stack
* @param value
* @return true
* @return false
*/
bool Pop(SqStack& stack, ElemType &value){
if (StackEmpty(stack)){
cout<<"栈为空"<<endl;
return false;
}
value = stack.base[stack.top]; //以栈顶位置作为下标的值赋值给value返回
stack.top--; //栈顶自减1
return true;
}
//读取栈顶元素
bool GetTop(SqStack& stack, ElemType &value){
if (StackEmpty(stack)){
cout<<"栈为空"<<endl;
return false;
}
value = stack.base[stack.top];
return true;
}
//销毁栈、释放栈的内存
void DestroyStack(SqStack& stack){
if(stack.base) { //若栈底指针分配有地址,则释放
delete stack.base; //释放栈底指针的地址
stack.top = -1; //令栈顶位置为0
stack.base = NULL; //将栈底指针指向空
cout<<"栈已释放内存！"<<endl;
}
}
当前栈顶的元素是：1
当前栈的元素个数是：5
出栈顺序：
1 2 3 4 5
栈已释放内存！
2.共享栈
因为顺序栈的缺点是栈的大小不可变，所以引出共享栈，两个栈共享一片空间。这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间。两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。
2.1初始化
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct {
ElemType data [MaxSize];//静态数组存放栈中元素
int top0; //0号栈线顶指针
int top1; //1号栈线顶指针
} ShStack;
//初始化栈
void InitStack(ShStack &S) {
S.top0 = -1; //初始化栈顶指针
S.top1 = MaxSize;
}
2.2判满
top0从-1开始，top1从MAX开始。那么放入元素后，top0逐渐增大，top1减小。当他们下一个指针的位置在一起时，说明这个栈已经放满元素。
top0+1 == top1
