In my last post I discussed creating a binary search tree with ES6. In this post I’ll be discussing a different type of data structure: queues. Once again I’ll be leaning on Data Structures and Algorithms With JavaScript by Michael McMillan for insight.
What is a queue?
A queue is a linear data structure that stores items in the order in which they are generated. A queue is rather like a list where items are added to the end and removed from the beginning. This type of data structure is known as a “first-in, first-out” data structure. It may help to think of a queue as a line at a grocery store where customers join at the back and check out at the front.
Creating a queue
Creating a queue requires a single class. The class should have one property for storing the data along with several standard methods for working with the data, e.g., adding items to the queue, removing items from the queue and querying the queue. Exact property and method names may vary but such a class may be designed as follows:
// A basic queue
class Queue {
// Creates the data store
constructor(dataStore = []) {
this.dataStore = dataStore;
}
// Adds an element to the back of the queue
push(element) {
this.dataStore.push(element);
}
// Removes an element from the front of the queue
shift() {
this.dataStore.shift();
}
// Inspects the first element in the queue
peekFront() {
return this.dataStore[0];
}
// Inspects the last element in the queue
peekBack() {
return this.dataStore[this.dataStore.length - 1];
}
// Checks to see if the queue is empty
isEmpty() {
return !this.dataStore.length;
}
// Outputs the contents of the queue
toString() {
let str = '';
for (var i = 0; i < this.dataStore.length; i++) {
str += `${this.dataStore[i]}\n`;
}
return str;
}
}
This simple class essentially proxies native array properties and methods in order to work with the data. For example the push() method that adds items to the queue proxies Array.prototype.push(); the shift() method that removes items from the queue proxies Array.prototype.shift(); and the isEmpty() method that checks to see if the queue is empty proxies Array.length. The class also has methods for inspecting the first and last elements in the queue (peekFront() and peekBack()), and outputting the contents of the queue (toString()).
Let’s now create a queue and add some items to it:
const queue = new Queue();
queue.push('George Washington');
queue.push('John Adams');
queue.push('Thomas Jefferson');
queue.push('James Madison');
queue.push('James Monroe');
Outputting the contents of the queue should return the following:
George Washington John Adams Thomas Jefferson James Madison James Monroe
Notice how each new item has been added to the back of the queue?
Let’s now remove an element from the queue using queue.shift(); and see how this affects the output:
John Adams Thomas Jefferson James Madison James Monroe
Notice how the first item has been removed from front of the queue?
Let’s now inspect the first and last items in the queue:
queue.peekFront(); // John Adams queue.peekBack(); // James Monroe
So far, so predictable.
Creating a double-ended queue
A more specific kind of queue is called a double-ended queue or “deque” (pronounced “deck”). In a deque items can be added to and removed from both the front and the back of the queue. Creating a deque requires us to extend our basic queue with a couple of extra methods: an unshift() method for adding items to the front of the queue and a pop() method for removing items from the back of the queue. Again these methods proxy the native array methods Array.prototype.unshift() and Array.prototype.pop().
class Deque extends Queue {
...
// Adds an element to the front of the queue
unshift(element) {
this.dataStore.unshift(element);
}
// Removes an element from the back of the queue
pop() {
this.dataStore.pop();
}
...
}
Let’s now create a deque and add some items to it:
const deque = new Deque();
deque.unshift('George Washington');
deque.unshift('John Adams');
deque.unshift('Thomas Jefferson');
deque.unshift('James Madison');
deque.unshift('James Monroe');
Outputting the contents of the queue should return the following:
James Monroe James Madison Thomas Jefferson John Adams George Washington
Notice how adding the items to the front of the queue affects the order?
Let’s now remove an item from the queue with deque.pop(); and see how this affects the output:
James Monroe James Madison Thomas Jefferson John Adams
Notice how the item has been removed from the back of the queue?
Let’s now inspect the first and last elements in the queue:
deque.peekFront(); // James Monroe deque.peekBack(); // John Adams
Straightforward enough!
Creating a priority queue
Another more specific kind of queue is called a priority queue. In a priority queue items are removed based on a manually defined “priority” as opposed to an automatically defined position (first or last).
As an example let’s take the line of succession to the U.S. presidency, in which the successor to the office is based on a set order of priority. A simple data model for a successor could look like this:
office: String // office to which successor belongs priority: Number // order of priority
Creating a line of succession class once again requires us to extend our basic queue with a few methods: a special implementation of the shift() method for removing items from the queue, a special implementation of the toString() method for outputting the contents of the queue, and a count() method for returning the number of items in the queue.
class LineOfSuccession extends Queue {
// Removes an element from the queue based on priority
shift() {
let order = 0;
for (var i = 1; i < this.count(); ++i) {
if (this.dataStore[i].order < this.dataStore[order].order) {
order = i;
}
}
return this.dataStore.splice(order, 1);
}
// Outputs the contents of the queue
toString() {
let retStr = ``;
for (var i = 0; i < this.dataStore.length; i++) {
retStr += `${this.dataStore[i].office}\n`;
}
console.log(retStr);
}
}
The shift() method works by returning the item with the highest priority from the queue. It does this by looping through all the items in the queue and upon encountering a higher priority item than the current highest priority item making the former the new highest priority item.
Let’s now create a line of succession:
const los = new LineOfSuccession([
{office: 'Speaker of the House of Representatives', order: 2},
{office: 'Vice President', order: 1},
{office: 'Secretary of the Treasury', order: 5},
{office: 'Secretary of State', order: 4},
{office: 'President pro tempore of the Senate', order: 3}
]);
Notice how this time we’re passing the data into the queue’s constructor rather than adding the items manually with queue.push()? Also notice how the data is in no particular order as it’s being passed in? Outputting the contents of the queue should return the following:
Speaker of the House of Representatives Vice President Secretary of the Treasury Secretary of State President pro tempore of the Senate
Now let’s create a successor variable and start pulling (removing) successors from the queue.
let successor; successor = los.shift(); successor[0].office // Vice President; successor = los.shift(); successor[0].office // Speaker of the House of Representatives; successor = los.shift(); successor[0].office // President pro tempore of the Senate; successor = los.shift(); successor[0].office // Secretary of State; successor = los.shift(); successor[0].office // Secretary of the Treasury;
Notice how each successor is being removed from the queue based on priority?
Conclusion
In this post I’ve described the basic idea of the queue data structure and, to see how it works in practice, used ES6 to implement a few different kinds of queue: a basic queue, a double-ended queue and a priority queue. The main differences between these kinds of queue can be summarized as follows:
- In a basic queue items are added to the back and removed from the front.
- In a doubled-ended queue items can be added to and removed from both the front and the back.
- In a priority queue items are removed based on a manually defined priority.