QueuesLesson 2

Implementing a Queue

Build a queue using an array and using a linked list. Understand the problem of wasted space and how to handle it.

What Is It?

Now that you know what a queue does, let's build one. There are two classic ways to implement it:

Array-based queue — use an array with a front index and a rear index. Simple, but has a wasted-space problem we'll look at.
Linked-list-based queue — use a chain of nodes with a head pointer at the front and a tail pointer at the back. Both enqueue and dequeue are fast.

Both give you fast enqueue and dequeue. The main difference is how they handle space.

Analogy

Array-based queue: Imagine a row of 10 numbered chairs in a waiting room. The first patient sits in chair 0, the next in chair 1, and so on. When chair 0's patient is called, that chair stays empty — no one scoots forward. Over time, the front of the line moves to the right, leaving empty chairs behind that no one can use. Eventually new patients cannot sit down even though there are empty chairs at the front. That is the wasted-space problem.

Linked-list-based queue: Now imagine people standing in a freeform line instead of chairs. The receptionist knows who is at the front and who is at the back. When someone joins, they stand at the back. When the front person is called, they leave and the next person becomes the front. No seats are wasted.

How It Works

Implementation 1: Array-Based Queue

We use an array and two numbers:

front — the index of the element at the front of the queue
rear — the index where the NEXT element will be placed
count — how many elements are currently in the queue

pseudocode

structure ArrayQueue:
    array = new array of size CAPACITY
    front = 0
    rear = 0
    count = 0

#### Full Pseudocode

pseudocode

function enqueue(queue, value):
    if queue.count equals CAPACITY:
        error("Queue is full")
    queue.array[queue.rear] = value
    queue.rear = queue.rear + 1
    queue.count = queue.count + 1
function dequeue(queue):
    if queue.count equals 0:
        error("Queue is empty")
    value = queue.array[queue.front]
    queue.front = queue.front + 1
    queue.count = queue.count - 1
    return value
function peek(queue):
    if queue.count equals 0:
        error("Queue is empty")
    return queue.array[queue.front]
function isEmpty(queue):
    return queue.count equals 0

#### Tracing Through Operations

pseudocode

Capacity = 6
Operation       front  rear  count  Array Contents
---------       -----  ----  -----  -----------------------------------------
(initial)         0     0     0     [ _ ][ _ ][ _ ][ _ ][ _ ][ _ ]
enqueue(10)       0     1     1     [10][ _ ][ _ ][ _ ][ _ ][ _ ]
enqueue(20)       0     2     2     [10][20][ _ ][ _ ][ _ ][ _ ]
enqueue(30)       0     3     3     [10][20][30][ _ ][ _ ][ _ ]
dequeue()->10     1     3     2     [  ][20][30][ _ ][ _ ][ _ ]
dequeue()->20     2     3     1     [  ][  ][30][ _ ][ _ ][ _ ]
enqueue(40)       2     4     2     [  ][  ][30][40][ _ ][ _ ]
enqueue(50)       2     5     3     [  ][  ][30][40][50][ _ ]
enqueue(60)       2     6     4     [  ][  ][30][40][50][60]

#### The Wasted Space Problem

Look at the last line above. Slots 0 and 1 are empty — we already dequeued those values. But rear has moved all the way to index 6, which is the end of the array. If we try to enqueue one more value, it fails with "Queue is full" even though two slots are sitting there empty.

pseudocode

[  ][  ][30][40][50][60]
          ^              ^--- rear is at the end, can't go further
          front is here

Those two empty slots at the front can never be reused in this simple version. Two fixes:

Shift everything left after each dequeue — works, but is slow (every shift touches all elements).
Use a circular queue — the elegant fix, covered in the next lesson.

Understanding this flaw is important because the circular queue builds directly on top of it.

Implementation 2: Linked-List-Based Queue

We use a chain of nodes. Each node holds a value and a pointer to the next node. We keep two pointers on the queue itself:

head points to the front (where dequeue removes from)
tail points to the back (where enqueue adds to)

Both enqueue and dequeue are fast — just one or two pointer updates.

pseudocode

structure Node:
    data
    next
structure LinkedQueue:
    head = null
    tail = null
    count = 0

Visualization:

Linked-List Queue— head (front) and tail (rear) pointers

head

tail

Dequeue removes from head (front). Enqueue adds after tail (rear). Both O(1).

#### Full Pseudocode

pseudocode

function enqueue(queue, value):
    newNode = new Node(value)
    if queue.tail is null:
        // Queue is empty — new node is both head and tail
        queue.head = newNode
        queue.tail = newNode
    else:
        queue.tail.next = newNode    // attach after current tail
        queue.tail = newNode         // update tail pointer
    queue.count = queue.count + 1
function dequeue(queue):
    if queue.head is null:
        error("Queue is empty")
    value = queue.head.data
    queue.head = queue.head.next
    if queue.head is null:
        // Queue became empty — reset tail too
        queue.tail = null
    queue.count = queue.count - 1
    return value
function peek(queue):
    if queue.head is null:
        error("Queue is empty")
    return queue.head.data
function isEmpty(queue):
    return queue.head is null

#### Tracing Through Operations

pseudocode

Operation        Head chain                         Return
---------        ----------                         ------
(initial)        null
enqueue(10)      [10|null]
                  ^head/tail
enqueue(20)      [10|*]-->[20|null]
                  ^head     ^tail
enqueue(30)      [10|*]-->[20|*]-->[30|null]
                  ^head              ^tail
dequeue()        [20|*]-->[30|null]                  10
                  ^head     ^tail
enqueue(40)      [20|*]-->[30|*]-->[40|null]
                  ^head              ^tail
dequeue()        [30|*]-->[40|null]                  20
                  ^head     ^tail
dequeue()        [40|null]                           30
                  ^head/tail
dequeue()        null                                40
                  head=null, tail=null

#### Why Dequeue Is Fast

Dequeue removes from the head. In a linked list, removing the head is just one pointer update:

pseudocode

head = head.next

That is fast no matter how long the list is.

#### Why Enqueue Is Fast

Because we keep a tail pointer. Without it, enqueue would be slow — you would have to walk the entire list to find the last node every time. With tail, you jump straight to the end:

pseudocode

tail.next = newNode
tail = newNode

Two pointer updates, done. The tail pointer is what makes this work.

#### Watch Out: The Queue-Becomes-Empty Edge Case

When you dequeue the last element, head becomes null. But tail still points to that removed node. You must also set tail = null. Forgetting this causes subtle bugs later.

Comparison: Array vs. Linked List

Array-Based Queue

enqueue / dequeue: O(1)
Fixed capacity (or circular)
Some wasted space as front moves
No extra memory per element
Good cache performance

contiguous memory, fixed capacity

Linked-List Queue

enqueue / dequeue: O(1)
Dynamic, unlimited capacity
No wasted space
One pointer per node overhead
Poor cache performance

scattered nodes, dynamic

When to choose array-based: When you know the maximum size ahead of time. Use the circular queue version (next lesson) to fix the wasted-space problem.

When to choose linked-list-based: When the queue size is unpredictable and you want it to grow freely.

Examples

Example 1: BFS Using a Linked Queue

pseudocode

function bfs(graph, startNode):
    queue = new LinkedQueue()
    visited = empty set
    enqueue(queue, startNode)
    add startNode to visited
    while not isEmpty(queue):
        node = dequeue(queue)
        process(node)
        for each neighbor of node in graph:
            if neighbor is not in visited:
                add neighbor to visited
                enqueue(queue, neighbor)

Example 2: Simulating a Printer Queue

pseudocode

printerQueue = new LinkedQueue()
enqueue(printerQueue, "Report.pdf")
enqueue(printerQueue, "Photo.jpg")
enqueue(printerQueue, "Letter.docx")
while not isEmpty(printerQueue):
    doc = dequeue(printerQueue)
    print(doc)    // prints Report.pdf, then Photo.jpg, then Letter.docx

Common Mistakes

1. Forgetting to reset tail when the queue becomes empty. After dequeuing the last element, head becomes null but tail still points at the removed node. Always set tail = null when head becomes null.

2. Missing the wasted-space problem in array queues. The array fills up even with empty slots at the front. Use a circular queue to fix this.

3. Not keeping a tail pointer. Without tail, enqueue is slow because you have to walk the whole list every time.

4. Enqueuing at the wrong end. Enqueue at the tail, dequeue at the head. Reversing this makes dequeue slow.

Best Practices

Always keep both head and tail pointers. This is what makes both enqueue and dequeue fast.

Use the circular queue for array-based implementations. It solves the wasted-space problem with very little extra code. We cover it next.

Track count separately. Keep an explicit count variable instead of computing it from head and tail.

Handle the empty-queue edge case explicitly. When you dequeue the last element, reset both head and tail to null.

Runnable Code

Here is a complete JavaScript queue implementation you can run. It includes enqueue, dequeue, front, isEmpty, and size operations.

Queue — Full Implementation

class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(item) {
    this.items.push(item);
  }
  dequeue() {
    if (this.isEmpty()) return 'Queue is empty';
    return this.items.shift();
  }
  front() {
    if (this.isEmpty()) return 'Queue is empty';
    return this.items[0];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
  print() {
    console.log('Queue (front -> back):', this.items.join(', '));
  }
}
// --- Demo ---
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log('After enqueue 10, 20, 30:');
queue.print();
console.log('Front:', queue.front());
console.log('Dequeue:', queue.dequeue());
console.log('Dequeue:', queue.dequeue());
console.log('After two dequeues:');
queue.print();
console.log('Size:', queue.size());
// Simulate a printer queue
console.log('\n--- Printer Queue Simulation ---');
const printer = new Queue();
printer.enqueue('Report.pdf');
printer.enqueue('Photo.jpg');
printer.enqueue('Letter.docx');
while (!printer.isEmpty()) {
  console.log('Printing:', printer.dequeue());
}

How Queues Work Circular Queues and Deques