Stack as a LIFO

Fundamental Stack Operations

Author: Fibi. This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

Start with an empty stack; PUSH('A') (at position 0); PUSH('B') (at position 1); POP() ['B']; POP() ['A']; Empty stack

Example: Implementing a Stack

Scenario: Simple undo history for a text editor. Each user action is pushed onto a stack. When the user presses UNDO, we pop the most recent action. Capacity limits prevent the history from growing indefinitely.

• Python
• Java

# Stack with capacity and basic operations
class Stack:
    def __init__(self, capacity):
        self.items = []          # underlying list
        self.capacity = capacity # maximum size

    def push(self, item):
        if not self.is_full():
            self.items.append(item)
        else:
            return "Stack is full"

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return "Stack is empty"

    def is_empty(self):
        return len(self.items) == 0

    def is_full(self):
        return len(self.items) >= self.capacity


# --- Scenario: simple UNDO history for a text editor ---
# Actions: normal strings are edits we record; "UNDO" means revert last edit.
actions = ["type 'A'", "type 'B'", "UNDO", "type 'C'", "UNDO", "UNDO"]
history = Stack(capacity=5)

for action in actions:
    if action == "UNDO":
        removed = history.pop()                 # reason to pop: user requested UNDO
        print("POP  -> Undo (removed):", removed)
    else:
        if history.is_full():
            print("History full; cannot record:", action)
        else:
            history.push(action)                # reason to push: new user action to remember
            print("PUSH -> added:", action)

top = history.peek()
print("Top of history:", top)

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> history = new Stack<>();
        int capacity = 5; // demo capacity limit

        // --- Scenario: simple UNDO history for a text editor ---
        String[] actions = {"type 'A'", "type 'B'", "UNDO", "type 'C'", "UNDO", "UNDO"};

        for (String action : actions) {
            if ("UNDO".equals(action)) {
                // reason to pop: user requested to revert last action
                if (!history.empty()) {
                    String removed = history.pop();
                    System.out.println("POP  -> Undo (removed): " + removed);
                } else {
                    System.out.println("Undo requested but history empty.");
                }
            } else {
                // reason to push: new action to remember
                if (history.size() >= capacity) {
                    System.out.println("History full; cannot record: " + action);
                } else {
                    history.push(action);
                    System.out.println("PUSH -> added: " + action);
                }
            }
        }

        System.out.println("Top of history: " + (history.empty() ? "(none)" : history.peek()));
    }
}

Performance and Memory Impact

• Push and Pop: Fast insertion and removal; O(1) time complexity.
• isFull / isEmpty: O(1) checks based on current size.
• Memory Usage: Each element consumes memory; fixed-capacity stacks may waste or limit memory.

Use Cases for Stacks

• Undo/Redo Operations: In text editors or graphic software, each user action (typing a character, drawing a line) is pushed onto a stack. When undo is pressed, the latest action is popped and reversed. The stack’s state tracks past operations, enabling sequential undos/redos.
• Expression Evaluation: During arithmetic parsing (e.g. converting infix to postfix), operators are pushed onto a stack to manage precedence. For input “3 + 4 * 2,” the '*' remains on the stack until its operand is processed, ensuring correct order. After evaluation, the stack is emptied as operators are popped.
• Backtracking: In maze-solving or DFS (Depth First Search), each decision point (cell coordinates) is pushed before exploring a path. If a dead end is reached, the last position is popped to backtrack. The stack reflects the current path, shrinking as you retreat.
• Function Call Management: During recursion, each function call’s local variables and return address are pushed onto the call stack. When a function returns, its frame is popped, restoring the previous context. The call stack depth indicates nesting level.