Stacks And Queues

NOTE: This will be important for the calculator assignment.

Classic Stack Analagy

  • Last-in, first-out (LIFO): the last item placed on the stack will be the first item removed.
  • Analogy: a stack of dishes. You only interact with a stack through the last item on the stack; either add or remove from the top.

Stack Operations

  • create empty stack
  • determine if stack is empty
  • "push" item on stack
  • "peek" - look at the item on top of the stack
  • "pop" - ?

Linked List as Stack

  • you add and remove things from the head.

Array or ArrayList as a stack

  • add to the end, and remove from the end.

See "Example Stack Use" for how to check for balanced braces.

Postfix (RPN) Evaluation

  • Given a postfix expression:
    • 2 3 4 + *
  • process from left to right
    • push operands (nums) on the stack
  • Some assemblers do algebra this way.

Stacks and Recursion

  • stacks are hidden in recursive programming.
  • each recursive call gets a copy of local variables.
  • programming languages use a "call stack"
    • there is a place in memoery where the local variables are stored, and it's accessed as a stack.
  • an explicit stack can be used to make non-recursive versions of recursive algorithms.

Queues

  • First-in, first-out (FIFO): Feed stuff in at one end, comes out of another end.
    • items enter at back of queue
    • items leave from front of queue
  • like a line at the store/movies.

Queue Operations

Abstract operations: * createQueue() * boolean isEmpty() * void enqueue(newItem) - adds a new item * Item dequeue() - returns and removes oldest item * Item peek() - return oldest item (w/o removing)