实现栈（链式存储）
- 自己写个栈和教材上对比
- 栈的应用一：括号配对
- 栈的应用二：逆波兰数
- 栈的应用三：求解迷宫
- 习题板块
自己写的链式栈
#include<bits/stdc++.h>
using namespace std;
//自己写的链式栈
//要实现的操作有： 初始化栈initstack ， 销毁栈destroystack ， 判断栈空emptystack
// 取栈顶元素 gettop 进栈pushstack ， 出栈popstack , 打印栈元素printstack
typedef struct linknode{
int data;
struct linknode *next;
}sqstack;
void initstack(sqstack*&st){
st=(sqstack*)malloc(sizeof(sqstack));
st->next=NULL;
}
void destroystack(sqstack*&st){
sqstack *pre=st,*p=st->next;
while(p){
free(pre);
pre=p;
p=pre->next;
}
free(pre);
}
bool emptystack(sqstack*st){
return(st->next==NULL);
}
int gettop(sqstack*st){//栈空的时候请不要用这个函数
return st->next->data;
}
void pushstack(sqstack*&st,int e){
sqstack*p;
p=(sqstack*)malloc(sizeof(sqstack));
p->data=e;
p->next=st->next;
st->next=p;
}
bool popstack(sqstack*&st){
if(st->next==NULL)
return false;
// st->next=st->next->next;
// free(st->next);
// return true;
sqstack *p;
p=st->next; //p指向首结点
st->next=p->next;//删除首结点
free(p);
return true;
}
void printstack(sqstack*st){
st=st->next;//栈的头结点是没有数据的
while(st){
cout<<st->data<<" ";
st=st->next;
}
}
int main(){
sqstack *st;
initstack(st);
for(int i=1;i<=10;i++)
pushstack(st,i);
popstack(st);
printstack(st);
int bl=emptystack(st);
cout<<bl;
}标准栈结构（链式）
//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LinkStNode; //链栈类型
void InitStack(LinkStNode *&s)
{
s=(LinkStNode *)malloc(sizeof(LinkStNode));
s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
LinkStNode *p=s->next;
while (p!=NULL)
{
free(s);
s=p;
p=p->next;
}
free(s); //s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{ LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e; //新建元素e对应的结点p
p->next=s->next; //插入p结点作为开始结点
s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{ LinkStNode *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始结点
e=p->data;
s->next=p->next; //删除p结点
free(p); //释放p结点
return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}括号配对
例子3-5：设计一个算法判断输入的表达式中括号是否配对（假设只有左右，圆括号）
思路很明确，题目只设计圆括号，我觉得还可以加上方括号和❀括号，遇到左括号就进栈，遇到右括号就判断栈顶元素是否和它匹配，匹配就出栈， 这里我用自己写的栈代码来写，顺便看看自己写的栈有没有错误
//自己写的链式栈
//要实现的操作有： 初始化栈initstack ， 销毁栈destroystack ， 判断栈空emptystack
// 取栈顶元素 gettop 进栈pushstack ， 出栈popstack , 打印栈元素printstack
#include<bits/stdc++.h>
using namespace std;
typedef struct linknode{
char data;
struct linknode *next;
}sqstack;
void initstack(sqstack*&st){
st=(sqstack*)malloc(sizeof(sqstack));
st->next=NULL;
}
void destroystack(sqstack*&st){
sqstack *pre=st,*p=st->next;
while(p){
free(pre);
pre=p;
p=pre->next;
}
free(pre);
}
bool emptystack(sqstack*st){
return(st->next==NULL);
}
char gettop(sqstack*st){//栈空的时候请不要用这个函数
return st->next->data;
}
void pushstack(sqstack*&st,char e){
sqstack*p;
p=(sqstack*)malloc(sizeof(sqstack));
p->data=e;
p->next=st->next;
st->next=p;
}
bool popstack(sqstack*&st){
if(st->next==NULL)
return false;
// st->next=st->next->next;
// free(st->next);
// return true;
sqstack *p;
p=st->next; //p指向首结点
st->next=p->next;//删除首结点
free(p);
return true;
}
void printstack(sqstack*st){
st=st->next;//栈的头结点是没有数据的
while(st){
cout<<st->data<<" ";
st=st->next;
}
}
int main(){
string s;
cin>>s;
sqstack *st;
char ss;
int bl=1;
initstack(st);
for(int i=0;i<s.length();i++){
if(s[i]=='('||s[i]=='['||s[i]=='{')
pushstack(st,s[i]);
if(s[i]==')'){
if(emptystack(st)){
bl=0;
break;
}
ss=gettop(st);
if(ss=='(')
popstack(st);
else{
bl=0;
break;
}
}
if(s[i]==']'){
if(emptystack(st)){
bl=0;
break;
}
ss=gettop(st);
if(ss=='[')
popstack(st);
else{
bl=0;
break;
}
}
if(s[i]=='}'){
if(emptystack(st)){
bl=0;
break;
}
ss=gettop(st);
if(ss=='{')
popstack(st);
else{
bl=0;
break;
}
}
}
if(!emptystack(st))
bl=0;
if(bl)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
}标准答案（只判断了圆括号
//【例3.5】的算法：判断表达式中的括号是否配对
#include "listack.cpp"
#include <string.h>
bool Match(char exp[],int n)
{
int i=0; char e;
bool match=true;
LinkStNode *st;
InitStack(st); //初始化栈
while (i<n && match) //扫描exp中所有字符
{
if (exp[i]=='(') //当前字符为左括号,将其进栈
Push(st,exp[i]);
else if (exp[i]==')') //当前字符为右括号
{
if (GetTop(st,e)==true)
{
if (e!='(') //栈顶元素不为'('时表示不匹配
match=false;
else
Pop(st,e); //将栈顶元素出栈
}
else match=false; //无法取栈顶元素时表示不匹配
}
i++; //继续处理其他字符
}
if (!StackEmpty(st)) //栈不空时表示不匹配
match=false;
DestroyStack(st); //销毁栈
return match;
}
int main()
{
char exp[]="(1+2*(5+3)/2)";
if (Match(exp,strlen(exp))==1)
printf("表达式%s括号配对\n",exp);
else
printf("表达式%s括号不配对\n",exp);
return 1;
}栈的应用二：逆波兰数
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：实现栈（链式存储）
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-10-03)，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
