Stacks

Stack ADT

• Provides abstraction/encapsulation
• Internal details are protected from external misuse
• Last-in, first-out (LIFO)
• Add to, remove from, and peek at the top only
• Required: push(item), pop, peek
• Java's Stack: (size, empty, search)
• EmptyStackException (peek, pop)

Array Based Stacks

• Store stack data on array
• Keep bottom of stack at 0, use stack pointer to keep track of top-of-stack (TOS)
• Start with TOS pointer at -1
• On push(item), array[++TOS] = item
• On peek, return array[TOS]
• On pop, return array[TOS--]
• Size, TOS + 1
• Don't forget to handle when stack is empty

Create an empty stack

data
index	-1	0	1	2	3	4	5
TOS	^

push(A)

data		A
index	-1	0	1	2	3	4	5
TOS		^

push(B)

data		A	B
index	-1	0	1	2	3	4	5
TOS			^

push(C)

data		A	B	C
index	-1	0	1	2	3	4	5
TOS				^

peek() should return?

pop() (returns C)

data		A	B	C
index	-1	0	1	2	3	4	5
TOS			^

pop() (returns B)

data		A	B	C
index	-1	0	1	2	3	4	5
TOS		^

push(Z)

data		A	Z	C
index	-1	0	1	2	3	4	5
TOS			^

Big-O

• push - O(1) (unless we have to create a larger array and copy everything down, then O(n))
• pop - O(1)
• peek - O(1)

Node Based Stacks

• Use of singly linked list is sufficient
• Keep track of TOS with a node (head)
• An empty stack should have a TOS which points to null
• push(item), make new node point to what TOS points at, make TOS point to new node
• peek, return data in node at TOS
• pop, return data in node at TOS, TOS = TOS.next
• Keep track of size independently
• Don't forget to throw EmptyStackException

Empty stack

TOS
 |
null

push(A)

TOS
 |
 A -> null

push(B)

TOS
 |
 B - > A -> null

push(C)

TOS
 |
 C -> B -> A -> null

peek() ?

pop(), returns C

     TOS
      |  
 C -> B -> A -> null

TOS
 |
 B -> A -> null

pop(), returns B

     TOS
      |  
 B -> A -> null

TOS
 |
 A -> null

push(X)

TOS
 |
 X -> A -> null

Big-O

• push - O(1)
• peek - O(1)
• pop - O(1)

Why are Stacks useful?

• Computer Programs - Bottom of stack fixed spot in memory, stack pointer stored in register
• Call stack - Keep track of which methods are called, and locations to return
• Stack oriented programming language (JVM)
• Many CPUs have special registers for stack pointers to conserve opcode space
• Converting decimal to binary
• Towers of Hanoi (will revisit when we get to recursion)
• Expression evaluation and syntax parsing (context-free languages)
• Matching of parenthesis/brackets
• Evaluation of an infix expressions
• Evaluation of prefix expressions
• Evaluation of postfix expressions
• Conversion between different expression types
• Backtracking
• Tree Traversals