Data Structures — Queues & Stacks
AKA FIFO & LIFO
In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently. Data structures provide a way for systems to manage large amounts of data efficiently, such as with databases. This post will be one of many in a series that dissects the intricacies of specific data structures. To begin with, we will be going over the two basic data structures: Queues and Stacks.
Queue
As the name suggests, a Queue data structure behaves exactly like a queue (or line). That is to say, it is a structure defined by its ‘First In, First Out’ methods. These adding and removing methods are often represented by the method names enqueue and dequeue.
To put it in terms of JavaScript, a queue can be thought of as an array with the methods push and shift. In this exercise, we will focus on how to build a Queue from scratch.
// Create our Queue Class
// Queue will have a storage property
// Queue will have two counter variables to identify the first and last keys // Create an Enqueue method
// Enqueue will add values onto the storage// Create a Dequeue method
// Store dequeued value onto a temporary value
// remove the first value
// return the first temporary value
Remember, the dequeue method is supposed to return the dequeued value in much the same way that shift returns the shifted value of an array. Now that we’ve pseudocoded, we’re ready to implement a solution:
// Create our Queue Class
class Queue {
constructor() {
this.storage = {};
this.first = 0;
this.last = 0;
}
}// Create an Enqueue method
Queue.prototype.enqueue = (value) => {
this.storage[this.last++] = value;
} // Create a Dequeue method
Queue.prototype.dequeue = () => {
let temp = this.storage[this.first];
delete this.storage[this.first];
this.first++
return temp;
}
Pretty simple right? Although there may be more intuitive enqueue and dequeue methods out there, the one above allows us to keep our time complexity to constant time, while not making use of any native JavaScript Object methods.
Stack
As the name suggests, a Stack data structure behaves exactly like a stack of things. That is to say, it is a structure defined by its ‘Last In, First Out’ methods. An easy way to think of a stack would be like a stack of dishes — once dishes start piling up you’re not about to wash the oldest dish in the stack, you’re going to want to start at the top (the last one in the stack) and work your way down. These adding and removing methods are often represented by the method names push and pop.
To put it in terms of JavaScript, a stack can be thought of as an array with the push and pop methods. In this exercise, we will focus on how to build a Stack from scratch.
// Create our Stack Class
// Stack will have a storage property
// Stack will have a counter variable to identify the keys
// Stack will have a length property// Create an Push method
// Push will add values onto the end of the storage // Create a Pop method
// Store popped values onto a temporary value
// remove the last value
// return the temporary value
Remember, just like the native pop array method, this pop function will return the popped value. Now that we’ve pseudocoded, we’re ready to implement a solution:
// Create our Stack Class
class Stack {
constructor() {
this.storage = {};
this.count = 0;
this.length = Object.keys(this.storage).length || 0;
}
}// Create a Push method
Stack.prototype.enqueue = (value) => {
this.storage[this.last++] = value;
}// Create a Pop method
Stack.prototype.dequeue = () => {
let temp = this.storage[--this.length];
delete this.storage[this.length];
return temp;
}
This example shows just how we can utilize existing Object methods in order to implement the stack, however there are plenty of other ways of implementing a stack without using these native methods.
Recap:
- Data Structures are ways of storing data efficiently and effectively
- Basic Data Structures include Queues (‘FIFO) and Stacks (‘LIFO)
- Both Queues and Stacks utilize adding and removing methods
- Queues can be thought of as a waiting in line, while Stacks can be thought of as a stack of dishes
This is Part I of a multi-part series on Data Structures. If you’re interested in continuing on with the series on Data Structures and learning about Linked Lists, click here.