Stack，又稱作堆疊，顧名思義就是從上面(也可以說前面)放入與取出的資料結構。 Queue，稱為佇列，是從前面放後面取出的資料結構。
實作程式碼如下
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
| #include<bits/stdc++.h>
using namespace std;
template<class T>
class Stack{
private:
int t=-1;
vector<T> dt;
public:
T top(){
if(t!=-1){
return dt[t];
}else{
cout<<"Stack is empty.\n";
}
}
void pop(){
if(t!=-1){
t--;
dt.pop_back();
}else{
cout<<"Stack is empty.\n";
}
}
void push(T p){
t++;
dt.push_back(p);
}
};
template<class T>
class Queue{
private:
deque<T> dt;
public:
T front(){
if(!dt.empty()){
return dt.front();
}else{
cout<<"Queue is empty.\n";
}
}
void pop(){
if(!dt.empty()){
dt.pop_front();
}else{
cout<<"Queue is empty.\n";
}
}
void push(T p){
dt.push_back(p);
}
};
|
C++已經幫你將這兩個資料結構實做好了，以下示範例程式碼
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
| #include<iostream>
#include<stack>
#include<queue>
#include<deque>
using namespace std;
int main(){
stack<int> st;
for(int i=0;i<10;++i){
st.push(i);
}
cout<<st.size()<<"\n";
while(!st.empty()){
cout<<st.top()<<" ";
st.pop();
}
cout<<"\n\n";
queue<int> q;
for(int i=0;i<10;++i){
q.push(i);
}
cout<<q.size()<<"\n";
while(!q.empty()){
cout<<q.front()<<" "<<q.back()<<"\n";
q.pop();
}
cout<<"\n";
}
|
光聽這兩個介紹以及大部分的分享，相信你還是不知道這兩個東西要用在哪裡。以下會有幾個應用的範例，都是用 STL 。
1.在 O(N) 的複雜度下做單調對列 Ex : 洛谷
題目敘述： 對於每個元素，從後面找出第一個比他大的元素的位置
這題就是要透過 stack 保持裡面所存位置對應的元素的單調遞減性。實際做法就是，遇到比他大的就丟掉，反正已經確認現在這個元素已經比他大了，後面也不會用到。否則他就還沒遇到還沒遇到比他大的。
以下為程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;++i) cin>>v[i];
vector<int> ans(n,0);
stack<int,vector<int>> st;
for(int i=0;i<n;++i){
while(!st.empty() && v[st.top()]<v[i]){
ans[st.top()]=i+1;
st.pop();
}
st.push(i);
}
for(int a:ans)
cout<<a<<" ";
}
|
2.以 O(N) 在滑動窗口中找最大以及最小值 Ex : 洛谷
題目敘述： 在所有長度為k的窗口中找到最大以及最小值
這題要用deque(double-ended-queue)，也就是雙向佇列，是一個從前後方都可以加入以及刪除值的queue。用以維持內部元素既在範圍以內，又保持單調遞增或遞減。
以下為程式碼
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int nm[1000010]={0},rmax[1000010],rmin[1000010];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++) cin>>nm[i];
deque<int> mx,mn;
for(int i=0;i<k;i++){
while(!mx.empty() && nm[mx.front()]<nm[i])
mx.pop_front();
mx.push_front(i);
while(!mn.empty() && nm[mn.front()]>nm[i])
mn.pop_front();
mn.push_front(i);
}
rmax[0]=mx.back();
rmin[0]=mn.back();
for(int i=1,j=k;j<n;i++){
while(!mx.empty() && mx.back()<i)
mx.pop_back();
while(!mn.empty() && mn.back()<i)
mn.pop_back();
while(!mx.empty() && nm[mx.front()]<nm[j])
mx.pop_front();
mx.push_front(j);
while(!mn.empty() && nm[mn.front()]>nm[j])
mn.pop_front();
mn.push_front(j);
rmax[i]=mx.back();
rmin[i]=mn.back();
j++;
}
for(int i=0;i<n-k+1;i++)
cout<<nm[rmin[i]]<<" ";
cout<<"\n";
for(int i=0;i<n-k+1;i++)
cout<<nm[rmax[i]]<<" ";
return 0;
}
|