0%

0-19 queue 與 stack

隊列(queue)

想像有一天,你來到了師大最熱門的 TOI 拉麵店,店內空間不大,只有三十個左右,因此門外的人排成了長長的隊伍。你加入到了隊列的尾端,等待老闆叫號。隨著時間過去,前面的人依序進入店裡,也看到不少人帶著滿足的笑容走出。終於,就快輪到你了!

只能從後方加入,並且只能從前方取出,這就稱作 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
#include<bits/stdc++.h>
using namespace std;
int arr[1000005], l=0, r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r] = x;
}

void pop(){
assert(l<=r); // 還有東西
l++;
}

int front(){
assert(l<=r);
return arr[l];
}

int siz(){
return r-l+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

這樣雖然可以得到正確的答案,但不免會有浪費空間(pop 後前方空間就浪費了)或記憶體不夠大的問題,因此,可將 r mod 陣列長度,當元素存到底時,就再回到第一格,以避免浪費空間,當然,陣列還是要開得夠大,至少必須超過同時存在的元素數量。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
int arr[N+5], l=0, r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r%N] = x;
}

void pop(){
assert(l<=r); // 還有東西
l++;
}

int front(){
assert(l<=r);
return arr[l%N];
}

int siz(){
return r-l+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << front() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

更好的方法

放在這個章節,想必可以想到,這東西其實是有 STL 的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
queue<int> q;

int main(){
q.push(1); // 從後方加入元素
q.push(2);
q.push(5);
cout << q.front() << '\n'; // 查看最前方元素
cout << q.size() << '\n'; // 查看queue大小
q.pop(); // 從前方移除元素
cout << q.front() << '\n'; // 查看最前方元素
cout << q.size() << '\n'; // 查看queue大小
q.pop();
q.pop();
if(q.empty()) cout << "Empty!\n";
}

這樣就完成了一個長度會自己變化的 queue 了!(當然,開太大還是會 RE)

要注意的一點是,如果在 queue 為空時,呼叫了 pop() 或 front() 等函式,都是會導致 RE 的!

stack

吃完了拉麵,要付錢時,你居然發現,錢包不知道為什麼不見了!沒有付錢的你只好乖乖留下來洗碗。

你每次會從最上方拿出一個碗來洗,有新的髒碗要洗時也會放在最上面。

只能從上方加入,並且只能從上方取出,這就稱作 stack!

實作

如何實作 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
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
int arr[N+5], r=-1; // 想想為什麼 r = -1

void push(int x){
r++;
arr[r] = x;
}

void pop(){
assert(r>=0);
r--;
}

int top(){
assert(r>=0);
return arr[r];
}

int siz(){
return r+1;
}

int main(){
push(1); // 從後方加入元素
push(2);
push(5);
cout << top() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
pop(); // 從前方移除元素
cout << top() <<'\n'; // 查看最前方元素
cout << siz() <<'\n'; // 查看queue大小
}

事實上,也完全可以使用能動態改變長度,並且能從後方加入刪除的 vector 來實作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
vector<int> arr;


int main(){
arr.push_back(1); // 從後方加入元素
arr.push_back(2);
arr.push_back(5);
cout << arr.back() <<'\n'; // 查看最前方元素
cout << arr.size() <<'\n'; // 查看queue大小
arr.pop_back(); // 從前方移除元素
cout << arr.back() <<'\n'; // 查看最前方元素
cout << arr.size() <<'\n'; // 查看queue大小
}

不過,還是有一個名為 stack 的 STL,它是這樣用的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000;
stack<int> stk;


int main(){
stk.push(1); // 從後方加入元素
stk.push(2);
stk.push(5);
cout << stk.top() <<'\n'; // 查看最前方元素
cout << stk.size() <<'\n'; // 查看queue大小
stk.pop(); // 從前方移除元素
cout << stk.top() <<'\n'; // 查看最前方元素
cout << stk.size() <<'\n'; // 查看queue大小
}

功用

queue 與 stack 與其說是一種工具,更像是一種概念。queue 代表著的是,先進去的元素一定先出來(FIFO),而 stack 則是剛好相反。

STL 的 queue 與 stack 本身,都能夠輕易被其他工具代替。我們使用它們的原因,是因為它們所表達出來的概念,能夠讓程式可讀性更高。

你可能第一時間看不懂一個 vector 一直 push_back() 又 pop_back(),但只要看到 stack,就可確信這裡用到了先進後出的概念,從而更快理解整段程式碼。

練習

ZJ b923

ZJ e155

★★ ZJ c123

★★ ZJ a565

★★★★ ZJ a813

★★★★★ ZJ a664

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// b923
#include<bits/stdc++.h>
using namespace std;
int n, ope, x;
stack<int> s;

int main(){
cin >> n;
while(n--){
cin >> ope;
if(ope == 1){
s.pop();
}
else if(ope == 2){
cout << s.top() << '\n';
}
else{
cin >> x;
s.push(x);
}
}
}

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
// ZJ e155
#include<bits/stdc++.h>
using namespace std;
int n;
queue<int> q;
vector<int> dis;

int main(){
while(cin>>n){
if(n==0) break;
dis.clear();
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) q.push(i);
while(q.size() > 1){
dis.push_back(q.front());
q.pop();
q.push(q.front());
q.pop();
}
cout << "Discarded cards: ";
for(int i=0;i<dis.size();i++){
if(i>0) cout << ", ";
cout << dis[i];
}
cout << '\n';
cout << "Remaining card: " << q.front() << "\n";
}
}
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
// ZJ c123
#include<bits/stdc++.h>
using namespace std;
int n;
stack<int> station;
queue<int> train;

int main(){
while(cin>>n){
if(n == 0) break;
while(1){
bool ok = 1, out = 0;
while(!station.empty()) station.pop();
while(!train.empty()) train.pop();

for(int i=1;i<=n;i++){
train.push(i);
}

for(int i=1,x;i<=n;i++){
cin >> x;
if(x == 0){
out = 1;
break;
}
while(station.empty() || station.top() != x){
if(train.empty()){
ok = 0;
break;
}
else{
station.push(train.front());
train.pop();
}
}
if(ok) station.pop();
}
if(out) break;
else if(ok) cout << "Yes\n";
else cout << "No\n";
}
cout << '\n';
}
}

我們分別計算往左與往右能夠看到多少大樓,對於一個大樓,如果右邊出現比他高的大樓,那這座大樓就永遠不會再被右邊的其他人看到了。這題用到了單調隊列這個有趣的東西,有興趣的可以自行查詢,未來有機會也會單獨開一個章節介紹。

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
// ZJ a813
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
ll arr[1000005], n;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++){
cin >> arr[i];
}
ll ans = 0;
for(int t=0;t<2;t++){
stack<pii> s;
for(int i=1;i<=n;i++){
while(!s.empty() && s.top().first < arr[i]){
ans += s.top().second;
s.pop();
}
if(!s.empty() && s.top().first == arr[i]){
pii tmp = s.top();
s.pop();
if(!s.empty()) ans++;
ans += tmp.second;
s.emplace(tmp.first, tmp.second+1);
}
else{
if(!s.empty()) ans++;
s.emplace(arr[i], 1);
}
}
reverse(arr+1, arr+1+n);
}
cout << ans << '\n';
}

將中序算式轉為後序運算式後,進行運算。
中序轉後序

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
// ZJ a664
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int pri[128];

stack<ll> stk;
stack<char> op;

ll calc(ll a1, ll a2, char ope){
//cout << a1 << " " << a2 << " " << ope << '\n';
if(ope == '+') return a1+a2;
if(ope == '-') return a1-a2;
if(ope == '*') return a1*a2;
if(ope == '/') return a1/a2;
return -1;
}

string s;
void solve(){
cin >> s;
bool is_num = 0;
int num = 0;
for(auto &c:s){
if(isdigit(c)) num = num * 10 + c - '0', is_num = 1;
else{
if(is_num) stk.push(num), num = 0, is_num = 0;
if(c == ')'){
while(op.top() != '('){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
op.pop();
}
else if(c == '(') op.push(c);
else{
while(!op.empty() && op.top() != '(' && pri[op.top()] > pri[c]){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
op.push(c);
}
}
}
if(is_num) stk.push(num);

while(stk.size() > 1){
ll a2 = stk.top();
stk.pop();
ll a1 = stk.top();
stk.pop();
char ope = op.top();
op.pop();
stk.push(calc(a1, a2, ope));
}
cout << stk.top() << '\n';
stk.pop();
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
pri['*'] = pri['/'] = 1;
pri['+'] = pri['-'] = 0;

int t;
cin >> t;
while(t--) solve();
}