Introduction

有了動態陣列之後，堆疊與佇列就可以被實作出來了。堆疊的基本概念是先進去的後出來，就像疊好的盤子。佇列則相反，先進去的會先出來，就像一群在排隊的人。

Queue

接著我們來實作佇列，你會發現，這次我們要利用resize。如果佇列沒有內容物而要求輸出front()，請輸出-1。如果佇列內沒有任何元素，請跳過指令。因為想要有效的利用空間，所以我們會使用環形陣列的方式儲存資料。

Template for your program

// push back, pop front, and get front
#include <iostream>
#include <vector>
// [l, r)
struct Queue {
    Queue(): sz(0), l(0), r(0), capacity(0) {}
    std::vector<int> values;
    int l, r, sz, capacity;
    void set_capacity(int new_capacity);
    Queue& push(int val);
    Queue& pop();
    int front();
    int size() { return sz; }
};

void Queue::set_capacity(int new_capacity) {
    // Your code below
    
    // Your code above
}

Queue& Queue::push(int val) {
    // Your code below
    
    // Your code above
    return *this;
}

Queue& Queue::pop() {
    // Your code below
    
    // Your code above
    return *this;
}

int Queue::front() {
    // Your code below

    // Your code above
}

const int PUSH{1};
const int POP{2};
const int FRONT{3};

int main(void) {
    std::ios::sync_with_stdio(0);std::cin.tie(0);
    int operation_num;
    std::cin >> operation_num;

    Queue st;
    for (int i{0}; i < operation_num; ++i) {
        int op, value;
        std::cin >> op;
        switch (op) {
        case PUSH:
            std::cin >> value;
            st.push(value);
            std::cout << st.size() << "\n";
            break;
        case POP:
            st.pop();
            break;
        case FRONT:
            std::cout << st.front() << "\n";
            break;
        }
    }
}

Usage of Queue

BFS(CSES)

你有一個迷宮的地圖，任務是找到從起點到終點的路徑。你可以向左、向右、向上、或向下移動。

Input

第一行有兩個整數 \(n\) 和 \(m\)，分別代表地圖的高度和寬度。接著有 \(n\) 行，每行包含 \(m\) 個字元，描述迷宮。每個字元可以是以下其中之一：

. (地板)
# (牆壁)
A (起點)
B (終點)

輸入中恰好有一個 A 和一個 B。

Output

首先輸出 “YES”（如果存在路徑），否則輸出 “NO”。
如果存在路徑，輸出最短路徑的長度，並輸出該路徑的描述，該描述為由以下字符組成的字串：

L (左)
R (右)
U (上)
D (下)

你可以輸出任意有效解。

Constraint

\(1 \leq n, m \leq 1000\)

Samples

Sample Input 1

5 8
########
#.A#...#
#.##.#B#
#......#
########

Sample Output 1

1
2
3

YES
9
LDDRRRRRU

Solution

#include<bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops,fast-math")
using namespace std;
 
//   3
// 2   0 
//   1
const int dx[4]{1,0,-1,0},dy[4]{0,-1,0,1};
map<int,char> toc{{0,'R'},{1,'U'},{2,'L'},{3,'D'}};
map<char,int> toi{{'R',0},{'U',1},{'L',2},{'D',3}};
 
struct info{
    int r,c;
    info(int _r,int _c){
        r=_r; c=_c;
    }
};
 
 
int n,m;
vector<string> mp,tp,pre;
string ans;
 
info bfs(int r,int c){
    queue<info> q;
    q.emplace(r,c);
    while(!q.empty()){
        info now=q.front();
        q.pop();
 
        if(tp[now.r][now.c]=='B'){
            return info(now.r,now.c);
        }
 
        for(int i=0;i<4;i++){
            int px=now.c+dx[i],py=now.r+dy[i];
            if(px>=0 && py>=0 && px<m && py<n){
                if(mp[py][px]!='#'){
                    mp[py][px]='#';
                    pre[py][px]=toc[i];
                    q.emplace(py,px);
                }
            }
        }
    }
    return info(-1,-1);
}
 
void solve(){
    mp.clear();
    cin>>n>>m;
 
    for(int i=0;i<n;i++){
        string line;
        cin>>line;
        mp.emplace_back(line);
    }
    tp=pre=mp;
 
    info pos(-1,-1),st(0,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='A'){
                pos=bfs(i,j);
                st=info(i,j);
                break;
            }
        }
    }
 
    if(pos.r!=-1){
        cout<<"YES"<<"\n";
        while(pos.r!=st.r || pos.c!=st.c){
            ans+=pre[pos.r][pos.c];
            int p=toi[pre[pos.r][pos.c]];
            pos.r-=dy[p];
            pos.c-=dx[p];
        }
        reverse(ans.begin(),ans.end());
        cout<<ans.size()<<"\n"<<ans<<"\n";
    }else{
        cout<<"NO"<<"\n";
    }
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    // freopen("test_input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
 
    int t=1;
    while(t--){
        solve();
    }
}

Home but not work

雙端佇列(Deque)
模擬廣度優先遞迴
隱式圖BFS

mtmatt.Page

Stack and Queue (Part 2)