Stacks

Intro

Another AbstractDataType that represents a sequential collection of data. Stacks are characterised by their LIFO (Last In First OUT) operation order, meaning the element added last is the first to be removed.

Operations

The support the operations push (insert a new element on the top of the stack) and pop (remove and return the most recently added element, the element at the top of the stack).

Implementation

Similar to a Queue a Stack can also be implemented using arrays or singly linked lists. Here’s an example I built using Java’s ArrayList data type:

import java.util.ArrayList;
 
// Stack class
class MyStack {
    private int length;
    private final ArrayList<Character> items;
 
    public MyStack() {
        this.length = 0;
        this.items = new ArrayList<Character>();
    }
    
    // Insert a character to the top (end) of the stack
    public void push(char character) {
        this.items.add(character);
        this.length++;
    }
 
    // Remove and return the top character from the stack
    public void pop() {
        if (this.length > 0) {
            char popped = this.items.get(this.length - 1);
            this.items.remove(this.length - 1);
            this.length--;
        }
    }
 
    // Show the top character in the stack
    public char peak() {
        return this.items.get(this.length - 1);
    }
 
    public int size() {
        return this.length;
    }
}

Stacks and Recursion

Stacks are important for implementing and supporting nested or recursive behavior. It’s also used to implement DFS, which is either done by recursive calls or manually managing a stack.

Use Cases

Backtracking

Finding correct path through mazes

Compile time memory management

Storing local data and procedure info. Nested and recursive functions.

Depth First Search

DFS is implemented recursively which is orchestrated by function calls on the Stack. Read about it here Graph and Tree Algorithms.

Undo - Redo

On any computer or program that has an undo-redo functionality, it’s using stacks to do so, via pop and push.

Time complexity

Operation	Big-O
Top/Peek	O(1)
Push	O(1)
Pop	O(1)
isEmpty	O(1)
Search	O(n)

Edge cases

• Empty stack. Popping from an empty stack
• Stack with one item
• Stack with two items

Essential questions

• Valid Parentheses
• Implement Queue using Stacks

Recommended practice questions

• Implement Stack using Queues
• Min Stack
• Asteroid Collision
• Evaluate Reverse Polish Notation
• Basic Calculator
• Basic Calculator II
• Daily Temperatures
• Trapping Rain Water
• Largest Rectangle in Histogram

---

References

• Tech Interview Handbook