Stacks, Queues, & Deques

The previous page introduced lists as fundamental data structures, and provided a way to conceptualize organizing collections of data objects in memory. However, you may have noticed that the basic list ADT provides limited operations for composing algorithms. This page expands the basic list concept by introducing several higher-level abstractions which can be layered on top of simple base list structures to provide much more practical and versatile structures for real-world programs.

The Stack ADT

Stacks derive their name from a literal stack of items. Legend has it that the name originated from the way a spring-loaded cafeteria plate dispenser or a stack of papers works. The idea is that you load items in one at a time, one on top of the previous, and then retrieve items in reverse order starting with the last item inserted onto the stack. Indeed the defining characteristic of stacks are their last in, first out (LIFO) behavior. This means that only the most recent item added to the stack is immediately available.

Canonically, the stack ADT has a similar (but even more restricted) set of operations as the basic list ADT. You push items to the stack, and pop the most recently inserted item for use or removal. If you just want to view the top of the stack without removing it you can define a peek or top routine which returns a copy or reference to the data at the top of the stack. A pop or peek on an empty stack is considered an error, but running out of memory for a push is not. Indeed the latter operation is where the famous “stack overflow” term comes from. It is not common to provide a contains operation on stacks, as only one immediate element in the stack is available at a time.

Representation

It’s possible to represent stacks with either of the list variants covered on the previous page. Indeed it is common to do so with both contiguous- or linked-based storage layouts.

Both contiguous structures (that store a len) and linked lists that push new nodes to the head of the list can access, add, and remove the top stack element in O(1) time. This constant time bound is amortized for contiguous structures because of potential O(n) resize operations for dynamic arrays, but guaranteed for linked lists.

Example

This section outlines some common stack-based operations to get you thinking about how to use stacks.

The first exapmle is an “undo” function in a text editor. Each addition is pushed to the editor’s stack. When you invoke the “undo” function it pops (removes) the elements from the stack. You could similarly push the popped elements to a different stack to implement “redo” functionality. When you’re satisfied with the current state of the document, you can commit the initial stack to non-volatile memory which saves the document’s state.

This example checks if a string (slice) contains balanced sets of braces. That is, if each opening brace [, {, or ( has a matching closing brace as ], }, or ). The example uses Rust’s Vec (dynamic array) backing structure to create a stack. The example function reads the string’s characters one-by-one, checking for opening braces. If it encounters one of the listed opening braces it gets pushed to the stack. When the loop encounters a closing brace it attempts to match against a reference to the top of the stack, the last item pushed to the stack. If the symbols match the function pops the stack, exposing the next potential match.

fn balance(s: &str) -> bool {

    // Create a stack to track delimeters
    let mut stack = Vec::new();

    for e in s.chars() {
        match e {
            // Push opening symbols to the stack
            '[' | '{' | '(' => stack.push(e),

            // Otherwise, check if the closing symbol has an opener
            // if it does, the opener gets popped
            ']' | '}' | ')' => {
                if stack.is_empty() {
                    panic!("Error: No opening symbol for {e}");
                } else {
                    let check = *stack.last().expect("Error: No symbols on stack");
                    if matches!((check, e), ('[', ']') | ('{', '}') | ('(', ')')) {
                        stack.pop();
                    }
                }
            }
            _ => {} // No-op catch-all for non-delimieter symbols
        }
    }

    // The stack should be empty after iterating through all delimeters
    if !stack.is_empty() {
        panic!(
            "Error: Missing closing symbol for {}",
            stack.last().unwrap()
        )
    }

    true
}

The Queue ADT

Queues (pronounced like the letter Q) are sequential data types with specific rules about insertion and removal, called queuing logic. There are several common sub-types that specify slightly differing queuing logic approaches. The basic queue operates with first in, first out (FIFO) logic, like a line to order food. As people arrive they get in line and the cashier helps each customer in a “first come, first served” order. That is to say you “enter” the queue at the “back” of the line, and you’re served at the “front” of the line. The operations are canonically named enqueue for inserts at the “back”/“tail” of the queue, and dequeue (pronounced “dee-Q”) for removals at the “head”/“front” of the queue.

Queues as logical structures occur in many real-life situations. The food truck example is just one of many situations that is appropriately addressed by queuing logic. Queuing logic is also very common in computer programs. You may experience queuing logic in how a networked printer handles print jobs, or how a server responds to more requests than it can process. Queues are also used heavily in computational graph algorithms, which this module covers later.

Deques & Circular Queues

Double-ended queues, also called deques (pronounced “decks”), are queues that are capable of O(1) enqueue and dequeue operations at either end of the queue. You can slap a enqueue_front, enqueue_back, dequeue_front, and dequeue_back on any list, but its the time complexity guarantee that makes it a proper deque.

Circular queues, also called ring buffers, are queues where the head and tail of the queue are logically connected in a way that allows you to iterate over the list in one direction indefinitely without any logical “end” or “hard stop”.

Representation

Similar to stacks, its possible to represent queues with either of the two list representations, but linked lists provide easy (and guaranteed) O(1) operations. Supporting O(1) (amortized) operations at both ends of a queue based on a contiguous structure is a little trickier. If the enqueue operation simply adds elements to the next open slot of the array, each dequeue operation would naively require O(n) moves to shift the queue elements. As a result, its common to impose some logical wrapper over the contiguous backing structure that stores indexes to the “head” and “tail” of the queue as logical entities independent of the underlying layout. Using the logical representation, if you enqueue five elements into an indexed list with a capacity of 10, your “tail” index would be 4 and your “head” index would be 0. If you then dequeue four elements, your “head” index moves up to 3, such that the queue now contains only one item. A naive implementation would then calculate that the queue’s capacity is now only six, despite “dequeuing” the first four indexes. In this scenario the best solution is to use circular queue logic, also called index wrapping or ring buffers, to properly account for the “removed” nodes. To do this, a simple solution is to use modulus operations for both enqueuing and dequeing. Doing this allows you to retain the underlying list’s capacity while providing efficient O(1) operations without shifting remaining elements when dequeuing.

Alternatively, it may be helpful to organize queue representations into memory-bound and un-bounded categories. For example, if your design requirements stipulate a fixed maximum number of possible queue elements it may be more efficient to implement a memory-bound solution with index-wrapped arrays to guarantee O(1) operations. Un-bounded representations may use dynamic arrays or linked lists.

Conclusion

Stacks and queues provide conveneint abstractions over both contiguous and linked list data types. Efficient stacks, queues, and deques provide O(1) insert and removal operations. Queue and deque designs over contiguous structures require additional index wrapping logic to support efficient O(1) operations. Just like with the underlying lists, stack, queue, and deque designs over contiguous lists may experience occasional O(n) resize operations when implementing growable structures, whereas linked structures guarantee O(1) operations with the potential for additional pointer chasing overhead.

Implementation Notes

Be sure to check out the companion library’s doubly-linked list which contains operations to build a stack, queue, or deque. Because Rust requires compile-time constants to instantiate arrays, the library contains a Vec-based queue with fixed (memory bound) and dynamically sized (unbounded) options.