Queue Data Structure
August 15, 2022Disclaimer
This article focuses solely on the "simple queue"; There are different types of queues (circular, priority, double-ended) that might be covered in future articles.
Introduction
The queue is a linear data structure that follows a specific order of how actions are executed - FIFO (First In, First Out).
You can imagine this data structure as a line of people waiting to get something. A person who waits for the longest will be served first.
Queue operations
The queue has a few basic operations, described below. It does not mean you cannot add any other method if you need one. The most common method that won't be implemented in this article is checking the newest item added to the queue.
enqueue
Add an item to the queue; The method should accept the item and should not return anything (void
)
dequeue
Remove an item from the queue. The method does not accept any argument and should remove the first (oldest) item from the queue.
isEmpty
Check if the queue is empty. The method does not accept any argument and returns a boolean value.
length
Check the length of the queue. If the queue is empty, the method returns 0
. Otherwise, the length of the array will be returned.
peek
Returns the first (oldest) item from the queue. If the queue is empty, it should return undefined
.
Implementation
TypeScript definition
As we know the requirements for the queue
, we can create a type definition first to make our lives easier later in the process.
1// as we want to support various item types, we are making our type `CreateQueueReturnType` generic by accepting a `T` type variable2type CreateQueueReturnType<T> = {3 // add a new item to the queue, do not return anything4 enqueue: (item: T) => void5 // remove the first (oldest) item from the queue, do not return anything6 dequeue: () => void7 // check if queue is empty8 isEmpty: () => boolean9 // check the length of the queue10 length: number11 // retrieve the first (oldest) item from the queue12 peek: () => T13}
Factory function implementation
We will need to create a new factory function to create a queue.
Factory function is any function that is not a class nor constructor and returns an object. Every JavaScript function can return an object - if it does without a
new
keyword - it is a factory function.
1// `createQueue` factory function accepts generic `T` type variable2// `T` type variable will be used within `CreateQueueReturnType` and inside of factory function3export function createQueue<T>(): CreateQueueReturnType<T> {4 // the queue itself will be an array of items5 // the type of item is dynamic, controlled by the `T` type variable6 const queue: Array<T> = []78 return {9 enqueue() {},10 dequeue() {},11 isEmpty() {},12 // we need to use `get` to access the latest `length` property of the queue13 get length() {},14 peek() {},15 }16}
Adding tests
As we have the createQueue
function specified, as well as return types of factory function, we can write a test suite before implementing methods of that function.
1import { createQueue } from './queue'23describe('queue', () => {4 const queue = createQueue<string>()56 it('should be empty initially', () => {7 // initially queue is empty8 expect(queue.length).toBe(0)9 expect(queue.isEmpty()).toBe(true)10 })1112 it('should enqueue and dequeue', () => {13 // enqueue (add) 'First item' to the queue14 queue.enqueue('First item')15 expect(queue.length).toBe(1)16 expect(queue.isEmpty()).toBe(false)17 expect(queue.peek()).toBe('First item')1819 // enqueue (add) 'Second item' to the queue20 queue.enqueue('Second item')21 expect(queue.length).toBe(2)22 expect(queue.isEmpty()).toBe(false)23 // queue is FIFO (first in, first out) data structure24 expect(queue.peek()).toBe('First item')2526 // dequeue (remove) 'First item' from the queue27 queue.dequeue()28 expect(queue.length).toBe(1)29 expect(queue.isEmpty()).toBe(false)30 expect(queue.peek()).toBe('Second item')3132 // dequeue (remove) 'Second item' from the queue33 queue.dequeue()34 expect(queue.length).toBe(0)35 expect(queue.isEmpty()).toBe(true)36 expect(queue.peek()).toBe(undefined)37 })38})
All tests are failing, but that is the process of test-driven-development. Now, let's implement methods to fix the failing tests.
Implement enqueue
1export function createQueue<T>(): CreateQueueReturnType<T> {2 const queue: Array<T> = []34 return {5 enqueue(item: T) {6 // `unshift` inserts an item at the start of our queue7 queue.unshift(item)8 },9 dequeue() {},10 isEmpty() {},11 get length() {},12 peek() {},13 }14}
Implement dequeue
1export function createQueue<T>(): CreateQueueReturnType<T> {2 const queue: Array<T> = []34 return {5 enqueue(item: T) {6 // `unshift` method inserts an item at the start of our queue7 queue.unshift(item)8 },9 dequeue() {10 // `pop` method removes the last item from our queue11 queue.pop()12 },13 isEmpty() {},14 get length() {},15 peek() {},16 }17}
Implement isEmpty
1export function createQueue<T>(): CreateQueueReturnType<T> {2 const queue: Array<T> = []34 return {5 enqueue(item: T) {6 // `unshift` inserts an item at the start of our queue7 queue.unshift(item)8 },9 dequeue() {10 // `pop` method removes the last item from our queue11 queue.pop()12 },13 isEmpty() {14 // checks if queue is empty and returns corresponding `boolean` value15 return queue.length === 016 },17 get length() {},18 peek() {},19 }20}
Implement length getter
1export function createQueue<T>(): CreateQueueReturnType<T> {2 const queue: Array<T> = []34 return {5 enqueue(item: T) {6 // `unshift` inserts an item at the start of our queue7 queue.unshift(item)8 },9 dequeue() {10 // `pop` method removes the last item from our queue11 queue.pop()12 },13 isEmpty() {14 // checks if queue is empty and returns corresponding `boolean` value15 return queue.length === 016 },17 get length() {18 // returns length (number of items) of the queue19 return queue.length20 },21 peek() {},22 }23}
Implement peek
1export function createQueue<T>(): CreateQueueReturnType<T> {2 const queue: Array<T> = []34 return {5 enqueue(item: T) {6 // `unshift` inserts an item at the start of our queue7 queue.unshift(item)8 },9 dequeue() {10 // `pop` method removes the last item from our queue11 queue.pop()12 },13 isEmpty() {14 // checks if queue is empty and returns corresponding `boolean` value15 return queue.length === 016 },17 get length() {18 // returns length (number of items) of the queue19 return queue.length20 },21 peek() {22 // returns first (oldest) queue item23 return queue[queue.length - 1]24 },25 }26}
Complete Implementation
1type CreateQueueReturnType<T> = {2 dequeue: () => void3 enqueue: (item: T) => void4 isEmpty: () => boolean5 length: number6 peek: () => T7}89export function createQueue<T>(): CreateQueueReturnType<T> {10 const queue: Array<T> = []1112 return {13 dequeue() {14 queue.pop()15 },16 enqueue(item: T) {17 queue.unshift(item)18 },19 isEmpty() {20 return queue.length === 021 },22 get length() {23 return queue.length24 },25 peek() {26 return queue[queue.length - 1]27 },28 }29}
Conclusion
In today's article, we've implemented the queue data structure. Our implementation is both type-safe and covered by tests so that we can build additional methods on top of our simple queue.
Have you found any bugs, or do you have any questions? Feel free to reach out on Twitter.
If you do not want to miss the next article, click on the follow button!