Array-Backed Stack and Queue

Description

Library stacks and queues grow on demand, but many systems need fixed memory and no allocation: audio buffers, network packet queues, embedded code. Building a stack or queue on a plain array is simple - except that a queue's front keeps moving, and without wrapping around, the freed space at the start is lost.

This skill builds a stack and a queue on a plain array. A stack needs one index. A queue becomes a ring with a front index and a count, so freed slots are reused. A deque adds stepping backwards safely. These are the building blocks of every fixed-memory buffer.

We'll go from simple to more technical:

1. The pattern: a stack with one index, and a queue as a ring wrapped with modulo.
2. A second flavor: a circular deque, where stepping the front backwards needs care.
3. Where ring buffers run (audio, network rings, last-N logs, lock-free queues).
4. What breaks it: no wrap-around, full versus empty, negative modulo, ambiguous empty markers.

The approach

// Stack: one index
int[] a = new int[capacity];
int top = -1;                                      // -1 = empty
void push(int x) { a[++top] = x; }
int pop()        { return top == -1 ? -1 : a[top--]; }

// Queue: a front index and a count, wrapped with modulo
int front = 0, count = 0;
void enqueue(int x) { a[(front + count) % a.length] = x; count++; }
int dequeue() {
    if (count == 0) return -1;
    int v = a[front];
    front = (front + 1) % a.length;                // wrap: slot 0 follows the last slot
    count--;
    return v;
}

# Stack: one index
a = [0] * capacity                                 # preallocated: the point is fixed memory
top = -1                                           # -1 = empty


def push(x: int) -> None:
    global top
    top += 1
    a[top] = x


def pop() -> int:
    global top
    if top == -1:
        return -1
    top -= 1
    return a[top + 1]


# Queue: a front index and a count, wrapped with modulo
front = count = 0


def enqueue(x: int) -> None:
    global count
    a[(front + count) % len(a)] = x
    count += 1


def dequeue() -> int:
    global front, count
    if count == 0:
        return -1
    v = a[front]
    front = (front + 1) % len(a)                   # wrap: slot 0 follows the last slot
    count -= 1
    return v

The modulo turns the array into a ring, so slots freed at the front are reused at the back - the queue can run forever in fixed memory. The count distinguishes full from empty: with only front and rear indices, both states can look like "front == rear", which is why some implementations waste one slot on purpose instead. Returning -1 for "empty" is safe only when -1 can never be stored; here values are 0 to 10^9.

A second flavor: a circular deque

A deque adds and removes at both ends. Stepping the front backwards needs care, because Java's % keeps the sign of its left operand: (0 - 1) % 5 is -1, an invalid index. (Python's % takes the divisor's sign, so there (0 - 1) % 5 is already 4.)

boolean insertFront(int value) {
    if (size == a.length) return false;
    front = (front - 1 + a.length) % a.length;     // add the capacity before taking the remainder
    a[front] = value;
    size++;
    return true;
}
int getRear() { return size == 0 ? -1 : a[(front + size - 1) % a.length]; }

def insert_front(self, value: int) -> bool:
    if self.size == len(self.a):
        return False
    self.front = (self.front - 1) % len(self.a)    # Python's % is never negative for a positive divisor
    self.a[self.front] = value
    self.size += 1
    return True


def get_rear(self) -> int:
    return -1 if self.size == 0 else self.a[(self.front + self.size - 1) % len(self.a)]

Every index is derived from front and size, so the four operations stay O(1). Math.floorMod(front - 1, a.length) does the same as adding the capacity first.

Where you'll see it

Ring buffers are everywhere in systems code: audio and video buffers, network card receive rings, logging buffers that keep the last N lines, and lock-free queues such as the LMAX Disruptor, which requires a power-of-two size so it can wrap with index & (size - 1) instead of a division. Java's own ArrayDeque is a resizable circular array; Python's collections.deque is a linked list of fixed-size blocks instead - O(1) at both ends, O(n) to index the middle.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does an array queue wrap its indices with % capacity?

2. How do you tell a full ring buffer from an empty one?

3. What's wrong with front = (front - 1) % capacity in a deque's insertFront?

Key takeaways

• Stack: one index starting at -1. Queue: front plus count, wrapped with %.
• A count tells full from empty.
• Step backwards with (i - 1 + n) % n; Java's % can be negative.
• An "empty" return value must not be a storable value.