Stacks and Queues
What is a stack?
A stack is a data structure like a list. However, a stack is LIFO - Last In First Out. This means you can only ever access items at the top of the stack, just like with a stack of plates, a stack of books or the Towers of Hanoi game pictured below. You should think of a stack as vertical. So you push items onto or pop items from the top of the stack.
Stack Operations
Here are the main functions for a stack:
Push()- add to the stackPop()- retrieve from the stack.Peek()- is there something more there? Takes a copy of the item but does not remove it.IsEmpty()- is it empty?IsFull()- is it full?
Considerations when pushing onto or popping off of a stack.
Push()- what if the stack is full? Trying to push onto a full stack results in a stack overflow error.Pop()- what if the stack is empty? Trying to pop off an empty stack resulting in stack underflow error.
Queues
A queue is like a stack, but just like a queue of customers at a shop, a queue is FIFO - First in First out. New items are added to the back of the queue.
Queue Operations
Enqueue()- add an item to the queue.Dequeue()- take an item from the front of the queue.Peek()- return an item from the front of the queue without actually removing it from the queue.IsEmpty()- is it empty?IsFull()- is it full?
Trying to enqueue onto a full queue results in an overflow error.
Trying to dequeue from an empty queue results in an under flow error.
