---
# System prepended metadata

title: 0-19 queue 與 stack
tags: [演算法, C++, APCS, Python]

---

# 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++`