Queue and Deque

1
#include <iostream>
2
#include <vector>
3
#include <stdexcept>
4
5
class CircularDeque {
6
private:
7
    std::vector<int> buf;   // storage buffer
8
    int head;               // index of the first element
9
    int len;                // number of elements currently stored
10
11
    void resize_if_needed() {
12
        if (len < (int)buf.size()) return; // not full
13
        int oldC = (int)buf.size();
14
        int newC = oldC * 2;
15
        std::vector<int> nb(newC);
16
        // Copy elements in logical order to new buffer starting at 0
17
        for (int i = 0; i < len; ++i) {
18
            nb[i] = buf[(head + i) % oldC];
19
        }
20
        buf.swap(nb);
21
        head = 0; // realign to start
22
    }
23
24
public:
25
    CircularDeque(int capacity = 8) : buf(std::max(2, capacity)), head(0), len(0) {}
26
27
    bool empty() const { return len == 0; }
28
    int size() const { return len; }
29
    int capacity() const { return (int)buf.size(); }
30
31
    // Accessors
32
    int front() const {
33
        if (empty()) throw std::runtime_error("front on empty deque");
34
        return buf[head];
35
        
36
    }
37
    int back() const {
38
        if (empty()) throw std::runtime_error("back on empty deque");
39
        int C = (int)buf.size();
40
        int tailIndex = (head + len - 1 + C) % C;
41
        return buf[tailIndex];
42
    }
43
44
    // Push operations
45
    void push_front(int x) {
46
        resize_if_needed();
47
        int C = (int)buf.size();
48
        head = (head - 1 + C) % C; // move head backward with wrap-around
49
        buf[head] = x;
50
        ++len;
51
    }
52
    void push_back(int x) {
53
        resize_if_needed();
54
        int C = (int)buf.size();
55
        int tail = (head + len) % C; // position after the last element
56
        buf[tail] = x;
57
        ++len;
58
    }
59
60
    // Pop operations
61
    void pop_front() {
62
        if (empty()) throw std::runtime_error("pop_front on empty deque");
63
        int C = (int)buf.size();
64
        head = (head + 1) % C;
65
        --len;
66
    }
67
    void pop_back() {
68
        if (empty()) throw std::runtime_error("pop_back on empty deque");
69
        --len; // logical removal from the back
70
    }
71
};
72
73
int main() {
74
    CircularDeque dq(4);
75
76
    // Use as a deque
77
    dq.push_back(10);
78
    dq.push_front(5);
79
    dq.push_back(20);
80
    std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << "\n"; // 5, 20
81
82
    dq.pop_front(); // remove 5
83
    std::cout << "Front after pop_front: " << dq.front() << "\n"; // 10
84
85
    dq.push_front(7);
86
    dq.push_back(30); // may trigger resize
87
88
    // Use as a queue: only push_back and pop_front
89
    dq.push_back(40);
90
    std::cout << "Queue-like front: " << dq.front() << "\n"; // 10
91
    dq.pop_front();
92
    std::cout << "Next front: " << dq.front() << "\n"; // 20
93
94
    std::cout << "Size: " << dq.size() << ", Capacity: " << dq.capacity() << "\n";
95
    return 0;
96
}
97

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <limits>
5
6
// BFS to compute shortest distances (in edges) from a source in an unweighted graph
7
std::vector<int> bfs_shortest_distances(const std::vector<std::vector<int>>& adj, int s) {
8
    int n = (int)adj.size();
9
    const int INF = std::numeric_limits<int>::max();
10
    std::vector<int> dist(n, INF);
11
    std::queue<int> q;
12
13
    dist[s] = 0;        // mark discovered at enqueue time
14
    q.push(s);
15
16
    while (!q.empty()) {
17
        int u = q.front(); q.pop();
18
        for (int v : adj[u]) {
19
            if (dist[v] == INF) {
20
                dist[v] = dist[u] + 1;
21
                q.push(v);
22
            }
23
        }
24
    }
25
    return dist;
26
}
27
28
int main() {
29
    // Example graph (undirected)
30
    int n = 6;
31
    std::vector<std::vector<int>> adj(n);
32
    auto add_edge = [&](int u, int v){ adj[u].push_back(v); adj[v].push_back(u); };
33
    add_edge(0, 1);
34
    add_edge(0, 2);
35
    add_edge(1, 3);
36
    add_edge(2, 3);
37
    add_edge(3, 4);
38
    add_edge(4, 5);
39
40
    int source = 0;
41
    std::vector<int> dist = bfs_shortest_distances(adj, source);
42
43
    std::cout << "Distances from node " << source << ":\n";
44
    for (int i = 0; i < n; ++i) {
45
        if (dist[i] == std::numeric_limits<int>::max()) std::cout << "INF ";
46
        else std::cout << dist[i] << ' ';
47
    }
48
    std::cout << '\n';
49
    return 0;
50
}
51

1
#include <iostream>
2
#include <vector>
3
#include <deque>
4
5
// Returns maximums for each window of size k
6
std::vector<int> sliding_window_max(const std::vector<int>& a, int k) {
7
    std::deque<int> dq; // stores indices, values are nonincreasing
8
    std::vector<int> ans;
9
    for (int i = 0; i < (int)a.size(); ++i) {
10
        // 1) Evict indices that fall out of the window [i-k+1, i]
11
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
12
        // 2) Maintain decreasing deque: remove smaller values from the back
13
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
14
        // 3) Add current index
15
        dq.push_back(i);
16
        // 4) Record answer once the first window is formed
17
        if (i >= k - 1) ans.push_back(a[dq.front()]);
18
    }
19
    return ans;
20
}
21
22
int main() {
23
    std::vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
24
    int k = 3;
25
    std::vector<int> res = sliding_window_max(a, k);
26
27
    std::cout << "Window maximums: ";
28
    for (int x : res) std::cout << x << ' ';
29
    std::cout << '\n';
30
    return 0;
31
}
32

1
#include <iostream>
2
#include <vector>
3
#include <deque>
4
#include <limits>
5
#include <utility>
6
7
// Graph with edges of weight 0 or 1
8
using Edge = std::pair<int,int>; // (to, weight)
9
10
std::vector<int> zero_one_bfs(const std::vector<std::vector<Edge>>& adj, int s) {
11
    int n = (int)adj.size();
12
    const int INF = std::numeric_limits<int>::max() / 4;
13
    std::vector<int> dist(n, INF);
14
    std::deque<int> dq;
15
16
    dist[s] = 0;
17
    dq.push_front(s);
18
19
    while (!dq.empty()) {
20
        int u = dq.front(); dq.pop_front();
21
        for (auto [v, w] : adj[u]) {
22
            int nd = dist[u] + w; // w is 0 or 1
23
            if (nd < dist[v]) {
24
                dist[v] = nd;
25
                if (w == 0) dq.push_front(v); // free move: process sooner
26
                else dq.push_back(v);          // cost-1 move: process later
27
            }
28
        }
29
    }
30
    return dist;
31
}
32
33
int main() {
34
    int n = 5;
35
    std::vector<std::vector<Edge>> adj(n);
36
    auto add = [&](int u, int v, int w){ adj[u].push_back({v, w}); };
37
    // Example directed graph with 0/1 weights
38
    add(0, 1, 0); add(0, 2, 1);
39
    add(1, 2, 0); add(1, 3, 1);
40
    add(2, 3, 0); add(3, 4, 1);
41
    add(1, 4, 1);
42
43
    int s = 0;
44
    std::vector<int> d = zero_one_bfs(adj, s);
45
46
    std::cout << "Distances from " << s << ":\n";
47
    for (int i = 0; i < n; ++i) {
48
        if (d[i] >= std::numeric_limits<int>::max()/8) std::cout << "INF ";
49
        else std::cout << d[i] << ' ';
50
    }
51
    std::cout << '\n';
52
    return 0;
53
}
54