Queues · learnDataStructures

Queues (FIFO)

A queue is a First-In-First-Out (FIFO) structure: the first item placed in is the first to come out. This is like a line at a store checkout — the earliest person to line up is the first one served. In its simplest form, you can imagine storing a queue inside a plain array. Adding new items is easy: you place the element at the end of the array. The trouble comes when removing from the front: to keep the “front” always at index 0, every remaining element must be shifted one position left. That makes each dequeue operation take O(n) time, which is inefficient.

A more efficient approach is to treat the array as “circular.” Instead of shifting elements, we keep two moving indices: head, pointing to the front item, and tail, pointing to where the next new item will go. When either index reaches the end of the array, it simply wraps back to the start. This way, both enqueue and dequeue take O(1) time, because we only update the indices instead of shifting the whole array. The size of the queue is tracked separately, and it tells us when the queue is empty (size = 0) or full (size = capacity).

Core functions

enqueue(x): add x at the rear of the line.
dequeue(): remove and return the item at the front.
front(): peek at the front item.
isEmpty(): true if there are no items.
size(): shows how many items are currently stored.

Complexity, Pros/Cons, and Implementations

Time complexity

Operation	Array/Circular-buffer queue	Linked-list queue	Notes
`enqueue(x)`	Amortized O(1)	O(1)	Array may occasionally resize; circular buffer avoids shifts
`dequeue()`	O(1)	O(1)	Remove from front
`front()`	O(1)	O(1)	Read front element
`isEmpty()`	O(1)	O(1)	Check if queue is empty
`size()`	O(1)	O(1)	Maintain a count

Implementations by language — how to create & use

Python

Simple circular-array queue (educational)

Best for learning: shows how wrap-around indexing avoids O(n) shifting.

class CircularQueue:
    def __init__(self, capacity=8):
        self._a = [None] * capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, x):
        if self._size == len(self._a):
            raise IndexError("queue full")
        self._a[self._tail] = x
        self._tail = (self._tail + 1) % len(self._a)
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("queue empty")
        x = self._a[self._head]
        self._a[self._head] = None
        self._head = (self._head + 1) % len(self._a)
        self._size -= 1
        return x

    def front(self):
        if self._size == 0:
            raise IndexError("queue empty")
        return self._a[self._head]

    def isEmpty(self): return self._size == 0
    def size(self):    return self._size

Linked-list queue

Best for unbounded queues: grows dynamically; no fixed capacity.

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def enqueue(self, x):
        node = Node(x)
        if self.rear:
            self.rear.next = node
        else:
            self.front = node
        self.rear = node
        self._size += 1

    def dequeue(self):
        if not self.front:
            raise IndexError("queue empty")
        x = self.front.data
        self.front = self.front.next
        if not self.front:
            self.rear = None
        self._size -= 1
        return x

    def front_item(self):
        if not self.front:
            raise IndexError("queue empty")
        return self.front.data

    def isEmpty(self): return self._size == 0
    def size(self):    return self._size

Using collections.deque (standard library)

Best for real-world use: highly optimized C implementation, O(1) for all operations.

from collections import deque

q = deque()
q.append("A")      # enqueue
q.append("B")
front_item = q[0]  # peek
x = q.popleft()    # dequeue
print(front_item, x, len(q))

Thread-safe Queue (queue.Queue)

Best for concurrency: built-in blocking semantics for producer/consumer problems.

from queue import Queue

q = Queue(maxsize=5)
q.put(10)           # enqueue
q.put(20)
print(q.get())      # dequeue (blocks if empty)
print(q.empty())    # check empty

Java

Queue via LinkedList (standard library)

Best for everyday Java: simple FIFO using the Queue interface.

import java.util.*;

public class QueueDemo {
  public static void main(String[] args) {
    Queue<String> q = new LinkedList<>(); // FIFO
    q.offer("A"); q.offer("B");
    System.out.println(q.peek()); // front
    System.out.println(q.poll()); // dequeue
    System.out.println(q.size());
  }
}

Minimal linked-list queue (educational)

Best for pointer practice: O(1) at both ends with head/tail refs.

public class LinkedQueue<T> {
  private static class Node<T> { T v; Node<T> n; Node(T v){ this.v=v; } }
  private Node<T> head, tail; private int size;

  public void enqueue(T x){
    Node<T> t = new Node<>(x);
    if (tail == null) head = tail = t;
    else { tail.n = t; tail = t; }
    size++;
  }
  public T dequeue(){
    if (size == 0) throw new java.util.NoSuchElementException();
    T v = head.v; head = head.n; if (head == null) tail = null; size--; return v;
  }
  public T front(){ if (size==0) throw new java.util.NoSuchElementException(); return head.v; }
  public boolean isEmpty(){ return size==0; }
  public int size(){ return size; }
}

Bounded, thread-safe queue (ArrayBlockingQueue)

Best for producers/consumers: blocking ops with fixed capacity.

import java.util.concurrent.*;

public class BlockingQueueDemo {
  public static void main(String[] args) throws InterruptedException {
    BlockingQueue<Integer> q = new ArrayBlockingQueue<>(3);
    q.put(1); q.put(2); q.put(3);        // blocks if full
    System.out.println(q.take());        // blocks if empty
  }
}

C++

Using std::queue (standard library)

Best for everyday C++: simple FIFO adapter with O(1) ops.

#include <iostream>
#include <queue>
int main(){
  std::queue<int> q;
  q.push(10); q.push(20); q.push(30);
  std::cout << q.front() << "\n";
  q.pop();
  std::cout << q.size() << "\n";
}

Minimal circular-buffer queue (educational)

Best for fixed-size, no heap allocations: wrap-around with head/tail.

#include <vector>
#include <cstddef>
template <typename T>
class CircularQueue {
  std::vector<T> a; std::size_t head=0, tail=0, cnt=0;
public:
  explicit CircularQueue(std::size_t cap): a(cap) {}
  bool enqueue(const T& x){
    if (cnt == a.size()) return false;
    a[tail] = x; tail = (tail + 1) % a.size(); cnt++; return true;
  }
  bool dequeue(T& out){
    if (cnt == 0) return false;
    out = a[head]; head = (head + 1) % a.size(); cnt--; return true;
  }
  const T& front() const { return a[head]; }
  bool isEmpty() const { return cnt == 0; }
  std::size_t size() const { return cnt; }
};

Minimal linked-list queue (educational)

Best for teaching nodes/pointers: dynamic size with O(1) ends.

#include <stdexcept>
template <typename T>
struct Node { T v; Node* n; Node(const T& v): v(v), n(nullptr) {} };

template <typename T>
class LinkedQueue {
  Node<T>* head=nullptr; Node<T>* tail=nullptr; std::size_t sz=0;
public:
  ~LinkedQueue(){ while(head){ auto* t=head; head=head->n; delete t; } }
  void enqueue(const T& x){
    auto* t = new Node<T>(x);
    if (tail) tail->n = t; else head = t; tail = t; ++sz;
  }
  T dequeue(){
    if (!head) throw std::runtime_error("empty");
    T v = head->v; auto* t=head; head=head->n; if(!head) tail=nullptr; delete t; --sz; return v;
  }
  const T& front() const { if(!head) throw std::runtime_error("empty"); return head->v; }
  bool isEmpty() const { return sz==0; }
  std::size_t size() const { return sz; }
};

Conceptual Questions

In a FIFO queue, which item is removed first — the newest one added or the oldest one?
In the simple array implementation, why does dequeue require shifting elements?
How does a circular array queue avoid the shifting problem that occurs in a simple array queue?
If a circular array queue has capacity 6, and after several operations the head index is 4 and the tail index is 1, how many items are currently in the queue?
If a circular array queue is completely full, what are two different strategies you could use to handle an extra enqueue? What is one trade-off of each strategy?

learnDataStructures