Reading notes about code for my future reference.
The lesson for today will be about the Stacks and Queues data structures.
So Stacks and Queues are relatively similar to linked list in their construction.
Today we will be going over Stacks and Queues. We will start with Stacks.
So the best way to visualise a stack is like a stack of pancakes. When you eat a stack of pancakes you don’t eat from the middle of the stack, you start from the ends (if you eat like a normal person atleast.)
Using pancake stack terms we can now bring up the concepts of how nodes travel within a stack.
This is first in Last Out, meaning that the first item you put on a stack will be the last on top.
Last In First Out
This means the last item in the stack will be the first to go.
Using pancake terminology it makes sense. Who eats a pancake from the bottom?
When you are at the opening of a stack we call that the top and the subsequent part of the stock is usually set as top.next. The parts of the stacks are called nodes.
We add things to the stack by using the PUSH method.
ALOGORITHM push(value) // INPUT <– value to add, wrapped in Node internally // OUTPUT <– none node = new Node(value) node.next <– Top top <– Node
We use Pop to remove nodes from the stack.
ALGORITHM pop() // INPUT <– No input // OUTPUT <– value of top Node in stack // EXCEPTION if stack is empty
Node temp <– top top <– top.next temp.next <– null return temp.value
Queues work like stacks except they are horizontal, like a line of people!
First In First Out
This means that the first item in the queue will be the first item out of the queue.
Last In Last Out
This means that the last item in the queue will be the last item out of the queue.
You wouldn’t just jump in the middle of a line, and you definitely wouldn’t jump into the front.
This is the method used to add a node onto a queue, these can only be appended in the rear like a line full of people.
This is what is used to remove a node from a queue and it always has to be the removed from the front like a line of people.