本章将讲解基础数据结构的实现。众所周知，程序=数据结构+算法。数据结构为算法提供服务，算法围绕数据结构操作。因此，掌握数据结构并用代码实现是至关重要的。
4. 基础数据结构
4.1 线性表
线性表是最简单、最基本的一种数据结构，线性表示多个具有相同类型的数据“串在一起”，每个元素有唯一的前驱（前一个元素）和唯一的后继（后一个元素）。根据不同的特点，线性表也分为栈、队列、链表等等。借助这些特点，线性表可以解决不同种类的问题。
4.1.1 栈
栈是一种先进后出的数据结构。类似于一个盒子，先进入的元素被压在栈底，后进入的元素放在栈顶，取元素时先从栈顶取，最后取栈底的最先放入的元素。
对于一个栈，我们需要的操作如下：
- push：向栈中加入一个数x。
- pop：将栈顶弹出。需要特判栈是否为空。
- query：输出栈顶元素。需要特判栈是否为空。
- size：输出此时栈内元素个数。
我们可以使用数组来模拟栈的操作，用一个top指针来指向栈顶的位置即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> using namespace std; int T,n; string q; unsigned long long x, stack[1000010]; int main() { cin>>T; while(T--) { cin>>n; int top=0; while(n--) { cin>>q; if(q=="push") { cin>>x; stack[++top]=x; } else if(q=="pop") { if(top==0) cout<<"Empty"<<endl; else top--; } else if(q=="query") { if(top==0) cout<<"Anguei!"<<endl; else cout<<stack[top]<<endl; } else if(q=="size") { cout<<top<<endl; } } } return 0; } |
同时，我们也可以使用STL标准模板库中，前人写好的栈：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <stack> using namespace std; int T,n; string q; unsigned long long x; int main() { cin>>T; while(T--) { cin>>n; stack<unsigned long long>s; while(n--) { cin>>q; if(q=="push") { cin>>x; s.push(x); } else if(q=="pop") { if(s.empty()) cout<<"Empty"<<endl; else s.pop(); } else if(q=="query") { if(s.empty()) cout<<"Anguei!"<<endl; else cout<<s.top()<<endl; } else if(q=="size") { cout<<s.size()<<endl; } } } return 0; } |
那么栈这样先进后出的问题可以为我们解决什么问题呢？
一类是表达式求值问题。还记得我们介绍的后缀表达式吗，它就极适合用栈来求值。
比如给出一个后缀表达式：352-*7+，这等价于中缀表达式的3*(5-2)+7，在求值的过程中，我们可以将数字压入栈中，直到读到一个符号时，取出栈顶的两个元素进行该运算。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <stack> using namespace std; stack<int>s; char c; int x; int main() { cin>>c; while(c!='@') { if(c>='0'&&c<='9')x=x*10+(c-'0'); else if(c=='.') { s.push(x); x=0; } else { int f1=s.top();s.pop(); int f2=s.top();s.pop(); if(c=='+')s.push(f2+f1); if(c=='-')s.push(f2-f1); if(c=='*')s.push(f2*f1); if(c=='/')s.push(f2/f1); } cin>>c; } cout<<s.top()<<endl; return 0; } |
另一类应用是括号匹配问题。我们可以将左括号入栈，碰到右括号则出栈一个左括号，来检验是否是正确的括号匹配，或者修改不正确的括号。这种方法通常不需要真的声明一个栈，但是用到了栈的思想。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; char c; int cnt=0; bool flag=true; int main() { cin>>c; while(c!='@') { if(c=='(')cnt++; else if(c==')') { if(cnt==0)flag=false; else cnt--; } cin>>c; } if(flag==false||cnt>0)cout<<"NO"<<endl; else cout<<"YES"<<endl; return 0; } |
最后我们来介绍单调栈。所谓单调栈，就是栈内元素满足从栈顶到栈底单调递增/减。这样的栈可以解决找一个人后面第一个比自己大/小的人的问题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <stack> using namespace std; int n; int a[3000010]; int ans[3000010]; stack<int>s; int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) { while(!s.empty()) { if(a[s.top()]<a[i]) { ans[s.top()]=i; s.pop(); } else break; } s.push(i); } for(int i=1;i<=n;i++)cout<<ans[i]<<" "; return 0; } |