Stacks

Stacks are linear data structures that derive their name from a literal stack of items. Common analogies to describe stacks include a spring-loaded cafeteria plate dispenser or a stack of papers. The idea is that you load items in one at a time, one on top of the previous, and then retrieve items linearly starting with the last item inserted onto the stack. Indeed the defining characteristic of stacks are their last in, first out (LIFO) nature. This means that only the most recent item added to the stack is immediately available. Colloquially you push or add items to the stack, and pop them for use or removal. If you just want to view the top of the stack without removing it you can implement a peek or top routine which returns a copy or referene 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.

Implementations

It’s possible to implement stacks with pretty much any of the basic list ADT variants already covered and includes arrays (or dynamic arrays such as vectors), and linked lists.

If you’re already tracking a stack’s “top” via either an array index of 0 or a top reference in a linked-list your operations can generally be assumed to take O(1) time. Dynamically sized stacks may require occasional O(N) time for pushes to array-based lists, but if you double the array when you reach capacity these operations amortize to roughtly O(1). Because the actual mechanics of each of the list implementations have already been covered in the Lists section this page does not duplicate those efforts. Instead this section provides some simple examples and covers a couple standard library implmentations for use in your programs.

Examples

Stacks are often considered to be one of the most fundamental data structures in computer science. One stack example is the “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. This tracks the state of the data. When you’re happy, you can commit the initial stack to non-volatile memory which saves the document’s state.

This example checks if a String contains balanced sets of braces. It works by leveraging Rust’s ultra-handy Vec type to create a stack. The functions reads the string’s characters, checking for opening braces. If it encounters one of the listed opening braces the 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. If the symbols match the function pops the stack. You can imagine how this might be used in other string parsing functions, a compiler, or an interpreter to signal function calls with arguments between braces.

fn balance(s: String) -> bool {
    let mut symbols = Vec::new();

    for e in s.chars() {
        match e {
            '[' | '{' | '(' => {
                symbols.push(e);
            }
            ']' | '}' | ')' => {
                // Checks that all closing symbols have a matching opener,
                // if it does, the opener is popped
                if symbols.len() == 0 {
                    panic!("Error: Unexpected closing symbol");
                } else {
                    let check = *symbols.last().expect("Error: No symbols on stack");
                    if (check == '[' && e == ']')
                        || (check == '{' && e == '}')
                        || (check == '(' && e == ')')
                    {
                        symbols.pop();
                    }
                }
            }
            _ => {}
        }
    }
    // Checks that all opening symbols have a matching closer
    if symbols.len() > 0 {
        panic!("Error: Missing closing symbol")
    }
    true
}

Standard Library Implementations

The stack is a fundamental ADT, so operations are included in both Rust and Java’s standard libraries. The following operations can be found in Rust’s std::vec::Vec module and Java’s java.util.ArrayList class.

Operation	Explanation	Rust Vec	Java ArrayList
Push	Adds (“pushes”) an item to the “top” of the stack	push(e)	push(e)
Peek	Returns the “top” of the stack without removing it	last()	peek()
Pop	Returns (and removes) the top of the stack	pop()	pop()
Size	Returns how many items are in the stack	len()	size()
Is empty	Returns a boolean to indicate if the stack is empty or not	is_empty()	empty()