What is a Stack
A stack is a data structure that consists of Nodes
. Each Node
references the next Node in the stack, but does not reference its previous.
Stacks follow these concepts:
FILO
First In Last Out
This means that the first item added in the stack will be the last item popped out of the stack.
LIFO
Last In First Out
This means that the last item added to the stack will be the first item popped out of the stack.
Stack Visualization
Push:
Pop:
Peek:
When conducting a peek
, you will only be inspecting the top
Node of the stack.
Typically, you would check isEmpty
before conducting a peek. This will ensure that an exception is not raised. Alternately, you can wrap the call in a try/catch block.
We do not re-assign the next
property when we peek
because we want to keep the reference to the next Node in the stack. This will allow the top
to stay the top until we decide to pop
.
IsEmpty:
ALGORITHM isEmpty()
// INPUT <-- none
// OUTPUT <-- boolean
return top = NULL
What is a Queue
Queues follow these concepts:
FIFO
First In First Out
This means that the first item in the queue will be the first item out of the queue.
LILO
Last In Last Out
This means that the last item in the queue will be the last item out of the queue.
Queue Visualization
Enqueue:
Dequeue:
Peek:
When conducting a peek
, you will only be inspecting the front
Node of the queue.
Typically, you want to check isEmpty
before conducting a peek. This will ensure that an exception is not raised. Alternately, you can wrap the call in a try/catch block.
IsEmpty:
ALGORITHM isEmpty()
// INPUT <-- none
// OUTPUT <-- boolean
return front = NULL