The Stack ADT

• Stack


  A list with the restriction that insertions and deletions can be performed in only one position, namely, at the end of the list, called the top
• Fundamental operations

  • Push
  • Pop
• Push


  1. Inserts

  2. Input operations
• Pop


  1. Deletes the most recently inserted element

  2. Output operations
• LIFO


  Last in first out
• Implementation

  • A stack is a list so any list implementation will do
  • 99% of the time ArrayList and LinkedList are the most reasonable choice
  • Stacks are constant-time operations
• Applications

  • Balancing Symbols
  • Postfix Expressions
  • Infix to Postfix Conversions
• Balancing Symbols


  Checks whether everything is balanced
• Infix to Postfix Conversions


  When an Operator is seen, it is placed on the stack