Code 401: Class 10 - Stacks and Queues

Read: Stacks and Queues

Stack data structure that consists of nodes that each reference the next but not the previous
FILO First In Last Out
LIFO Last In First Out
Pushing something in to a stack will place it at the top
Popping something off of the stack removes the top item
To Push O(1)
1. Assign new node’s next to current top node
2. Reassign reference to top node to the new node
To Pop O(1)
1. Set a temp to hold the top pointer
2. Reassign top to next
3. Remove top node
4. Clear out temp reference
To Peek O(1)
1. Run isEmpty() first to check if the list is empty
2. Return the value of the top node
isEmpty() O(1)
1. Check to see if the top node is null
Queue
Enqueue O(1)
1. Set rear.next to new node
2. Reassign rear to new node
Dequeue O(1)
1. Create a temp reference that points to the same location as Front
2. Reassign Front to next
3. Clear the temp reference
Peek O(1)
1. Check isEmpty() first to make sure queue is not empty
2. Return front value
isEmpty O(1)
1. Return true if front = null