C++STL棧、隊(duì)列(Stack & Queue)
一、棧的概念
棧是一種特殊的線性表，其插入操作和刪除操作限定在表的一端進(jìn)行，這一段被稱為“棧頂”（top），相對(duì)的另一端稱為“棧底”（bottom）。插入操作一般稱之為“壓棧”（push），刪除操作稱之為“退?！保╬op）。棧的特點(diǎn)是“先進(jìn)后出” (LIFO,First In Last Out) 。
二、棧的操作
1.定義
stack<typename> 棧的名字;
1
其中typename是想要的數(shù)據(jù)類型。
哦，對(duì)了，要使用棧，還需要加上一個(gè)頭文件：（加了萬(wàn)能頭文件就不需要了）
#include <stack>
1
如果要存int,可以這么寫:
stack<int> s
1
2.棧的函數(shù)
假設(shè)已經(jīng)定義一個(gè)棧，名字是s，那么就有這些函數(shù)：
s.push(x); //插入元素,x表示要插入的值,什么都行（但是類型必須和定義的相同）
s.pop(); //將棧頂彈出,無(wú)返回值
s.empty(); //判斷是否是空棧
s.size(); //返回棧中有多少個(gè)元素
s.top(); //返回棧頂
s.swap(s2); //交換s和s2里面的值(s2需要和s是一個(gè)類型)
1
2
3
4
5
6
stack默認(rèn)是空隊(duì)列，如果不想怎么辦?
假設(shè)已經(jīng)定義了s1是stack<int>類型,那么可以這么寫:
stack<int> s2(s1);
1
2
注意！stack沒(méi)有重載=號(hào)！
舉個(gè)栗子:（倒序輸出）
#include <iostream>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
stack<int> s;
for(int i=1;i<=5;i++)
s.push(i);
while(!s.empty()){ //只要非空就循環(huán)
cout<<s.top()<<' ';
s.pop(); //這一步千萬(wàn)不要忘了
}
cout<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
來(lái)幾道題
表達(dá)式括號(hào)匹配(stack)
分析:不是括號(hào)不需要入棧，如果是左括號(hào)就入棧，如果是右括號(hào)就看棧頂是不是左括號(hào)，如果是，就把左括號(hào)彈出，否則輸出NO，結(jié)束程序。如果最后棧為空（所有左括號(hào)都被彈出了），輸出YES，否則輸出NO。
字符串匹配問(wèn)題(strs)
分析:其實(shí)和上一道差不多，只不過(guò)多了幾組數(shù)據(jù)和優(yōu)先級(jí)，可以一組數(shù)據(jù)一組數(shù)據(jù)的做，再弄一個(gè)棧，來(lái)保存每一個(gè)的最大的優(yōu)先級(jí)是多少，在入棧的時(shí)候判斷是否可行，如果可行把這個(gè)棧加上這個(gè)的優(yōu)先級(jí)，在出棧的同時(shí)把這個(gè)棧也刪一個(gè)。
表達(dá)式求值
分析：還是先分離，因?yàn)榉?hào)肯定比數(shù)字少一個(gè)，所以循環(huán)數(shù)字就行了，每循環(huán)一次就把這個(gè)數(shù)入棧，如果符號(hào)沒(méi)越界，那么就判斷符號(hào)是什么，如果是“+”，把棧頂?shù)膬蓚€(gè)數(shù)入棧，否則把這兩個(gè)數(shù)乘起來(lái)在對(duì)10000取模，再把結(jié)果入棧。因?yàn)闂＠锩娴臄?shù)都是要加的，所以把這些數(shù)加起來(lái)（加的同時(shí)要對(duì)10000取模），再輸出
后綴表達(dá)式
分析:可以遍歷一遍，把數(shù)找出來(lái)入棧，如果是符號(hào)，從棧里彈出兩個(gè)做運(yùn)算（注意要下面的-上面的（下面的/上面的））
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
分析，用了這個(gè)方法：
先定義一個(gè)棧，用來(lái)存運(yùn)算符，遍歷一遍中綴表達(dá)式
如果這個(gè)字符是數(shù)字，則輸出
否則，如果是運(yùn)算符的話，
3.1. 如果棧為空，或棧頂運(yùn)算符為左括號(hào)“(”，則直接將此運(yùn)算符入棧
3.2. 如果優(yōu)先級(jí)比棧頂運(yùn)算符的優(yōu)先級(jí)高，也將運(yùn)算符壓入棧
3.3.將棧頂?shù)倪\(yùn)算符彈出并輸出，再次轉(zhuǎn)到分析的第4行與棧中新的棧頂運(yùn)算符相比較。
否則（是括號(hào)）
4.1 如果是左括號(hào)，直接壓入棧
4.2 如果是右括號(hào)，則依次彈出棧頂?shù)倪\(yùn)算符，并輸出，直到遇到左括號(hào)為止，此時(shí)將左括號(hào)彈出（因?yàn)橛依ㄌ?hào)沒(méi)有入棧）。
還有一道題，也是表達(dá)式求值（有+ - * /），我是用了前面兩個(gè)的結(jié)合加判錯(cuò)：（自己試試，不給代碼）
中綴表達(dá)式值(expr)
--------------------------------------分割線--------------------------------------
驗(yàn)證棧序列
分析（一組數(shù)據(jù)）:可以把輸入的出棧序列的值改為在入棧序列中的位置，然后遍歷b數(shù)組，如果已入棧， 則看棧頂是否是它，如果不是，可以直接輸出“No”，看下一組數(shù)據(jù)了。如果未入棧，那就把它前面的都入棧，最后輸出“Yes”。
出棧序列
分析：我這里用一個(gè)計(jì)數(shù)器來(lái)記錄出棧了幾個(gè)，如果都出棧了，就結(jié)束循環(huán)
在大小為(c-棧的大小)的窗口里找最小的
如果棧非空
2.1 如果這個(gè)數(shù)比棧頂元素還小， 把前面的都入棧，當(dāng)前元素輸出
2.2 否則，輸出棧頂元素并出棧
否則，把前面的都入棧，當(dāng)前元素輸出
移動(dòng)到下一個(gè)窗口
自己嘗試做一做吧~
代碼
表達(dá)式括號(hào)匹配(stack)
#include <iostream>
#include <conio.h>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
char c;
stack<char> s;
do{
cin>>c;
if(c=='(')
s.push(c); //壓棧
else if(c==')'){
if(!s.empty()&&s.top()=='(')
s.pop(); //把左括號(hào)彈出
else{
cout<<"NO\n"; //沒(méi)有左括號(hào)
return 0;
}
}
}while(c!='@');
if(s.empty()) //如果左括號(hào)都彈出了
cout<<"YES\n";
else
cout<<"NO\n";
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
字符串匹配問(wèn)題(strs)
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <string>
#include <stack>
using namespace std;
int priority(char c) { //返回c的優(yōu)先級(jí)?
if(c=='<'||c=='>')
return 1;
if(c=='('||c==')')
return 2;
if(c=='['||c==']')
return 3;
if(c=='{'||c=='}')
return 4;
return -1;
}
bool is_left(char c) { //判斷是否是左括號(hào)?
return c=='('||c=='['||c=='{'||c=='<';
}
bool is_right(char c) {
return c==')'||c==']'||c=='}'||c=='>';
}
//兩個(gè)括號(hào)是否匹配?
bool match(char a,char b) {
if(!is_left(a)) //如果左邊的不是左括號(hào)?
return false;
if(a=='(')
return b==')';
if(a=='[')
return b==']';
if(a=='{')
return b=='}';
if(a=='<')
return b=='>';
}
//一個(gè)一個(gè)判斷?
bool func(stack<char>& s,char c,stack<int>& prioritys) {
if(is_left(c)) { //如果是左括號(hào)?
if(prioritys.top()>=priority(c)) {
s.push(c);
prioritys.push(priority(c));
} else {
return false; //優(yōu)先級(jí)太高?
}
} else if(is_right(c)) { //如果是右邊?
if(!s.empty()&&match(s.top(),c)) { //如果匹配?
s.pop();
if(!prioritys.empty()) //非空?
prioritys.pop();
} else
return false;
}
return true;
}
bool check(string str) {
stack<char> s;
stack<int> prioritys; //優(yōu)先級(jí)?
prioritys.push(0x7fffffff); //很大很大的數(shù)?
for(int i=0; i<str.size(); i++) {
char c=str[i];
if(!func(s,c,prioritys)) {
return false;
}
}
return s.empty();
}
int main(int argc,char* argv[],char** env) {
int n;
cin>>n;
getchar(); //以防把n后面的換行當(dāng)成第一個(gè)字符?
while(n--) {
string str;
getline(cin,str); //保險(xiǎn)，其實(shí)完全可以用cin>>str;
if(check(str))
cout<<"YES\n";
else
cout<<"NO\n";
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
表達(dá)式求值
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) {
return c>='0'&&c<='9';
}
string num[100003],operators; //數(shù)字和運(yùn)算符
int calc(string str) { //分離
int n=0,len=str.size();
for(int i=0; i<len; ++i) {
if(is_digit(str[i])) {
num[n]+=str[i];
} else {
n++;
operators+=str[i];
}
}
return ++n; //因?yàn)槭裁?，所以要??
}
int main(int argc,char* argv[],char** env) {
string str;
getline(cin,str);
int n=calc(str);
stack<int> s;
stack<char> op;
for(int i=0; i<n; i++) {
bool flag=false;
//下面用C++11的函數(shù)來(lái)把num[i]轉(zhuǎn)換成int，用的要在Dev-C++
//編譯選項(xiàng)->代碼生成/優(yōu)化->代碼生成->語(yǔ)言標(biāo)準(zhǔn) 設(shè)置位ISO C++11或GNU C++11
int x=stoi(num[i]);
s.push(x%10000);
char c;
if(i+1<n)
c=operators.at(i); //或operators[i]
else
flag=true; //最后一個(gè)
if(op.empty()||op.top()=='+') {
op.push(c);
} else { //op.top=='*'
s.pop();
int y=s.top();
s.pop();
s.push(x*y%10000);
op.push(c); //別忘了把當(dāng)前的加進(jìn)去
}
if(flag) { //最后一個(gè)要在這里判斷，為什么自己想想
int sum=0;
while(!s.empty()) {
sum+=s.top()%10000; //其實(shí)對(duì)不對(duì)10000取模都一樣，因?yàn)榉凑齪ush的時(shí)候
//都對(duì)10000取模了
sum%=10000; //這里非常重要，我就是沒(méi)寫這個(gè)才過(guò)不去，如果不寫這個(gè)的話下面的
//cout<<sum<<endl;就得改成cout<<sum%10000<<endl;
s.pop();
}
cout<<sum<<endl;
return 0; //加不加隨便，反正都是最后一輪
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
后綴表達(dá)式
#include <iostream>
#include <conio.h>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) { //判斷是否為數(shù)字，也可以用algorithm中的
return c>='0'&&c<='9';
}
int calc(string input) {
int x=0;
stack<int> s;
for(int i=0; i<input.size(); i++) {
char c=input[i];
if(is_digit(c)) { //如果是數(shù)字
x=x*10+c-'0'; //當(dāng)前的數(shù)
} else {
if(c=='@') //結(jié)束符
break;
if(c=='.') //分隔符
s.push(x);
x=0; //清0
if(c=='+'||c=='-'||c=='*'||c=='/') { //是運(yùn)算符
int b=s.top(); //注意要先取b，因?yàn)橄旅嬉猘+b或a-b或a*b或a/b
s.pop(); //取一個(gè)彈出一個(gè)
int a=s.top();
s.pop(); //這一步很重要
switch(c) {
case '+': {
s.push(a+b);
break;
}
case '-': {
s.push(a-b);
break;
}
case '*': {
s.push(a*b);
break;
}
case '/': {
s.push(a/b);
break;
}
default: {
break;
}
}
}
}
}
return s.top(); //棧里面應(yīng)該只剩結(jié)果了
}
int main(int argc,char* argv[],char** env) {
string s;
getline(cin,s); //保險(xiǎn)
cout<<calc(s)<<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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) {
return c>='0'&&c<='9';
}
int priority(char c) { //優(yōu)先級(jí)
if(c=='+'||c=='-')
return 1;
if(c=='*'||c=='/')
return 2;
}
string change(string str){ //把中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式?
string ans,x;
stack<char> s;
for(int i=0; i<str.size(); i++) {
char c=str[i];
if(is_digit(c)) {
x+=c;
if(i+1==str.size()||!is_digit(str[i+1])){
ans+=x; //將結(jié)果加這個(gè)數(shù)
ans+=' '; //為了區(qū)分是哪個(gè)數(shù)
x=""; //清空數(shù)
}
} else if(c=='+'||c=='-'||c=='*'||c=='/') {
while(1) {
if(s.empty()||s.top()=='(') {
s.push(c);
break;
} else if(priority(c)>priority(s.top())) {
s.push(c);
break;
} else {
char t=s.top();
s.pop();
ans+=t;
}
}
} else {
if(c=='(') {
s.push(c);
} else { //右括號(hào)?
while(s.top()!='(') {
char t=s.top();
s.pop();
ans+=t;
}
s.pop(); //將左括號(hào)彈出，不要忘了
}
}
}
while(!s.empty()){
ans+=s.top();
s.pop();
}
return ans;
}
int main(int argc,char* argv[],char** env) {
string str;
getline(cin,str); //保險(xiǎn)
cout<<change(str)<<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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
驗(yàn)證棧序列
#include <iostream>
#include <stack>
#include <map>
using namespace std;
bool check(int a[],int b[],bool is_pushed[],int n) {
stack<int> s;
for(int i=1; i<=n; i++) { //遍歷b數(shù)組?
if(is_pushed[b[i]]) { //b[i]已入棧?
if(!s.empty()&&s.top()!=a[b[i]])
return false;
s.pop(); //如果等于，將這個(gè)數(shù)彈出?
} else { //b[i]未入棧?
//把a(bǔ)[b[i]]的前面的元素入棧.
int j=b[i],k;
is_pushed[j]=true;
for(k=j-1;k>0;k--) //找到?jīng)]入棧的開(kāi)頭-1?
if(is_pushed[k])
break;
for(int l=k+1; l<j; l++) { //把前面的都入棧?
s.push(a[l]);
is_pushed[l]=true;
}
}
}
return true;
}
int main(int argc,char* argv[],char** env) {
int n,t;
cin>>t;
while(t--) {
map<int,int> mp; //mp[i]表示i在a數(shù)組中的下標(biāo)?
cin>>n;
int a[n+2],b[n+2],x; //a數(shù)組記錄入棧序列,b數(shù)組存出棧序列的數(shù)在a[]中的下標(biāo)?
bool is_pushed[n+2]; //is_pushed[i]記錄a[i]有沒(méi)有入棧
for(int i=1; i<=n; i++) {
cin>>a[i];
//初始化?
is_pushed[i]=0;
mp[a[i]]=i;
}
for(int i=1; i<=n; i++){
cin>>x;
b[i]=mp[x];
}
if(check(a,b,is_pushed,n)) //這里傳is_pushed因?yàn)橥耆梢栽谳斎氲臅r(shí)候初始化，不需要在里面初始化?
cout<<"Yes\n";
else
cout<<"No\n";
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
出棧序列
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
stack<int> s; //棧里存在a數(shù)組中的下標(biāo)??
int x,n,c,cnt=0;
cin>>n>>c;
int a[n+2],begin=0,end=c-1; //窗口的開(kāi)頭和結(jié)尾?
for(int i=0;i<n;i++)
cin>>a[i];
while(cnt<n){
//找a數(shù)組中最小?
int MinIndex=min(begin,n-1);
for(int i=min(begin,n-1);i<=end&&i<n;i++){
if(a[i]<a[MinIndex])
MinIndex=i;
}
//判斷??
if(!s.empty()){ //棧非空?
if(a[s.top()]<a[MinIndex]){ //如果棧頂元素比這個(gè)數(shù)還小?
cout<<a[s.top()]<<' '; //出棧?
cnt++;
a[s.top()]=0x7fffffff; //記錄已經(jīng)出棧了??
end++;
s.pop();
} else {
//把前面的都入棧?
for(int i=begin;i<MinIndex;i++){
if(a[i]<0x7fffffff){
s.push(i);
begin=i;
}
}
if(begin==MinIndex)
begin++;
else
begin+=2;
cout<<a[MinIndex]<<' '; //輸出??
cnt++;
a[MinIndex]=0x7fffffff;
end++;
}
} else { //棧為空??
//把前面的都入棧?
for(int i=begin;i<MinIndex;i++){
if(a[i]<0x7fffffff){
s.push(i);
begin=i;
}
}
if(begin==MinIndex)
begin++;
else
begin+=2;
cout<<a[MinIndex]<<' '; //也是輸出?
cnt++;
a[MinIndex]=0x7fffffff;
end++;
}
}
return 0;
}
————————————————
版權(quán)聲明：本文為CSDN博主「2345瀏覽器」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/orangebench11/article/details/104618433
