04 Stacks and Queues

The shared idea: access rules

Stacks and queues are abstract data types (ADTs): they describe how data may be accessed and which operations are supported, while leaving the internal representation open. The same access behavior can be built with an array, a linked list, or another structure.

The central distinction is the order in which items leave:

• A stack uses last-in, first-out (LIFO) order.

• A queue uses first-in, first-out (FIFO) order.

This distinction determines which data structure fits a problem. Choose a stack when the newest item should be handled first; choose a queue when items should be handled in arrival order.

Takeaway: A stack or queue is defined by its access rule, not by whether it is implemented with an array or a linked list.

Stacks: one end, newest item first

A stack has one active end, called the top. Both insertion and removal happen there.

Core operations

• push(x) adds x to the top.

• pop() removes and returns the top item.

• peek() or top() returns the top item without removing it.

• isEmpty() tests whether the stack contains no items.

For example, starting empty, pushing A, then B, then C produces a stack whose top is C. The first pop() returns C, and the next returns B. The newest item leaves first because the stack follows LIFO order.

A pop() or peek() on an empty stack causes underflow. If a fixed-capacity array is used, trying to push when the array is full causes overflow, unless the implementation can resize the array.

Performance

With appropriate management of the top, push, pop, and peek each take $O(1)$ time when capacity is available. A dynamically growing array may need to copy $n$ elements during one resize, making that individual insertion take $O(n)$ time. With geometric resizing, the average cost over a long sequence of insertions is amortized $O(1)$ per insertion.

Takeaway: A stack exposes one end and supports constant-time basic operations, apart from occasional array-resizing work.

Queues: two ends, earliest item first

A queue has two active ends: insertion occurs at the rear, or tail, and removal occurs at the front, or head.

Core operations

• enqueue(x) adds x at the rear.

• dequeue() removes and returns the front item.

• front() or peek() returns the front item without removing it.

• isEmpty() tests whether the queue contains no items.

For example, after enqueuing A, B, and C, the first dequeue() returns A, followed by B. The earliest arrival leaves first because the queue follows FIFO order.

A dequeue() or front() on an empty queue causes underflow. In a bounded queue, inserting into a full structure causes overflow or may require the operation to wait, depending on the design.

A queue is not always strictly FIFO in every related structure. A priority queue removes the item with the highest priority, while a deque permits insertion and removal at both ends. A deque can therefore support either stack-like or queue-like behavior.

Takeaway: A queue separates the insertion end from the removal end so that waiting items are processed in arrival order.

Implementations and efficiency

The implementation must preserve the access rule while keeping the important operations efficient.

Array-based stacks

An array-based stack commonly stores the number of elements in size. The next pushed element is placed at array[size], and size increases. To pop, the implementation decreases size and returns the element at the new last occupied position. This uses contiguous storage and generally provides good cache locality.

Linked-list stacks

A linked-list stack stores a value and a reference in each node. The top reference points to the first node. A push creates a node whose next reference points to the old top; a pop moves the top reference to the next node. Both operations take $O(1)$ time, but each node requires link storage and may be allocated separately.

Circular-array queues

A naive array queue shifts every remaining element left after each dequeue, making removal take $O(n)$ time. A circular array avoids this shifting. It maintains:

• front, the position of the next item to remove;

• rear, the position where the next item will be inserted;

• size, the number of stored items.

After an operation reaches the physical end of the array, its index wraps to the beginning. Enqueue, dequeue, and front can then take $O(1)$ time when resizing is not required.

Linked-list queues

A linked-list queue should maintain both a front reference and a rear reference. Enqueue adds a node at the rear, while dequeue removes a node at the front. Both operations take $O(1)$ time. After the final item is dequeued, both references must be set to null; otherwise the empty queue may retain an invalid rear reference.

Takeaway: Correct end references are the key to constant-time operations: one top reference for a stack, and both front and rear references for a linked-list queue.

Applications and design choice

The access rule makes each structure useful for different patterns of work.

Where stacks fit

• Function calls and recursion: A call stack stores return information, parameters, and local variables. A new call pushes an activation record; returning pops it.

• Undo and redo: The latest user action is pushed onto an undo stack. Undo removes the latest action, and a second stack can support redo.

• Expression processing: Compilers and calculators use stacks for postfix evaluation and for managing operators and parentheses.

• Backtracking: A maze solver or depth-first search can push choices and restore the most recent choice when a path fails.

• Syntax matching: Opening parentheses or brackets can be pushed and matched when their corresponding closing symbols appear.

Where queues fit

• Printer spooling: Documents wait in submission order.

• Task scheduling: A system can process waiting tasks in FIFO order.

• Breadth-first search: Discovered vertices are enqueued and explored level by level.

• Buffers: Keyboard input, network packets, and streaming data can wait while production and consumption occur at different rates.

• Event handling: User or system events can be processed sequentially.

Choosing between them

Ask which item should be processed next:

• If it is the most recent item, use a stack.

• If it is the earliest waiting item, use a queue.

The choice is independent of the representation. Both structures can be implemented efficiently with arrays or linked lists when their active ends are managed correctly.

Final takeaway: Stacks organize nested, reversible, or backtracking work; queues organize waiting work that should proceed in arrival order.

• abstract data type (ADT)