Stacks and queues are often taught in the same breath. They are a relatively simple data structure each of which only needs two methods to be functional by definition. We need a way to put something in and then take something out.
A few real-world examples of these data structures:
Stack:
A pile of plates in a cafeteria. When you remove a dish from the stack you are going to take the one from the top ( since removing from the bottom would cause a mess ). This is to say the last plate added to the stack is removed first. This means a stack operates on the LIFO principle.
Last
In
First
Out
Queues:
If you’ve ever waited in a line you have been a node in a queue. Think checkout line. The first person in line is going to be the one that is served first. If you recently joined a line and are fifth you need to wait for the four people ahead of you to be served. Thankfully, queues ( and lines ) operate on a FIFO principle.
First
In
First
Out
Let’s Code a Stack Class
Above is the blueprint to get us started for our Stack data structure. At its core, a Stack is a special variant of a singly linked list. We are simply only going to have methods for adding and removing to/from the top of the stack.
Let’s start with add() since you can’t remove() from an empty Stack
add() Pseudocode:
// define a function called add; it takes a value as an argument
// create a new Node using the passed in value
// if the stack is empty; set the first and the last to the new Node
// otherwise; save this.first to a variable then re-assign this.first to our new Node
//new Node should point to our oldFirst
// increment the size of the stack
// return the size of the stack
In the above pseudocode, we are making a stack that is going to add and remove from the top ( this.first ) of the stack. * Remember that singly-linked lists are not great at removing from the end of the list since we do not have a previous property to easily get the second to last node ( which would become our new tail ). Adding to and removing from the top ( this.first ) allows us to do it in constant time.
While we’re at it lets hash out the remove() pseudocode
remove() Pseudocode:
// define a function called remove() ; it takes no arguments
// if the stack is empty; return null
// assign the first item in the stack to a variable
// if there is only one item in the stack; set this.last to null
// then re-assign this.first to oldFirst.next
// decrement the size
// return the value of the oldFirst
Here we are making sure we are removing in constant time as well. We need to make sure if we are emptying the list we also remove the connection to this.last as well.
Here’s my implementation:
Queues similarly have only need a method to add to and remove from the queue. The difference is that queues need to add() to the end and remove from the beginning. This will ensure we have the LIFO methodology mentioned above.
Let’s put together our blueprint for the Queue class
Let’s talk about our add() and remove() methods
add() Pseudocode:
// define a function called add(); it takes a value as an argument
// create a new Node using the value passed in
// if the Queue is empty set this.first and this.last to our new Node
// otherwise add the new Node to the end of our list
remove() Pseudocode:
// define a function called remove(); it takes no argument
// if the queue is empty; return null
// store the oldFirst in a variable
// if there is only one node in the queue set this.last to null
// set this.first to the next node in the queue
// decrement the size of the queue
// return oldFirst.val
Our queue is going to add to the end of the list ( this.last ) and remove it from the front of the queue. This obeys our FIFO methodology.
Here’s my implementation:
Queues and Stacks are simple structures with some basic functionality but will be used as a component to other larger and more complex data structures. If you want to check out more about them I’ll link to more articles about them in the coming weeks.
