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 保持裡面所存位置對應的元素的單調遞減性。實際做法就是，遇到比他大的就丟掉，反正已經確認現在這個元素已經比他大了，後面也不會用到。否則他就還沒遇到還沒遇到比他大的。
以下為程式碼