5 Stacks and Queues

Stack behavior and operations

A stack is a linear abstract data type whose removal rule is last in, first out (LIFO). If A, B, and C are pushed in that order, C is removed first, followed by B, then A.

The core operations are:

• push(x): insert x at the top.

• pop(): remove and return the top element.

• peek() or top(): inspect the top element without removing it.

• isEmpty(): test whether the structure has no elements.

• size(): return the number of elements.

Removing from or inspecting an empty stack causes underflow. A fixed-capacity array stack can also experience overflow when an insertion is attempted after the array is full.

Takeaway: choose a stack when the newest pending item should be handled first, such as in undo histories, nested operations, parsing, or backtracking.

Queue behavior and operations

A queue ordinarily follows first in, first out (FIFO). If A, B, and C are enqueued in that order, A is removed first, followed by B, then C. New elements enter at the rear, and removals occur at the front.

The core operations are:

• enqueue(x): insert x at the rear.

• dequeue(): remove and return the front element.

• front() or peek(): inspect the front element without removing it.

• isEmpty(): test whether the structure has no elements.

• size(): return the number of elements.

An empty queue produces underflow when a removal or inspection is attempted. A bounded queue may also report overflow when it has no unused capacity.

A queue is appropriate when older work should be served before newer work, including print jobs, processor tasks, packets, and requests waiting for service.

Takeaway: the removal rule distinguishes the structures: a stack favors the newest item, while a queue ordinarily favors the oldest item.

Array implementations and circular storage

An array-based stack stores elements near one end of an array and maintains a top position. If top denotes the next unused position, insertion writes at items[top] and then increments top; removal decrements top and returns the element at the new position.

With sufficient capacity, push, pop, and peek each take $O(1)$ time. A dynamic array may occasionally resize by allocating a larger array and copying existing elements. One resize can take $O(n)$ time, but geometric growth makes a long sequence of insertions amortized O(1) per insertion. Storing $n$ elements requires $O(n)$ space.

A naive array queue removes the front element by shifting every remaining element toward the front. That makes one dequeue take $O(n)$ time. The usual improvement is a circular buffer: maintain a front index, a rear index, and a size count, and advance each index using modular wraparound.

With a fixed-capacity circular buffer, enqueue, dequeue, and peek take $O(1)$ time. Dynamic growth can make an individual insertion expensive, but repeated insertions remain amortized constant time. The queue uses $O(n)$ space.

Takeaway: arrays give compact storage and good locality, but queues must avoid shifting elements after every dequeue.

Linked-list implementations

A linked-list implementation stores each element in a node containing a value and one or more links. Nodes do not need to occupy adjacent memory locations.

For a linked-list stack, the list head serves as the top. A push creates a node, links it before the current head, and updates the head. A pop removes the head and advances the pointer. Therefore, push, pop, and peek each take $O(1)$ time.

For a linked-list queue, maintain both a front pointer and a rear pointer. Enqueueing attaches a new node after the rear and moves the rear pointer. Dequeueing removes the front node and advances the front pointer. When the queue becomes empty, both pointers must be reset appropriately. With both endpoint pointers, enqueue, dequeue, and peek take $O(1)$ time.

If a singly linked queue omits its rear pointer, finding the insertion point requires traversal, making enqueue take $O(n)$ time. Linked structures use $O(n)$ space but include node and pointer overhead.

Takeaway: linked lists grow one node at a time, while endpoint pointers are essential for constant-time queue operations.

Complexity and implementation trade-offs

The abstract data type specifies behavior, while the implementation determines how that behavior is achieved and what it costs.

For a well-designed stack or queue:

• Primary insertion, removal, and next-element inspection operations should take $O(1)$ time.

• isEmpty and size take $O(1)$ time when a size counter is maintained.

• Traversing all stored elements takes $O(n)$ time.

• Searching for an arbitrary value in an unsorted structure takes $O(n)$ time.

• Storing $n$ elements takes $O(n)$ space.

The phrase amortized O(1) is important because dynamic arrays sometimes resize. The copying cost of a resize is spread across many successful insertions rather than charged equally to every individual operation.

Implementation choice also affects practical performance. Arrays often provide better locality of reference and lower per-element overhead. Linked lists can be useful when the maximum size is unknown or when nodes must be added without relocating other elements. Java's ArrayDeque is a resizable-array deque whose ordinary end operations are amortized constant time, and Java recommends a Deque implementation rather than the legacy Stack class for stack behavior.

Deques and applications

A deque supports insertion, removal, and inspection at both ends. Queue behavior uses insertion at the rear and removal from the front. Stack behavior inserts and removes at the same end. A deque also permits operations such as inserting at the front or removing from the rear.

Stacks and queues appear throughout algorithms and systems:

• A call stack tracks active function calls. Calling a function pushes an activation record, and returning pops it. Nested calls therefore return in the reverse order in which they were created. Deep recursion can exhaust the call stack.

• Expression processors use stacks to match parentheses and brackets, evaluate postfix expressions, and manage operators and operands. For ([{}]), each opening delimiter is pushed, and each closing delimiter must match the most recently pushed opening delimiter.

• Undo systems store earlier actions or states on a stack. Backtracking stores choices and removes them when a choice fails.

• Depth-first search can use an explicit stack instead of recursion.

• Scheduling and buffering systems use queues for work awaiting service.

• Breadth-first search uses a queue to process graph vertices in layers. With an adjacency-list graph and suitable bookkeeping, its running time is $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges.

Use a stack for nested operations, undo history, parsing, depth-first exploration, and backtracking. Use a queue for fair processing, buffering, scheduling, producer-consumer pipelines, and breadth-first exploration. Use a deque when both ends must be accessed, and use a priority queue when priority rather than arrival order determines service.

Final takeaway: the correct structure follows the required removal rule: LIFO for stacks, ordinarily FIFO for queues, and both-end access for deques.