数据结构C/C++实现——栈之顺序栈(含共享顺序栈)
2021/12/29 22:08:53
本文主要是介绍数据结构C/C++实现——栈之顺序栈(含共享顺序栈)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
top指向栈顶元素本身:
/*
栈：只允许在一段进行插入或删除操作的线性表
顺序栈：用顺序存储方式实现的栈
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define MaxSize 5 //定义顺序栈最大长度
#define ElemType int
typedef struct {
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack; //顺序栈类型定义 sq:sequence顺序
//初始化顺序表
void InitStack(SqStack& S) {
S.top = -1;
}
/*
此种设定下：
栈顶指针：S.top(指向栈顶元素)
初始时设置：S.top = -1
栈顶元素：S.data[S.top]
栈空：S.top == -1
栈满：S.top == MaxSize - 1
栈长：S.top + 1
进栈操作：栈不满时，栈顶指针先+1，再送值到栈顶元素
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针-1
*/
//判空
bool StackEmpty(SqStack S) {
if (S.top == -1) return true;
else return false;
}
//要注意的是，需要改动栈本身的时候一定要加&
//入栈
bool Push(SqStack& S, ElemType x) {
if (S.top == MaxSize - 1) return false; //栈满
S.top = S.top + 1;
S.data[S.top] = x;
return true;
}
bool Push2(SqStack& S, ElemType x) {
if (S.top == MaxSize - 1) return false; //栈满
S.data[++S.top] = x;
return true;
}
//出栈
bool Pop(SqStack& S, ElemType& x) {
if (S.top == -1) return false; //栈空
x = S.data[S.top];
S.top = S.top - 1;
return true;
}
bool Pop2(SqStack& S, ElemType& x) {
if (S.top == -1) return false; //栈空
x = S.data[S.top--];
return true;
}
//读取栈顶元素
bool GetTop(SqStack S, ElemType& x) {
if (S.top == -1) return false;
x = S.data[S.top];
return true;
}
//以上所有基本操作时间复杂度为O(1)
//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack &S) {
S.top = -1;
}
int main() {
SqStack S;
InitStack(S);
int x;
bool sign;
cout << "请连续输入要入栈的值 空格分界 999结束：\n";
scanf_s("%d", &x);
while (x != 999) {
sign = Push(S, x);
if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息
cout << "栈最大容量为：" << MaxSize << "，当前栈已满，超出部分未入栈\n";
break;
}
scanf_s("%d", &x);
}
int top;
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop(S, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop2(S, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
return 0;
}
top指向栈顶元素下一位置:
/*
栈：只允许在一段进行插入或删除操作的线性表
顺序栈：用顺序存储方式实现的栈
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define MaxSize 5 //定义顺序栈最大长度
#define ElemType int
typedef struct {
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶指针
}SqStack; //顺序栈类型定义 sq:sequence顺序
//初始化顺序表
void InitStack(SqStack& S) {
S.top = 0;
}
/*
此种设定下：
栈顶元素的位置：S.top - 1
初始时设置：S.top = 0
栈顶元素：S.data[S.top - 1]
栈空：S.top == 0
栈满：S.top == MaxSize
栈长：S.top
进栈操作：栈不满时，先送值到栈顶元素，栈顶指针再+1
出栈操作：栈非空时，先将栈顶指针-1，再取栈顶元素值
*/
//判空
bool StackEmpty(SqStack S) {
if (S.top == 0) return true;
else return false;
}
//要注意的是，需要改动栈本身的时候一定要加&
//入栈
bool Push(SqStack& S, ElemType x) {
if (S.top == MaxSize) return false; //栈满
S.data[S.top] = x;
S.top = S.top + 1;
return true;
}
bool Push2(SqStack& S, ElemType x) {
if (S.top == MaxSize) return false; //栈满
S.data[S.top++] = x;
return true;
}
//出栈
bool Pop(SqStack& S, ElemType& x) {
if (S.top == 0) return false; //栈空
S.top = S.top - 1;
x = S.data[S.top];
return true;
}
bool Pop2(SqStack& S, ElemType& x) {
if (S.top == 0) return false; //栈空
x = S.data[--S.top];
return true;
}
//读取栈顶元素
bool GetTop(SqStack S, ElemType& x) {
if (S.top == 0) return false;
x = S.data[S.top - 1];
return true;
}
//以上所有基本操作时间复杂度为O(1)
//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack& S) {
S.top = 0;
}
int main() {
SqStack S;
InitStack(S);
int x;
bool sign;
cout << "请连续输入要入栈的值 空格分界 999结束：\n";
scanf_s("%d", &x);
while (x != 999) {
sign = Push(S, x);
if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息
cout << "栈最大容量为：" << MaxSize << "，当前栈已满，超出部分未入栈\n";
break;
}
scanf_s("%d", &x);
}
int top;
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop(S, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop2(S, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
return 0;
}
共享顺序栈:
/*
栈：只允许在一段进行插入或删除操作的线性表
共享顺序栈：用顺序存储方式实现的栈，且两个栈共享同一个存储空间
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define MaxSize 10 //定义顺序栈最大长度
#define ElemType int
typedef struct {
ElemType data[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}SqStack; //顺序栈类型定义 sq:sequence顺序
//初始化顺序表
void InitStack(SqStack& S) {
S.top0 = -1;
S.top1 = MaxSize;
}
/*
此种设定下：
栈顶指针：S.top0、S.top1 (分别指向各自栈顶元素)
初始时设置：S.top0 = -1 S.top1 = MaxSize
栈顶元素：S.data[S.top0]、S.data[S.top1]
栈空：S.top0 == -1/S.top1 == MaxSize
栈满：S.top0 + 1 == S.top1
进栈操作：栈不满时，栈顶指针先+1(对0号栈) -1(对1号栈)，再送值到栈顶元素
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针-1(对0号栈) +1(对1号栈)
*/
//判空
bool StackEmpty(SqStack S,int i) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (i == 0) {
if (S.top0 == -1) return true;
else return false;
}
else if (i == 1) {
if (S.top1 == MaxSize) return true;
else return false;
}
}
//要注意的是，需要改动栈本身的时候一定要加&
//入栈
bool Push(SqStack& S,int i, ElemType x) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (S.top0 + 1 == S.top1) return false; //栈满
if (i == 0) {
S.top0 = S.top0 + 1;
S.data[S.top0] = x;
return true;
}
else if (i == 1) {
S.top1 = S.top1 - 1;
S.data[S.top1] = x;
return true;
}
}
bool Push2(SqStack& S,int i, ElemType x) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (S.top0 + 1 == S.top1) return false; //栈满
if(i == 0)
S.data[++S.top0] = x;
else if (i == 1)
S.data[--S.top0] = x;
return true;
}
//出栈
bool Pop(SqStack& S,int i, ElemType& x) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (i == 0) {
if (S.top0 == -1) return false; //栈空
x = S.data[S.top0];
S.top0 = S.top0 - 1;
return true;
}
else if (i == 1) {
if (S.top1 == MaxSize) return false; //栈空
x = S.data[S.top1];
S.top1 = S.top1 + 1;
return true;
}
}
bool Pop2(SqStack& S,int i, ElemType& x) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (i == 0) {
if (S.top0 == -1) return false; //栈空
x = S.data[S.top0--];
return true;
}
else if (i == 1) {
if (S.top1 == MaxSize) return false; //栈空
x = S.data[S.top1++];
return true;
}
}
//读取栈顶元素
bool GetTop(SqStack S,int i, ElemType& x) {
if (i != 0 && i != 1) {
cout << "栈号指定错误 程序退出\n";
exit(0);
}
if (i == 0) {
if (S.top0 == -1) return false; //栈空
x = S.data[S.top0];
return true;
}
else if (i == 1) {
if (S.top1 == MaxSize) return false; //栈空
x = S.data[S.top1];
return true;
}
}
//销毁(因为采用的是变量声明的方式分配得内存空间 未使用malloc函数 存储空间的回收由系统自动完成 故只需要完成清空操作即可)
void DestroyStack(SqStack& S) {
S.top0 = -1;
S.top1 = MaxSize;
}
int main() {
SqStack S;
InitStack(S);
int x;
bool sign;
cout << "请连续输入要入栈0的值 空格分界 999结束：\n";
scanf_s("%d", &x);
while (x != 999) { //实际测试发现，如果此处数值数就已经超过MaxSize break，则后续包含999在内的屏幕数值并未被读取，但会被下面的scanf_s继续读取，其实算个小bug
sign = Push(S,0, x);
if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息
cout << "栈最大容量为：" << MaxSize << "，当前栈已满，超出部分未入栈\n";
break;
}
scanf_s("%d", &x);
}
cout << "请连续输入要入栈1的值 空格分界 999结束：\n";
scanf_s("%d", &x);
while (x != 999) {
sign = Push(S, 1, x);
if (sign == false) {//由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息
cout << "栈最大容量为：" << MaxSize << "，当前栈已满，超出部分未入栈\n";
break;
}
scanf_s("%d", &x);
}
int top;
cout << "------下面操作栈0------\n";
sign = GetTop(S,0, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop(S,0, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S,0, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop2(S,0, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S,0, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
cout << "------下面操作栈1------\n";
sign = GetTop(S, 1, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop(S, 1, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, 1, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
sign = Pop2(S, 1, top);
if (sign == true)
cout << "出栈元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，出栈失败\n";
sign = GetTop(S, 1, top);
if (sign == true)
cout << "当前栈顶元素为：" << top << "\n";
else if (sign == false)
cout << "栈空，读取栈顶元素失败\n";
return 0;
}
这篇关于数据结构C/C++实现——栈之顺序栈(含共享顺序栈)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23增量更新怎么做？-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些？-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗？-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处？-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享
