Queue (Antrean)

1from collections import deque2
3queue = deque()4
5# Enqueue three values at the rear6for value in [3, 7, 5]:7    queue.append(value)8    print(f"enqueue {value} -> {list(queue)}")9
10# Dequeue them from the front: first in, first out11while queue:12    value = queue.popleft()13    print(f"dequeue {value} -> {list(queue)}")14
15print("empty:", len(queue) == 0)

1// A plain array makes dequeue O(n): shift() moves every element left.2// Track a head index instead, the fix the queue article describes.3const queue = { items: [], head: 0 };4
5function enqueue(value) {6    queue.items.push(value);7}8
9function dequeue() {10    const value = queue.items[queue.head];11    queue.items[queue.head] = undefined; // free the slot12    queue.head += 1;13    // Reclaim space once the consumed prefix dominates.14    if (queue.head * 2 >= queue.items.length) {15        queue.items = queue.items.slice(queue.head);16        queue.head = 0;17    }18    return value;19}20
21const size = () => queue.items.length - queue.head;22
23for (const value of [3, 7, 5]) {24    enqueue(value);25    console.log(`enqueue ${value} -> size ${size()}`);26}27
28// Dequeue from the front: first in, first out, amortized O(1)29while (size() > 0) {30    console.log(`dequeue ${dequeue()} -> size ${size()}`);31}32
33console.log('empty:', size() === 0);

1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5    public static void main(String[] args) {6        Queue<Integer> queue = new ArrayDeque<>();7
8        // Enqueue three values at the rear9        for (int value : new int[] {3, 7, 5}) {10            queue.add(value);11            System.out.println("enqueue " + value + " -> " + queue);12        }13
14        // Dequeue them from the front: first in, first out15        while (!queue.isEmpty()) {16            int value = queue.remove();17            System.out.println("dequeue " + value + " -> " + queue);18        }19
20        System.out.println("empty: " + queue.isEmpty());21    }22}

1#include <iostream>2#include <queue>3
4int main() {5    std::queue<int> queue;6
7    // Enqueue three values at the rear8    for (int value : {3, 7, 5}) {9        queue.push(value);10        std::cout << "enqueue " << value << " -> size " << queue.size() << "\n";11    }12
13    // Dequeue them from the front: first in, first out14    while (!queue.empty()) {15        int value = queue.front();16        queue.pop();17        std::cout << "dequeue " << value << " -> size " << queue.size() << "\n";18    }19
20    std::cout << "empty: " << std::boolalpha << queue.empty() << "\n";21    return 0;22}

1#include <stdio.h>2
3#define CAP 164
5int queue[CAP];6int front = 0;7int rear = 0; /* index of the next free slot */8
9int main(void) {10    int values[3] = {3, 7, 5};11
12    /* Enqueue three values at the rear */13    for (int i = 0; i < 3; i++) {14        queue[rear++] = values[i];15        printf("enqueue %d -> size %d\n", values[i], rear - front);16    }17
18    /* Dequeue them from the front: first in, first out */19    while (front < rear) {20        int value = queue[front++];21        printf("dequeue %d -> size %d\n", value, rear - front);22    }23
24    printf("empty: %d\n", front == rear);25    return 0;26}