概念
- 堆疊（stack）是一種運算受限的線性表，堆疊只能從末尾插入或洗掉資料，我們把這一端稱為堆疊頂，對應地，把另一端稱為堆疊底，
- 佇列（queue）是一種線性表，它允許在表的某一端進行插入操作，在另一端進行洗掉操作，我們把進行洗掉操作的一端稱作佇列的隊尾，把進行插入操作的一端稱作佇列的隊首，
實作
注：由于堆疊和佇列的實作方法不同，故分開講解，
堆疊
- 使用一個陣列模擬堆疊，用top表示堆疊頂，如果插入資料，則++top，洗掉則--top，
- 使用STL庫中自帶的stack（堆疊），以下為stack中常見的命令：
1 stack.push(x)//向堆疊中添加元素x 2 stack.pop()//洗掉堆疊頂的元素 3 stack.size()//堆疊的大小 4 stack.top()//回傳堆疊頂的元素 5 stack.empty()//回傳是否為空堆疊（即堆疊中是否沒有元素），如果是則回傳true
注意：使用STL中的stack前需要參考，
1 #include<stack>//參考 2 using namespace std; 3 stack<int>st;//宣告一個名字為st，存放資料為整型的堆疊（存盤資料型別在<>中修改）
佇列
- 使用一個陣列模擬佇列，用head（或h）表示佇列的隊尾，用tail（或t）表示隊首，如果插入資料，則++head，洗掉則--tail，
- 使用STL庫中自帶的queue（佇列），以下為queue中常見的命令：
1 queue.push(x)//在隊首插入元素x 2 queue.pop()//洗掉隊尾的元素 3 queue.size()//回傳佇列的長度 4 queue.empty()//判斷佇列是否為空 5 queue.front()//回傳隊首的值 6 queue.back()//回傳隊尾的值
注意：與stack一樣，使用STL的佇列也需要參考，
1 #include<queue> 2 using namespace std; 3 queue<int>qu;
應用
堆疊
后綴運算式（P1449）
1 #include<bits/stdc++.h> 2 using namespace std; 3 stack<int>st; 4 char ops; 5 int now=0,pre=0; 6 int main(){ 7 while(ops!='@') 8 { 9 scanf("%c",&ops); 10 if(ops>='0'&&ops<='9') 11 { 12 now=now*10+ops-'0'; 13 } 14 if(ops=='.') 15 { 16 st.push(now); 17 now=0; 18 } 19 switch(ops) 20 { 21 case '+': 22 for(int i=1;i<=2;++i) 23 { 24 now+=st.top(); 25 st.pop(); 26 } 27 st.push(now); 28 now=0; 29 break; 30 case '-': 31 now+=st.top(); 32 st.pop(); 33 now-=st.top(); 34 st.pop(); 35 st.push(0-now); 36 now=0; 37 break; 38 case '*': 39 now=1; 40 for(int i=1;i<=2;++i) 41 { 42 now*=st.top(); 43 st.pop(); 44 } 45 st.push(now); 46 now=0; 47 break; 48 case '/': 49 now+=st.top(); 50 st.pop(); 51 pre+=st.top(); 52 st.pop(); 53 st.push(pre/now); 54 now=0,pre=0; 55 break; 56 } 57 } 58 printf("%d",st.top()); 59 return 0; 60 }
打掃宿舍（T178339）
1 #include<bits/stdc++.h> 2 using namespace std; 3 stack<int>H; 4 int n,last,sum=0,w,h; 5 int main(){ 6 scanf("%d",&n); 7 scanf("%d%d",&w,&h); 8 H.push(h); 9 sum=1; 10 for(int i=2;i<=n;++i) 11 { 12 scanf("%d%d",&w,&h); 13 while(!(H.empty())&&H.top()>h) 14 { 15 H.pop(); 16 } 17 if(!H.empty()) 18 { 19 if(h>H.top()) 20 { 21 ++sum; 22 H.push(h); 23 } 24 } 25 else{ 26 H.push(h); 27 ++sum; 28 } 29 } 30 printf("%d",sum); 31 return 0; 32 }
面積（T178340）
1 #include<bits/stdc++.h> 2 using namespace std; 3 char n[20100]; 4 int sum=0,s=0; 5 struct Node 6 { 7 int S; 8 int left; 9 }; 10 stack<int>st1; 11 stack<Node>st2; 12 int a[20100]; 13 int main() 14 { 15 scanf("%s",n+1); 16 int m=strlen(n+1); 17 for(int i=1;i<=m;++i){ 18 if(n[i]=='\\'){ 19 st1.push(i); 20 } 21 if(n[i]=='/'&&!st1.empty()){ 22 int k=st1.top(); 23 sum+=i-k; 24 st1.pop(); 25 s=i-k; 26 while(!st2.empty()&&st2.top().left>k){ 27 s+=st2.top().S; 28 st2.pop(); 29 } 30 st2.push((Node){s,k}); 31 } 32 } 33 printf("%d\n",sum); 34 printf("%d ",st2.size()); 35 int cnt=0; 36 while(!st2.empty()){ 37 a[++cnt]=st2.top().S; 38 st2.pop(); 39 } 40 for(int i=cnt;i>=1;--i){ 41 printf("%d ",a[i]); 42 } 43 return 0; 44 }
佇列
合并果子（P1090）
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=10010; 4 int f1[N],n,f2[N],h1=1,h2=1,t1,t2; 5 long long ans=0; 6 int a1=0,a2=0,a3=0,s,f=1; 7 int main(){ 8 memset(f1,0x3f,sizeof(f1)); 9 memset(f2,0x3f,sizeof(f2)); 10 scanf("%d",&n); 11 for(int i=1;i<=n;++i) 12 { 13 scanf("%d",&f1[i]); 14 } 15 sort(f1+1,f1+n+1); 16 t1=n+1,t2=1; 17 for(int i=2;i<=n;++i) 18 { 19 a1=f1[h1]+f1[h1+1]; 20 a2=f1[h1]+f2[h2]; 21 a3=f2[h2]+f2[h2+1]; 22 s=a1,f=1; 23 if(a3<s) 24 { 25 f=2,s=a3; 26 } 27 if(a2<s) 28 { 29 f=3,s=a2; 30 } 31 ans+=s,f2[t2]=s; 32 ++t2; 33 if(f==1) 34 { 35 h1+=2; 36 } 37 if(f==2) 38 { 39 h2+=2; 40 } 41 if(f==3) 42 { 43 ++h1,++h2; 44 } 45 } 46 printf("%lld",ans); 47 return 0; 48 }
Blah數集（T178342）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a,n; 4 int main() 5 { 6 while(scanf("%d%d",&a,&n)==2){ 7 queue<long long>st1,st2; 8 long long ans=a; 9 st1.push(2*a+1); 10 st2.push(3*a+1); 11 for(int i=2;i<=n;++i){ 12 long long x=st1.front(),y=st2.front(); 13 if(x<y){ 14 ans=x; 15 st1.pop(); 16 }else if(x==y){ 17 ans=x; 18 st1.pop(); 19 st2.pop(); 20 }else{ 21 ans=y; 22 st2.pop(); 23 } 24 st1.push(2*ans+1); 25 st2.push(3*ans+1); 26 } 27 printf("%lld\n",ans); 28 } 29 return 0; 30 }
用STL的堆疊/佇列還是手寫需要看題目需求——并不是所有的堆疊都可以用STL里的方便地解決，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/484317.html
標籤：C++
上一篇：C++設計模式——單例模式