3.1 Stack ADT and Applications

Stacks are a crucial data structure that follows the Last-In-First-Out principle. They're used in various applications, from managing function calls to evaluating expressions and implementing undo/redo functionality.

The stack's primary operations—push, pop, peek, isEmpty, and size—all have O(1) time complexity. This efficiency makes stacks ideal for scenarios where quick access to the most recently added element is essential.

Stack ADT Fundamentals

Stack abstract data type

Top images from around the web for Stack abstract data type

• 

  Estructura de datos y algoritmos: pila View original

  Is this image relevant?

• 

  Stack (abstract data type) - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  IDisposable Thoughts - Data structures, the humble Stack View original

  Is this image relevant?

• 

  Estructura de datos y algoritmos: pila View original

  Is this image relevant?

• 

  Stack (abstract data type) - Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Stack abstract data type

• 

  Estructura de datos y algoritmos: pila View original

  Is this image relevant?

• 

  Stack (abstract data type) - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  IDisposable Thoughts - Data structures, the humble Stack View original

  Is this image relevant?

• 

  Estructura de datos y algoritmos: pila View original

  Is this image relevant?

• 

  Stack (abstract data type) - Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 3

• Abstract data type organizes elements in a Last-In-First-Out (LIFO) manner
• Insertions and deletions occur at the same end called the top of the stack (plates, books)
• Primary operations include push to insert an element, pop to remove the top element, peek to view the top element without removal, isEmpty to check if the stack is empty, and size to get the number of elements
• All primary operations have a time complexity of $O(1)$ enabling efficient manipulation of the stack

LIFO principle for stacks

• Last element inserted is the first one to be removed (stack of plates, web browser back button)
• Elements added and removed only from the top of the stack
• Bottom element is the first one inserted and the last one to be removed
• Accesses elements in the reverse order of their insertion
• Useful for scenarios processing the most recently added element first (undo/redo, backtracking)

Applications of stacks

• Function call management pushes local variables, parameters, and return address onto the call stack when a function is called and pops them when the function returns (recursive functions)
• Expression evaluation uses stacks to evaluate arithmetic expressions in infix, postfix, or prefix notation by pushing and popping operands and operators based on precedence rules (calculators)
• Undo/redo operations in text editors or software applications maintain a stack of previous actions
• Backtracking algorithms like depth-first search use stacks to keep track of visited nodes and explore alternative paths
• Syntax parsing and validation checks for balanced parentheses or brackets by pushing opening symbols and popping them when closing symbols are encountered

Time complexity of stack operations

• All basic stack operations have a time complexity of $O(1)$ making them highly efficient
  1. push(element): $O(1)$
  2. pop(): $O(1)$
  3. peek() or top(): $O(1)$
  4. isEmpty(): $O(1)$
  5. size(): $O(1)$
• Constant time complexity achieved by accessing or modifying only the top element without traversing the entire stack
• Space complexity of a stack is $O(n)$ where $n$ is the number of elements as the stack grows linearly with the number of elements it contains (call stack, browser history)