C/C++教程
数据结构C/C++实现——栈之顺序栈(含共享顺序栈)
本文主要是介绍数据结构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++实现——栈之顺序栈(含共享顺序栈)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
