Implementing a Queue: Built-In Queues & Deque per Language

A queue needs O(1) at both ends — add at the rear, remove at the front. The naive approach (a plain array where you shift() the front off) is O(n) per dequeue because every remaining element slides down. This page shows the idiomatic, O(1) built-in queue in each language, then a from-scratch two-pointer version so you understand how the O(1) front-removal is achieved. For the FIFO concept first, see the queues introduction.

The built-in queue (use this)

Each language ships a structure with true O(1) enqueue/dequeue. Reach for these by default.

#include <queue>
std::queue<int> q;       // backed by std::deque
q.push(10);              // enqueue at rear
q.push(20);
int f = q.front();       // 10 (peek front)
q.pop();                 // dequeue 10 (returns void)
bool e = q.empty();
int n = q.size();

import java.util.*;
// ArrayDeque is the fastest general-purpose queue in Java.
Queue<Integer> q = new ArrayDeque<>();
q.offer(10);             // enqueue at rear
q.offer(20);
int f = q.peek();        // 10 (peek front, null if empty)
q.poll();                // dequeue and return 10 (null if empty)
boolean e = q.isEmpty();
int n = q.size();

// JS has no built-in queue. A plain array works but shift() is O(n).
// Use a two-pointer wrapper for true O(1) dequeue (shown below).
const q = [];
q.push(10);              // enqueue
q.push(20);
const f = q[0];          // 10 (peek)
q.shift();               // dequeue — O(n)! fine for small inputs

from collections import deque
q = deque()              # NOT a list — list.pop(0) is O(n)
q.append(10)             # enqueue at rear
q.append(20)
f = q[0]                 # 10 (peek front)
q.popleft()              # dequeue and return 10 — O(1)
e = not q
n = len(q)

The #1 queue mistake: using a list/array and removing from the front. list.pop(0) in Python and array.shift() in JS are O(n). Use collections.deque in Python, ArrayDeque in Java, and a two-pointer or circular buffer in JS.

A from-scratch O(1) queue (two pointers)

How do the built-ins get O(1) front removal? They never physically shift elements — they track a head index that advances on dequeue. Here is the idea using a growable array plus a head pointer.

#include <vector>
#include <stdexcept>
class Queue {
    std::vector<int> data;
    size_t head = 0;            // index of the front element
public:
    void enqueue(int x) { data.push_back(x); }
    int dequeue() {
        if (head >= data.size()) throw std::out_of_range("dequeue from empty queue");
        int x = data[head++];
        if (head > data.size() / 2) {       // compact occasionally
            data.erase(data.begin(), data.begin() + head);
            head = 0;
        }
        return x;
    }
    int front() const { return data[head]; }
    bool empty() const { return head >= data.size(); }
    int size() const { return (int)data.size() - (int)head; }
};

import java.util.*;
class Queue {
    private List<Integer> data = new ArrayList<>();
    private int head = 0;                    // index of the front element
    public void enqueue(int x) { data.add(x); }
    public int dequeue() {
        if (head >= data.size()) throw new NoSuchElementException("empty queue");
        int x = data.get(head++);
        if (head > data.size() / 2) {        // compact occasionally
            data = new ArrayList<>(data.subList(head, data.size()));
            head = 0;
        }
        return x;
    }
    public int front() { return data.get(head); }
    public boolean isEmpty() { return head >= data.size(); }
    public int size() { return data.size() - head; }
}

class Queue {
  constructor() { this.data = []; this.head = 0; }
  enqueue(x) { this.data.push(x); }
  dequeue() {
    if (this.head >= this.data.length) throw new Error("empty queue");
    const x = this.data[this.head++];
    if (this.head > this.data.length >> 1) {   // compact occasionally
      this.data = this.data.slice(this.head);
      this.head = 0;
    }
    return x;
  }
  front() { return this.data[this.head]; }
  isEmpty() { return this.head >= this.data.length; }
  size() { return this.data.length - this.head; }
}

class Queue:
    def __init__(self):
        self._data = []
        self._head = 0              # index of the front element
    def enqueue(self, x):
        self._data.append(x)
    def dequeue(self):
        if self._head >= len(self._data):
            raise IndexError("dequeue from empty queue")
        x = self._data[self._head]
        self._head += 1
        if self._head > len(self._data) // 2:   # compact occasionally
            self._data = self._data[self._head:]
            self._head = 0
        return x
    def front(self):
        return self._data[self._head]
    def is_empty(self):
        return self._head >= len(self._data)
    def size(self):
        return len(self._data) - self._head

Advancing head makes dequeue amortized O(1); the periodic compaction stops the array from growing forever after many dequeues. A circular queue achieves the same with a fixed-size buffer and no compaction.

Choosing an implementation

Approach              enqueue   dequeue        notes
Built-in deque        O(1)      O(1)           use this by default
Two-pointer array     O(1)      O(1) amortized teaches the mechanism
Circular buffer       O(1)      O(1)           fixed capacity, no GC churn
Plain array + shift   O(1)      O(n)           AVOID for large inputs
Linked list (head/tail) O(1)    O(1)           per-node pointer overhead

Interview tip: When asked to “implement a queue,” the cleanest answers are a two-pointer array (above) or two stacks. Mention that ArrayDeque/collections.deque is what you’d ship.

Next: see how a circular queue reuses fixed memory, or how a deque generalizes both ends.