Stacks And Queues
Stacks
What is a stack?
A stack is an abstract data structure that abides by the last in, first out (LIFO) principle: the last element added to a stack will be the first one removed.
A real-life example of this is a stack of plates: the last one you washed and put in the cupboard is always the first one you use!
Use cases
Call stack: used to manage function invocations
Undo/redo: new actions are added to the top of the stack, and undoing those actions removes the most recent action
Routing history: a history of the routes you've visited in a browser are modeled as stacks
Array implementation
A stack is a concept: as long as you abide by LIFO, the data structure is considered a stack. For that reason, you could use arrays for stacks.
The most efficient approach is to use push and pop:
// Imagine this stack is for browser history
const stack = []
stack.push('https://google.ca')
stack.push('https://youtube.com')
stack.pop() // Returns google.caPro tip: The trouble with arrays is that they're indexed, and this means more data. If you care about efficiency and are dealing with lots of data but don't need features like random access, an array isn't the best implementation of a stack. After all, all you need to achieve a stack is an order of what came before. This is why linked lists are often better.
Custom class implementation
If we want to avoid the bloat associated with arrays--like indices or all the built-in array methods--we can opt for a linked list implementation with 2 methods: one that adds to the list and one that removes from the list.
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class Stack {
constructor() {
// These properties are just named this way to use the terminology of stacks
this.first = null
this.last = null
this.size = 0
}
}Note: Recall that pop is O(n) for singly liked lists because it traverses through ever node to get to the last node. As a result, this implementation will technically use unshift and shift since they're O(1), but we'll call them push and pop.
push(val) {
const node = new Node(val)
if (this.size === 0) {
this.first = node
this.last = node
} else {
const previousFirst = this.first
this.first = node
this.first.next = previousFirst
}
this.size++
return this.size
}
pop() {
if (this.size === 0) return null
const poppedNode = this.first
if (this.size === 1) {
this.first = null
this.last = null
} else {
this.first = poppedNode.next
poppedNode.next = null
}
this.size--
return poppedNode
}Big O
The two most important features of a stack are push and pop, which are O(1).
Search and access will be O(n) because you have to traverse using next. But if you need search and access, you probably don't want to use a stack.
Queues
What is a queue?
A queue is an abstract data structure that abides by the first in, first out (FIFO) principle: the first element added to a queue will be the first one removed. Adding an element to the end of a queue is to enqueue. Removing the oldest element at the beginning of a queue is to dequeue.
A real-life example of this is a queue (or lineup) at a rollercoaster: the first person in line gets to go on the ride first.
Use cases
Waiting in line to join an online game with full participants
Printers use a queue to track which document it will print next
When you upload or download content, sometimes it's treated like a queue
When you run background tasks, sometimes it's managed using a queue as well
Array implementation
With an array, you either choose push + shift or unshift + pop. The only difference is whether you're adding at the beginning and removing from the end or vice versa.
Custom class implementation
In a singly linked list, it's best to enqueue at the end (push) and dequeue at the beginning (shift). That's because the alternative involves removing from the end, which corresponds to a pop. And since pop in a singly linked list is O(n), that would be the less time efficient choice.
The implementation of a queue is identical to shift and push in the notes:
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class Queue {
constructor() {
this.first = null
this.last = null
this.size = 0
}
// Add at the end (like push)
enqueue(val) {
const node = new Node(val)
if (this.size === 0) {
this.first = node
this.last = node
} else {
this.last.next = node
this.last = node
}
return ++this.size
}
// Remove from the beginning (like shift)
dequeue() {
if (this.size === 0) return null
const removedNode = this.first
if (this.size === 1) {
this.first = null
this.last = null
} else {
this.first = removedNode.next
removedNode.next = null
}
this.size--
return removedNode.val
}
}Big O
Just like stacks, our custom implementation is O(1) for insertion and removal, but it's O(n) for search and access. However, if you're going to use a queue, you shouldn't care about search and access.
Last updated