Stacks

First in Last Out (FILO)

ADT

• Data
  • Items
  • Number of items
  • Top
• Operations
  • push(item): inserts an element
  • pop(): removes and returns the last inserted element
  • peek(): returns the last inserted element without removing
  • size()
  • isEmpty()

Implementations

Array

• Characteristics
  • Fixed size
  • Stores similar elements
  • Access through top index
• Performance
  • push(item): O(1)
  • pop(): O(1)
  • peek(): O(1)
  • size(): O(1)
  • isEmpty(): O(1)
• Pros/Cons
  • Pro: Constant time to add and remove elements
  • Con: Fixed size and no random access

Linked List

• Characteristics
  • Flexible Size
  • Stores similar elements
  • Access through top pointer
• Performance
  • push(item): O(1)
  • pop(): O(1)
  • peek(): O(1)
  • size(): O(1)
  • isEmpty(): O(1)
• Pros/Cons
  • Pros
    • Constant time to add and remove elements
    • Variable size
  • Con: More memory

C++ STL

• push() = push()
• pop() = pop() (but does not return removed element)
• peek() = top()
• size() = size()
• isEmpty() = empty()

Use Cases

• Evaluate expressions
  • Stack formatted expression: Have an operand stack and have operators pop out the top two elements and then push the result
• Balanced parenthesis
• Undo/Redo
• Depth first search
• Reversal
• Converting decimal to other number system

void dec_to_other(int num, int base) {
	stack<int> stk;
 
	while(num > 0) {
		stk.push(num % base);
		num = num / base;
	}
 
	while(!stk.empty()) {
		cout << stk.top();
		stk.pop();
	}
}

Storing the Minimum

• Push
  • If stack is empty
    • Insert $x$
    • $min=x$
  • Else If $x\ge min$
    • Insert $x$
  • Else
    • Insert $2x-min$
    • $min=x$
• Pop
  • y = removed value from top
  • If y < min
    • oldMin = min
    • min = $2\cdot min-y$
    • return oldMin
  • Else
    • return y
• Top
  • If top < min
    • return min
  • Else
    • return top
• Min
  • return min