# 0-19 queue 與 stack
講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月7日
## [ZeroJudge: e155. 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155)
### Python 程式碼
執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。但是這樣寫效率不好，因為移除串列索引值 0 的資料時，需要將之後的資料記憶體位址都往前移一格，時間複雜度是 $O(n)$。
```python=
while True:
n = int(input())
if n == 0: break
elif n == 1:
print("Discarded cards: ")
print("Remaining card: 1")
else:
cards = [i for i in range(1, n+1)]
discards = []
while len(cards) > 1:
discards.append(cards.pop(0))
c = cards.pop(0)
cards.append(c)
print("Discarded cards: ", end="")
for i in range(len(discards)):
print("{:d}".format(discards[i]), end="\n" if i == len(discards)-1 else ", ")
print("Remaining card: {:d}".format(cards[0]))
```
執行時間最久約為 22 ms，使用記憶體最多約為 3.2 MB，通過測試。
```python=
from collections import deque
while True:
n = int(input())
if n == 0: break
elif n == 1:
print("Discarded cards: ")
print("Remaining card: 1")
else:
cards = deque([i for i in range(1, n+1)])
discards = deque()
while len(cards) > 1:
discards.append(cards.popleft())
c = cards.popleft()
cards.append(c)
print("Discarded cards: ", end="")
for i in range(len(discards)):
print(f"{discards[i]:d}", end="\n" if i == len(discards)-1 else ", ")
print(f"Remaining card: {cards[0]:d}")
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 316 kB，通過測試。
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n;
while(true) {
cin >> n;
if (n == 0) {
break;
} else if (n == 1) {
cout << "Discarded cards: \n";
cout << "Remaining card: 1\n";
} else {
queue<int> cards, discards;
for(int i=1; i<=n; i++) cards.push(i);
while(cards.size() > 1) {
int d = cards.front();
cards.pop();
discards.push(d);
int c = cards.front();
cards.pop();
cards.push(c);
}
cout << "Discarded cards: ";
while(discards.size() > 1) {
cout << discards.front() << ", ";
discards.pop();
}
cout << discards.front() << "\n";
cout << "Remaining card: " << cards.front() << "\n";
}
}
return 0;
}
```
## [ZeroJudge: c123. 00514 - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
後來我再一次寫到這題，看起來第二次的寫法比較精簡，[連結在這裡](https://hackmd.io/@yizhewang/rkRkKNzMJx#ZeroJudge-c123-00514---Rails)。
### Python 程式碼
執行時間最久約為 0.2 s，使用記憶體最多約為 3.8 MB，通過測試。
```python=
import sys
for line in sys.stdin: # 由標準輸入逐行讀取資料並存入字串 line
N = int(line) # 將 line 轉成 int 並存入 N
if N == 0: break # 如果 N 為 0 中止迴圈
else: # 如果 N 不為 0，讀取列車於 B 的排序
for line in sys.stdin: # 由標準輸入逐行讀取資料並存入字串 line
if line == "0\n": # 如果 line 為 0\n，印出空行並跳出內層的 for 迴圈
print(); break;
else: # 如果 line 不為 0\n
A = [i for i in range(1, N+1)] # 産生列車於 A 的排序，由 1 ~ N
B = list(map(int, line.split())) # 將 line 轉成串列 B，為列車於 B 的排序
station = [] # 暫時停在車站的車廂編號
flag = True # 是否可以達成題目要求的 B 排序，預設為 True
for i in range(N): # 依序由 B 讀取要檢查的車廂編號並存入 need
need = B[i]
if station and station[-1] == need: # 如果 station 中有資料且最後一個車廂是要檢查的編號
station.pop(); continue # 將這個車廂移出 station，忽略 else 的部分，回到第17行繼續檢查 B 的下一個車廂
else: # 如果在 station 中沒有找到 need，改在 A 中尋找 need
find = False # 是否在 A 當中找到 need，預設為 False
while A: # 如果 A 還有資料則繼續執行 while 迴圈
a = A.pop(0) # 取出 A 最前方的資料並存入 a
if a == need: # 如果 a 等於 need，找到了，find 設定為 True，跳出第23行的 while 迴圈
find = True; break
else: # 如果 a 不等於 need，將 a 加入 station 最後面，繼續檢查 A 的下一個車廂
station.append(a)
if not find: # 如果沒有在 A 找到 need，無法達成題目要求的排序 B，flag 設定為 False，跳出第17行的 for 迴圈
flag = False; break
print("Yes" if flag else "No") # 如果 flag 為 True 印出 Yes，反之印出 No
```
### C++ 程式碼
執行時間最久約為 80 ms，使用記憶體最多約為 336 kB，通過測試。
```cpp=
#include <iostream>
#include <deque>
using namespace std;
int main() {
int N; // 儲存資料的變數 N
while(cin >> N) { // 由標準輸入讀取資料並存入 N
if (N == 0) { // 如果 N 為 0 中止迴圈
break;
} else { // 如果 N 不為 0，讀取列車於 B 的排序
while(true) { // 無窮迴圈
int d; cin >> d; // 由標準輸入讀取資料並存入 d
if (d == 0) { // 如果 d 為 0，印出空行並跳出第13行的 while 迴圈
cout << "\n"; break;
} else { // 如果 d 不為 0
deque<int> A, station; // 儲存資料用的雙向佇列 A 及 station
for(int i=1; i<=N; i++) A.push_back(i); // 産生列車於 A 的排序，由 1 ~ N
int B[N]; B[0] = d; // 列車於 B 的排序，記得要先存入 d
for(int i=1; i<N; i++) { // 存入 B[1] ~ B[N-1] 的資料
cin >> d; B[i] = d;
}
bool flag = true; // 是否可以達成題目要求的 B 排序，預設為 true
for(int i=0; i<N; i++) { // 依序由 B 讀取要檢查的車廂編號並存入 need
int need = B[i];
if (!station.empty() && station.back() == need) { // 如果 station 中有資料且最後一個車廂是要檢查的編號
station.pop_back(); continue; // 將這個車廂移出 station，忽略 else 的部分，回到第17行繼續檢查 B 的下一個車廂
} else { // 如果在 station 中沒有找到 need，改在 A 中尋找 need
bool find = false; // 是否在 A 當中找到 need，預設為 false
while(!A.empty()) { // 如果 A 還有資料則繼續執行 while 迴圈
int a = A.front(); A.pop_front(); // 取出 A 最前方的資料並存入 a
if (a == need) { // 如果 a 等於 need，找到了，find 設定為 True，跳出第30行的 while 迴圈
find = true; break;
} else { // 如果 a 不等於 need，將 a 加入 station 最後面，繼續檢查 A 的下一個車廂
station.push_back(a);
}
}
if (!find) { // 如果沒有在 A 找到 need，無法達成題目要求的排序 B，flag 設定為 False，跳出第25行的 for 迴圈
flag = false; break;
}
}
}
cout << (flag ? "Yes" : "No") << "\n"; // 如果 flag 為 true 印出 Yes，反之印出 No
}
}
}
}
return 0;
}
```
## [ZeroJudge: a565. 2.p&q的邂逅](https://zerojudge.tw/ShowProblem?problemid=a565)
### Python 程式碼
於第4筆測資會超時。
```python=
import sys
n = int(sys.stdin.readline())
for _ in range(n):
s = sys.stdin.readline()
ps = []
ans = 0
for c in s:
if c == 'p':
ps.append(1)
elif c == 'q' and ps:
ps.pop(); ans += 1
print(ans)
```
### C++ 程式碼
執行時間最久約為 0.2 s，使用記憶體最多約為 25.8 MB，通過測試。
```cpp=
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0),cin.tie(0);
int n; cin >> n;
string s;
for(int i=0; i<n; i++) {
stack<int> ps;
cin >> s;
int ans = 0;
for(auto c : s) {
if (c == 'p') {
ps.push(1);
} else if (c == 'q' && !ps.empty()) {
ps.pop(); ans++;
}
}
cout << ans << "\n";
}
return 0;
}
```
## [ZeroJudge: a813. 4. 城市觀測](https://zerojudge.tw/ShowProblem?problemid=a813)
### Python 程式碼
第三筆測資超時。
```python=
n = int(input()) # 房子數量
hs = [0] + list(map(int, input().split())) # 每一棟房子的高度，開頭加入 0
ans = 0 # 答案預設為 0
for _ in range(0, 2): # 執行2次，前向右掃與左側房子比較高度，再向左掃與右側房子比較高度
st = [] # 放入的資料為 [目前最高的高度, 累計數量]
for i in range(1, n+1): # 依序檢查第 1 ~ n 棟房子
while st and st[-1][0] < hs[i]: # 如果 st 還有資料而且 st 最後一項的高度小於第 i 棟房子
ans += st[-1][1] # ans 加上 st 最後一項的累計數量
st.pop() # 移除最後一項
if st and st[-1][0] == hs[i]: # 如果 st 還有資料而且 st 最後一項的高度等於第 i 棟房子
tmp = st.pop() # 暫存 st 最後一項至 tmp 並移除
if st: ans += 1 # 如果 st 還有資料 ans 加 1
ans += tmp[1] # ans 加上 tmp[1]
st.append([tmp[0], tmp[1]+1]) # st 最後加上 [tmp 的高度, tmp 原來的數量加 1]
else: # 如果 st 沒有資料或是最後一項的高度小於第 i 棟房子
if st: ans += 1 # 如果 st 還有資料 ans 加 1，因為一定能看到隔壁的房子
st.append([hs[i], 1]) # st 最後加上 [第 i 棟房子的高度, 數量為 1]
# end of for loop
hs[1:].reverse() # 將 hs[1] ~ hs[n] 順序反過來，
# end of for loop
print(ans)
```
### C++ 程式碼
執行時間最久約為 0.2 s，使用記憶體最多約為 10.4 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
LL n; cin >> n; // 房子數量
vector<LL> hs (n+1, 0); // 每一棟房子的高度，開頭加入 0
for(LL i=1; i<=n; i++) cin >> hs[i];
LL ans = 0; // 答案預設為 0
for(int k=0; k<2; k++) { // 執行2次，前向右掃與左側房子比較高度，再向左掃與右側房子比較高度
stack<pair<LL, LL>> st; // 放入的資料為 {目前最高的高度, 累計數量}
for(LL i=1; i<=n; i++) { // 依序檢查第 1 ~ n 棟房子
while(!st.empty() && st.top().first < hs[i]) { // 如果 st 還有資料而且 st 最後一項的高度小於第 i 棟房子
ans += st.top().second; // ans 加上 st 最後一項的累計數量
st.pop(); // 移除最後一項
}
if (!st.empty() && st.top().first == hs[i]) { // 如果 st 還有資料而且 st 最後一項的高度等於第 i 棟房子
pair<LL, LL> tmp = st.top(); st.pop(); // 暫存 st 最後一項至 tmp 並移除
if (!st.empty()) ans++; // 如果 st 還有資料 ans 加 1
ans += tmp.second; // ans 加上 tmp.second
st.push(make_pair(tmp.first, tmp.second+1)); // st 最後加上 {tmp 的高度, tmp 原來的數量加 1}
} else { // 如果 st 沒有資料或是最後一項的高度小於第 i 棟房子
if (!st.empty()) ans++; // 如果 st 還有資料 ans 加 1，因為一定能看到隔壁的房子
st.push(make_pair(hs[i], 1)); // st 最後加上 {第 i 棟房子的高度, 數量為 1}
}
}
reverse(hs.begin()+1, hs.end()); // 將 hs[1] ~ hs[n] 順序反過來，
}
cout << ans << "\n";
return 0;
}
```
## [ZeroJudge: a664. 四則運算](https://zerojudge.tw/ShowProblem?problemid=a664)
### Python 程式碼
執行時間最久約為 20 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
N = int(input()) # 要計算的算式數量
for _ in range(N): # 讀取 N 行算式
s = input() # 由標準輸入讀取算式
func = [] # 儲存算式用的串列
tmp = "" # 暫存數字的字串
for c in s: # 依序由 s 讀取字元 c
if c == '(' or c == '+' or c == '-' or c == '*' or c == '/': # 如果 c 是 (+-*/
if tmp: # 如果 tmp 有內容，將 tmp 加到 func 最後面，再清空 tmp
func.append(tmp); tmp = ""
func.append(c) # 將 c 加到 func 最後面
elif c == ')': # 如果 c 是 )
n = 0 # 暫存數值用的變數 n
if tmp: # 如果 tmp 有內容，將 tmp 加到 func 最後面，再清空 tmp
func.append(tmp); tmp = ""
while func: # 如果 func 有內容，繼續執行直到遇到 (
f = func.pop() # 取出 func 最後一項並存入 f
if func[-1] == '(': # 如果 func 目前最後一項是 (
func.pop(); func.append(f); break # 移除 (，將 f 加到 func 最後面，跳出第17行的 while 迴圈
elif f == '+': # 如果 f 是 +，取出 func 最後一項並轉成整數 t，計算 t + n 再轉成字串加到 func 最後面
t = int(func.pop()); func.append(str(t + n))
elif f == '-': # 如果 f 是 -，取出 func 最後一項並轉成整數 t，計算 t - n 再轉成字串加到 func 最後面
t = int(func.pop()); func.append(str(t - n))
elif f == '*': # 如果 f 是 *，取出 func 最後一項並轉成整數 t，計算 t * n 再轉成字串加到 func 最後面
t = int(func.pop()); func.append(str(t * n))
elif f == '/': # 如果 f 是 /，取出 func 最後一項並轉成整數 t，計算 t // n 再轉成字串加到 func 最後面
t = int(func.pop()); func.append(str(t // n))
else: # 如果 f 不是 (+-*/，則 f 是數字，轉成整數並存入 n
n = int(f)
else: # 如果 c 不是 (+-*/)，則 c 是數字，加到 tmp 最後面
tmp += c
print(func[0]) # 最後 func 只剩下一個元素，就是計算結果
```
### C++ 程式碼
一定要用 long 儲存計算結果，用 int 會溢位。執行時間最久約為 2 ms，使用記憶體最多約為 312 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
int N; cin >> N;
long n = 0, t = 0;
//stack<string> func;
string s, ss, f, tmp;
for(int i=0; i<N; i++) {
stack<string> func; ss.clear(); tmp.clear(); cin >> ss;
for(auto c : ss) {
s.assign(1, c);
if (s == "(" || s == "+" || s == "-" || s == "*" || s == "/") {
if (!tmp.empty()) {
func.push(tmp); tmp.clear();
}
func.push(s);
} else if (s == ")") {
if (!tmp.empty()) {
func.push(tmp); tmp.clear();
}
while(!func.empty()) {
f = func.top(); func.pop();
if (func.top() == "(") {
func.pop(); func.push(f); break;
} else if (f == "+") {
t = stol(func.top()); func.pop();
func.push(to_string(t + n));
} else if (f == "-") {
t = stol(func.top()); func.pop();
func.push(to_string(t - n));
} else if (f == "*") {
t = stol(func.top()); func.pop();
func.push(to_string(t * n));
} else if (f == "/") {
t = stol(func.top()); func.pop();
func.push(to_string(t / n));
} else {
n = stol(f);
}
}
} else {
tmp += s;
}
}
cout << func.top() << "\n";
}
return 0;
}
```
------
###### tags:`演算法`、`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet