Table of Contents

Description

Think of a stack of plates. You can add a plate to the stack by adding it to the top. To remove a plate from the stack, you have to remove the plate on top of the stack. The stack data structure models a stack of plates.

• Composition
  • Several adjacent data elements.
  • Each element is on top of the other.
• Properties
  • LIFO (Last In First Out): The last (most recent) item you added to the stack will be the first one that’s removed.
    • This means you must push and pop items from the same side.
  • You can only add/remove the top item of the stack.
• Operations
  • Push: Places an item on top of the stack.
  • Pop: Removes the item on top of the stack.
  • Peek: Return the value of the item on top of the stack.
  • Search: Searches through the stack for a particular item.
  • Size: Return the size of the stack.

Usage

• Real world models
  • Stack of plates
  • Pile of books
  • Any “stack of things” in the real world.
• Programming problems
  • Tower of Hanoi:
    • This is a programming problem where you have 3 totems. 1 totem has plates of various sizes on them, ordered by size (smallest on top).
    • Objective
      • Get all disks on another totem in the same order.
      • However, you’re not allowed to place any larger disk over a smaller disk in the process.
• Problems where you have to match parts of a string or code to something else, in the correct order.
  • Ex: Determine if every bracket is properly closed. {([])}
    1. Read through each character
  1. Push (, [, { in a stack.
  2. When you encounter ), ], }, pop the top character of the stack, then check if it matches.
  3. If they all match, and the stack is empty at the end, then the string is correct.
• Recursion problems
  • Remembering data: You go down 1 path of a recursive function tree, and store data in the stack while doing so. After you reach the end of one path, you backtrack and re-access the data in the stack, before restarting the process.
  • The stack allows you to remember data from one recursive function sequence, after you start a new one.
  • Reimplementing recursive algorithms: You can use a stack to reimplement a recursive algorithm iteratively (i.e. without recursion).

Efficiency

• Push, pop, and peek are constant time because they don’t require you to iterate through each element in the list. You just have to look at the first element.
• Searching in the worst case requires you to iterate through every element once until you find the one you’re looking for at the bottom of the stack. Therefore, it’s linear time.
• Size is a property that’s tracked in the field of the data structure. Whenever you push/pop, the field is modified.
  • To get the size, simply return the field value.
  • You don’t have to iterate through the entire stack counting how many items there are, so it’s constant time.

Implementation