Stack

Stack is an Abstract Data Type where the most recently added item is the first item removed.

This behavior is called last in, first out, or LIFO.

Common operations:

• Push: add an item to the top
• Pop: remove the item from the top
• Peek: read the item at the top without removing it

Stacks are useful for:

• Function call stacks
• Undo operations
• Parsing
• Depth-first search
• Matching brackets or parentheses

A stack can be implemented using an array or a linked list.

Typical operations are O(1) when the underlying implementation supports efficient insertion and removal at the top.

flowchart TD
    Top["top"] --> C["C: newest"]
    C --> B["B"]
    B --> A["A: oldest"]

Anki

id: stack-definition deck: Computer Science::Data Structures tags: data-structures stack

Q: In a stack, which item is removed first? A: The item that was added most recently.

id: stack-lifo deck: Computer Science::Data Structures tags: data-structures stack

Q: What everyday object behaves like a stack? A: A stack of plates: the last plate placed on top is usually the first one removed.