Data Structures: Stacks and Queues
Stacks and Queues are both pretty similar. Both are better than an array for inserting and removal. When you would implement a stack over a queue depends on how you want to retrieve your data. In this article we will explore how to implement a stack and a queue data structure. A prerequisite before following along in this post is to know how to create a singly linked list. I should note that you can create a stack or queue using an array, or a doubly linked list, but we will focus on a SLL. Without further ado, lets get started.
Stacks
Stacks follow the FILO (first in last out) principle, meaning the first item we put into our list will be the last one out. Another way of thinking about it is that the last item we put into our list will be the first one out. In terms of a SLL, what methods might that look like? Well, we could use push/unshift to put items into a list and pop/shift to take things out, but which combinations should we use? Think about a singly linked list and how we access items. It is far easier to remove an item at the start of the list than the end because we don’t have to traverse the list, making it constant time or O(1).
So which pair would be best? In order for us to remove the first item in a list while it also being the last one we put in we would need to use shift to remove from the beginning and unshift to add to the beggining which ensures FILO is followed. Now that we have the gist of everything put together it’s as simple as implementing a singly linked list with these methods which we already know how to do.
Try to implement it on your own before checking the answer below. I named my shift and unshift pop and push for convention purposes.
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
class Stack{
constructor(){
this.first = null;
this.last = null;
this.length = 0;
}
push(val){//unshift
let newNode = new Node(val)
if(!this.first){
this.first = newNode;
this.last = newNode;
}else{
let current = this.first;
this.first = newNode;
newNode.next = current;
}
this.length++
return this
}
pop(){//shift
if(!this.first) return null;
if(this.length === 1){
this.first = null;
this.last = null;
}else{
var remove = this.first;
this.first = this.first.next
}
this.length —
return remove
}
}
let list = new Stack()
list.push(0)
list.push(1)
list.push(2)
list.pop()
console.log(list)
Queues
A queue is just a list. It is almost identical to a stack except it follows the FIFO principle (first in first out). As you can see stacks and queues only seems to differ in the way in which we would want to access data. Stacks if you want to get access to the last piece of data input such as in a undo/redo function in Word. And for a queue the first task item such as in a print job.
Anyways, queues would be best accessed similarly to a stack. We want to retrieve the data at the beginning of the list to save ourselves the time of traversing the entire linked list. So we would use push/shift combo aka enqueue/dequeue as I put below. In doing so, we also get constant time O(1) for insertion and removal.
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
class Queue{
constructor(){
this.first = null;
this.last = null;
this.length = 0;
}
enqueue(val){
let newNode = new Node(val)
if(!this.first){
this.first = newNode;
this.last = newNode;
}else{
this.last.next = newNode;
this.last = newNode;
}
this.length++
return this
}
dequeue(){//shift
if(!this.first)return null;
if(this.length === 1){
this.first = null;
this.last = null;
}else{
var remove = this.first;
this.first = this.first.next;
}
this.length —
return remove
}
}
let list = new Queue();
list.enqueue(0)
list.enqueue(1)
list.enqueue(2)
list.dequeue()//removes 0
console.log(list)
That’s it for this week. Come back next week to see what new stuff I’ll be sharing.
