栈的顺序表和链表实现，以及一些涉及到栈思想的题目

2024-09-04 05:38
文章标签 链表 题目 顺序 涉及 思想 实现

本文主要是介绍栈的顺序表和链表实现，以及一些涉及到栈思想的题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、std里面栈的基本操作

#include <stdio.h>
#include <stack>
//使用命名空间std 
using namespace std;
stack<char> s; 
int main()
{//判断栈是否为空if(s.empty()){printf("空\n");}else{printf("非空\n");}char asd='a';//入栈s.push(asd);s.push('b');s.push('c');s.push('d');s.push('e');//获取栈顶元素printf("%c\n",s.top());//出栈s.pop();printf("%c\n",s.top());if(s.empty()){printf("空\n");}else{printf("非空\n");}//获取栈内元素个数printf("%d\n",s.size());return 0;
}

二、用顺序表实现栈的基本操作

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef char ElemType;
typedef struct{ElemType data[100];int top;
}SqStack;
//初始化栈
void InitStack(SqStack *&s)
{s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;
} 
//判断栈是否为空
bool StackEmpty(SqStack *s)
{return s->top==-1;	
} 
//将元素e入栈 
bool Push(SqStack *&s, ElemType e)
{if(s->top==MaxSize-1){return false;}s->top++; s->data[s->top]=e;return true;
}
//将栈顶元素赋值给变量e,然后出栈 
bool Pop(SqStack *&s, ElemType &e)
{//如果栈为空，无法出栈 if(s->top==-1){return false; } e=s->data[s->top]; s->top--;return true;
} 
//释放栈
void DestroyStack(SqStack *&s)
{free(s);
} 
int main()
{//新建一个栈，命名为asd SqStack *asd;ElemType e;//初始化栈 InitStack(asd);//判断栈是否为空 if(StackEmpty(asd)){printf("栈为空\n");}else{printf("栈不为空\n");}//依次入栈'a'、'b'、'c'、'd'、'e' Push(asd, 'a');Push(asd, 'b');Push(asd, 'c');Push(asd, 'd');Push(asd, 'e');//判断栈是否为空 if(StackEmpty(asd)){printf("栈为空\n");}else{printf("栈不为空\n");}//输出出栈序列 Pop(asd, e);printf("%c ", e);Pop(asd, e);printf("%c ", e);Pop(asd, e);printf("%c ", e);Pop(asd, e);printf("%c ", e);Pop(asd, e);printf("%c\n", e);//判断栈是否为空 if(StackEmpty(asd)){printf("栈为空\n");}else{printf("栈不为空\n");}//释放栈 DestroyStack(asd);return 0;
}

三、用链表实现栈的基本操作

#include <stdio.h>
#include <stdlib.h>
//默认头结点后面第一个位置为栈顶 
typedef char ElemType;
typedef struct linknode
{ElemType data;	//数据域 struct linknode *next;	//指针域 
}LinkStNode;	//链表实现的栈结点类型
//初始化栈,由于会改变栈s,所以需要引用& 
void InitStack(LinkStNode *&s)
{//开辟一片空间 s=(LinkStNode *)malloc(sizeof(LinkStNode));s->next=NULL;	//栈顶为空 
} 
//判断栈是否为空,由于不改变栈s,所以不需要加引用&  
bool StackEmpty(LinkStNode *s) 
{if(s->next==NULL){return true;}else{return false;}//return (s->next==NULL);
}
//将元素e入栈,要在栈顶入栈,栈顶为头结点后的第一个节点,所以用头插法 
void Push(LinkStNode *&s, ElemType e)
{//新建一个节点 LinkStNode *p; //为该节点分配空间p=(LinkStNode *)malloc(sizeof(LinkStNode));//为data域赋值 p->data=e;//将p和后面的节点(旧的栈顶节点)连一条箭头 p->next=s->next; //将头结点和节点p(新的栈顶节点)连一条箭头 s->next=p;
} 
//把栈顶元素赋值给变量e,并出栈
//由于调用该函数想要改变e的值,所以e前面需要加引用  
//栈顶为头结点s后的第一个数据结点 
bool Pop(LinkStNode *&s, ElemType &e)
{//首先需要判断栈是否为空if(s->next==NULL){return false;}//p指针用来保存旧栈顶,否则待会free时就找不到旧栈顶了 LinkStNode *p;p=s->next;e=p->data;//将头结点连到栈顶后面那个结点 s->next=p->next; //删除首节点 free(p);	//释放被删除结点的存储空间 return true; 
} 
//销毁栈,依次释放每一个结点的空间 
void DestroyStack(LinkStNode *&s)
{//定义栈结点变量,不需要申请空间 LinkStNode *p, *q;p=s;	//最开始给p赋值为头结点 q=s->next;	//给q赋值为第一个数据结点 while(q!=NULL){	//只要q不为空,则p就没用了 free(p);	//释放p的内存空间 p=q;		//p往后挪一位,挪到q的位置 q=q->next;	//q也往后挪一位 } //最后跳出while循环的时候,q已经为空了,只剩下q一个非空结点 free(p);		
} 
int main()
{ElemType e;//定义一个栈asd LinkStNode *asd;//初始化栈asd InitStack(asd); //判断栈是否为空if(StackEmpty(asd)==true){printf("栈为空\n");}else{printf("栈非空\n");}//依次入栈元素'a'、'b'、'c'、'd'、'e'Push(asd, 'a');Push(asd, 'b');Push(asd, 'c');Push(asd, 'd');Push(asd, 'e');//判断栈是否为空if(StackEmpty(asd)==true){printf("栈为空\n");}else{printf("栈非空\n");}//输出出栈序列while(!StackEmpty(asd)){Pop(asd, e);printf("%c ", e);}printf("\n");//判断栈是否为空if(StackEmpty(asd)==true){printf("栈为空\n");}else{printf("栈非空\n");}//释放栈 DestroyStack(asd);return 0;
}

四、涉及到栈思想的题目

P1739 表达式括号匹配

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
using namespace std;
char c[1000]; 
stack<char> s;
int cnt;
int main()
{//输出字符串 scanf("%s", &c);for(int i=0; i<strlen(c)-1; i++){//如果它既不是左括号,又不是右括号,跳过if(c[i]!='(' && c[i]!=')'){continue;} //如果是左括号(,直接入栈if(c[i]=='('){s.push('(');}else if(c[i]==')'){//如果是右括号)if(s.empty()){//如果栈为空,直接输出NO,结束程序printf("NO");return 0; }	//注意需要先判断栈是否为空，在不空的前提下才能用top函数 else if(s.top()=='('){ //如果栈顶是左括号(，直接出栈s.pop();}else if(s.top()==')'){	//如果栈顶是右括号)，直接入栈 s.push(')');}} cnt++;}//如果栈为空,输出YESif(s.size()==0 && cnt!=0){printf("YES");}else{	//否则,输出NO printf("NO");}return 0;
}

P1981 [NOIP2013 普及组] 表达式求值

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;stack<int> num;
string s;
int length;
int a[4];
int cur, before, ans;
int main()
{cin >> s;length=s.length();for(int i=0; i<length; ){//遇到数字 if(s[i]!='+' && s[i]!='*'){cur=0;while(s[i]>='0' && s[i]<='9'){cur=cur*10+s[i]-'0';if(cur>9999){cur%=10000;}++i;}num.push(cur);} if(s[i]=='+'){cur=0;//计算加号后面的那个数++i;while(s[i]>='0' && s[i]<='9'){cur=cur*10+s[i]-'0';if(cur>9999){cur%=10000;}++i;}num.push(cur);}if(s[i]=='*'){cur=0;before=num.top();//取出乘号前面的那个数 num.pop();//计算乘号后面的那个数++i;while(s[i]>='0' && s[i]<='9'){cur=cur*10+s[i]-'0';if(cur>9999){cur%=10000;}++i;}before*=cur;if(before>9999){before%=10000;}num.push(before);}}while(!num.empty()){ans+=num.top()%10000;num.pop();ans%=100000;}if(ans<=9999){cout << ans;}else{for(int i=0; i<4; ++i){a[i]=ans%10;ans/=10;}ans=a[0]+a[1]*10+a[2]*100+a[3]*1000;cout << ans;}return 0;
}

P1449 后缀表达式

#include <iostream>
#include <string.h>
#include <stack>
using namespace std;char s[1005];
int length, a, cur, before;
stack<char> opt;
stack<int> num;
int main()
{cin >> s;length=strlen(s);for(int i=0; i<length-1; ++i){if(s[i]>='0' && s[i] <='9'){while(s[i]!='.'){a=a*10+s[i]-'0';++i;}	num.push(a);a=0;}if(s[i]=='+'){cur=num.top();num.pop();before=num.top();num.pop();before+=cur;num.push(before);}if(s[i]=='-'){cur=num.top();num.pop();before=num.top();num.pop();before-=cur;num.push(before);}if(s[i]=='*'){cur=num.top();num.pop();before=num.top();num.pop();before*=cur;num.push(before);}if(s[i]=='/'){cur=num.top();num.pop();before=num.top();num.pop();before/=cur;num.push(before);}}while(!num.empty()){cout << num.top() << endl;num.pop();}return 0;
}

L2-1 彩虹瓶 (25 分)

rb.JPG

彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。

假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。

如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6 两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1 时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6 上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7 依次装填。

但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货，工人就必须要愤怒地折腾货架了，因为装填完 2 号颜色以后，不把货架上的多个箱子搬下来就拿不到 3 号箱，就不可能顺利完成任务。

输入格式：

输入首先在第一行给出 3 个正整数，分别是彩虹瓶的颜色数量 N（1<N≤10​3​​）、临时货架的容量 M（<N）、以及需要判断的发货顺序的数量 K。

随后 K 行，每行给出 N 个数字，是 1 到N 的一个排列，对应工厂的发货顺序。

一行中的数字都以空格分隔。

输出格式：

对每个发货顺序，如果工人可以愉快完工，就在一行中输出 YES；否则输出 NO。

输入样例：

7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1

输出样例：

YES
NO
NO
#include <bits/stdc++.h>
using namespace std;
bool flag;
int n, m, k, cur, number;
stack<int> s;
int main()
{//彩虹瓶的颜色数量 N(1<N<=1000)//临时货架的容量 M(M<N)//需要判断的发货顺序的数量K。cin >> n >> m >> k;for(int i=1; i<=k; ++i){cur=1;flag=true;for(int j=1; j<=n; ++j){cin >> number;//如果栈顶可用，用 while(!s.empty() && s.top()==cur){cur++;s.pop();}if(number==cur){	//当前可用，用 cur++;//如果栈顶可用，用  while(!s.empty() && s.top()==cur){cur++;s.pop();}}else{	//不可用，放 s.push(number);}if(s.size()>m){	//放不下了，标记为false flag=false;}}if(flag==false){	//放不下 cout << "NO" << endl;}else if(s.empty()){	//完美情况 cout << "YES" << endl;}else{	//栈不为空 cout << "NO" << endl;}while(!s.empty()){	//清空栈 s.pop();}}return 0;
}

P4387 【深基15.习9】验证栈序列

#include <bits/stdc++.h>
using namespace std;
int q, n, pushed[100010], poped[100010], pushid, asd;
stack<int> s;
int main()
{scanf("%d", &q);while(q--){//多测要清空 while(!s.empty()){s.pop();}scanf("%d", &n);//将入栈序列存下来 for(int i=1; i<=n; ++i){scanf("%d", &pushed[i]);}//将出栈序列存下来for(int i=1; i<=n; ++i){scanf("%d", &poped[i]);}asd=0;	//表示这一组测试数据入栈出栈匹配的数量 s.push(pushed[1]);	//将入栈序列中的第一个数入栈 pushid=2;			//待入栈序号赋值为2 for(int i=1; i<=n; ++i){	//枚举出栈序列 //栈不为空, 并且栈顶元素恰好等于出栈序列中的数 if(!s.empty() && poped[i]==s.top()){s.pop();	//出栈 asd++;		//出栈匹配数加一 if(asd==n){	//如果匹配数恰好等于n, 说明完全匹配 printf("Yes\n");break;	}}else{	//栈为空或者栈顶元素不等于出栈序列中的数 if(pushid>n){	//入栈序列中的元素已经全部入栈 //此时由于出栈序列中还有元素, 所以不可能匹配成功 printf("No\n");break;}s.push(pushed[pushid]);		//入栈 pushid++;i--;	//与for循环++i相抵消, 保持出栈序列的序号不变 }}}return 0;
}

//TODO

这篇关于栈的顺序表和链表实现，以及一些涉及到栈思想的题目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1135150。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注，收藏不迷路💖 Kubernetes的PodSecurityPolicy（PSP）是一个关键的安全特性，它在Pod创建之前实施安全策略，确保P
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2