從零開始的演算法競賽入門教學
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();
}