首页 > 代码库 > C++ 数据结构之栈
C++ 数据结构之栈
栈作为最常用的数据结构之一，一直是算法竞赛中最基础的的内容，但是它和递归一起算是初学者的噩梦，我在此也就秉着复习知识加造福新人的初衷，写一篇关于栈的基础详解。
栈也叫后进先出表，LIFO表，其实可以想象成一摞书，先搁上去的会被压在最底下，而最上面的书却是最后摞上去的。
这样讲还是比较抽象，我这里附图解释吧：
首先原始的栈中元素从下至上为“2,7,1”，而执行“压入8”之后最上层多了一个元素“8”，而后的push(2)则同理。执行pop()会弹出最上层的元素，执行三次后栈中元素还剩下“2,7”。
为了让大家更好的理解，这里附上手写栈的代码。
#include <bits/stdc++.h>using namespace std;int n, top = 0;int a[105];int Do[105];int Top()//返回栈顶元素 { return a[top - 1];}void pop()//弹栈 { if (top > 0) a[top] = 0;}void push(int x)//压栈 { a[top] = x; top++;}int main(){ cin >> n; for (int i = 1; i <= n; i++) cin >> Do[i];//操作命令数组 for (int i = 1; i <= n; i++) { if (Do[i] == 1)//1压2弹 push(i); else if (top > 0) pop();//栈非空才弹，否则错误 else cout << "Error"; } cout << Top();//输出栈顶 }
这只是个“婴幼儿版本”的手写栈，目的只是便于理解罢了，漏洞还是很多的，比如没有判空函数，而是用一个假指针来判断等等，权当做一个理解工具罢了，实际上做题时一般会使用头函数<stack>中的自带栈。
下面上几道题来辅助理解。
Codevs 2058 括号序列
样例输入
2
{()}<<>>
{{{{{}}}}
样例输出
TRUE
FALSE
这是道很经典的栈题，只需要用数组模拟栈就行，把左括号压栈，如果匹配到右括号就弹，若空则合法。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cstring>using namespace std;char s[2000001],a[2000001];int top=0;int i,j,n;int main(){ cin>>n; for( i = 1; i <= n; i++) { bool f = 1; cin >> s; int l = strlen(s); for(j = 0; j < l; j++) { if(s[j]==‘(‘||s[j]==‘{‘||s[j]==‘[‘||s[j]==‘<‘) { top++; a[top]=s[j]; } else if((s[j]==‘)‘)&&(a[top]==‘(‘)&&(top>0)) top--; else if(s[j]==‘]‘&&a[top]==‘[‘&&top>0) top--; else if(s[j]==‘>‘&&a[top]==‘<‘&&top>0) top--; else if(s[j]==‘}‘&&a[top]==‘{‘&&top>0) top--; else { f=0; break; } } if(f==0) cout<<"FALSE"<<endl; else if(top>0) cout<<"FALSE"<<endl; else cout<<"TRUE"<<endl; top=0; } return 0;}
Codevs 2821 天使之城
一样利用栈来模拟暂停站区，常规进行压弹栈操作就好。
#include <bits/stdc++.h>using namespace std;int p = 1;int n, cnt;int ans[105];char a[105];stack<int>s;int main(){ scanf("%d", &n); scanf("%s", a+1); for (int i = 1; i <= n; i++) { if (a[i] == ‘A‘) { ans[p] = p; p++; continue; } else if (a[i] == ‘B‘) { s.push(i); cnt++; if (cnt > 5) { cout << "No"; return 0; } continue; } else if (a[i] == ‘C‘) { if (s.empty() == 1) { cout << "No"; return 0; } else { ans[p] = s.top(); p++; s.pop(); cnt--; } continue; } } cout << "Yes\n"; for (int i = 1; i < p; i++) cout << ans[i] << endl; return 0;}
暂时就写这么多吧，日后会更新
<style></style>C++ 数据结构之栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。