Queue Data Structure

August 15, 2022

Disclaimer

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.

index.ts
1// as we want to support various item types, we are making our type `CreateQueueReturnType` generic by accepting a `T` type variable
2type CreateQueueReturnType<T> = {
3 // add a new item to the queue, do not return anything
4 enqueue: (item: T) => void
5 // remove the first (oldest) item from the queue, do not return anything
6 dequeue: () => void
7 // check if queue is empty
8 isEmpty: () => boolean
9 // check the length of the queue
10 length: number
11 // retrieve the first (oldest) item from the queue
12 peek: () => T
13}

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.

index.ts
1// `createQueue` factory function accepts generic `T` type variable
2// `T` type variable will be used within `CreateQueueReturnType` and inside of factory function
3export function createQueue<T>(): CreateQueueReturnType<T> {
4 // the queue itself will be an array of items
5 // the type of item is dynamic, controlled by the `T` type variable
6 const queue: Array<T> = []
7
8 return {
9 enqueue() {},
10 dequeue() {},
11 isEmpty() {},
12 // we need to use `get` to access the latest `length` property of the queue
13 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.

index.test.ts
1import { createQueue } from './queue'
2
3describe('queue', () => {
4 const queue = createQueue<string>()
5
6 it('should be empty initially', () => {
7 // initially queue is empty
8 expect(queue.length).toBe(0)
9 expect(queue.isEmpty()).toBe(true)
10 })
11
12 it('should enqueue and dequeue', () => {
13 // enqueue (add) 'First item' to the queue
14 queue.enqueue('First item')
15 expect(queue.length).toBe(1)
16 expect(queue.isEmpty()).toBe(false)
17 expect(queue.peek()).toBe('First item')
18
19 // enqueue (add) 'Second item' to the queue
20 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 structure
24 expect(queue.peek()).toBe('First item')
25
26 // dequeue (remove) 'First item' from the queue
27 queue.dequeue()
28 expect(queue.length).toBe(1)
29 expect(queue.isEmpty()).toBe(false)
30 expect(queue.peek()).toBe('Second item')
31
32 // dequeue (remove) 'Second item' from the queue
33 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

index.ts
1export function createQueue<T>(): CreateQueueReturnType<T> {
2 const queue: Array<T> = []
3
4 return {
5 enqueue(item: T) {
6 // `unshift` inserts an item at the start of our queue
7 queue.unshift(item)
8 },
9 dequeue() {},
10 isEmpty() {},
11 get length() {},
12 peek() {},
13 }
14}

Implement dequeue

index.ts
1export function createQueue<T>(): CreateQueueReturnType<T> {
2 const queue: Array<T> = []
3
4 return {
5 enqueue(item: T) {
6 // `unshift` method inserts an item at the start of our queue
7 queue.unshift(item)
8 },
9 dequeue() {
10 // `pop` method removes the last item from our queue
11 queue.pop()
12 },
13 isEmpty() {},
14 get length() {},
15 peek() {},
16 }
17}

Implement isEmpty

index.ts
1export function createQueue<T>(): CreateQueueReturnType<T> {
2 const queue: Array<T> = []
3
4 return {
5 enqueue(item: T) {
6 // `unshift` inserts an item at the start of our queue
7 queue.unshift(item)
8 },
9 dequeue() {
10 // `pop` method removes the last item from our queue
11 queue.pop()
12 },
13 isEmpty() {
14 // checks if queue is empty and returns corresponding `boolean` value
15 return queue.length === 0
16 },
17 get length() {},
18 peek() {},
19 }
20}

Implement length getter

index.ts
1export function createQueue<T>(): CreateQueueReturnType<T> {
2 const queue: Array<T> = []
3
4 return {
5 enqueue(item: T) {
6 // `unshift` inserts an item at the start of our queue
7 queue.unshift(item)
8 },
9 dequeue() {
10 // `pop` method removes the last item from our queue
11 queue.pop()
12 },
13 isEmpty() {
14 // checks if queue is empty and returns corresponding `boolean` value
15 return queue.length === 0
16 },
17 get length() {
18 // returns length (number of items) of the queue
19 return queue.length
20 },
21 peek() {},
22 }
23}

Implement peek

index.ts
1export function createQueue<T>(): CreateQueueReturnType<T> {
2 const queue: Array<T> = []
3
4 return {
5 enqueue(item: T) {
6 // `unshift` inserts an item at the start of our queue
7 queue.unshift(item)
8 },
9 dequeue() {
10 // `pop` method removes the last item from our queue
11 queue.pop()
12 },
13 isEmpty() {
14 // checks if queue is empty and returns corresponding `boolean` value
15 return queue.length === 0
16 },
17 get length() {
18 // returns length (number of items) of the queue
19 return queue.length
20 },
21 peek() {
22 // returns first (oldest) queue item
23 return queue[queue.length - 1]
24 },
25 }
26}

Complete Implementation

index.ts
1type CreateQueueReturnType<T> = {
2 dequeue: () => void
3 enqueue: (item: T) => void
4 isEmpty: () => boolean
5 length: number
6 peek: () => T
7}
8
9export function createQueue<T>(): CreateQueueReturnType<T> {
10 const queue: Array<T> = []
11
12 return {
13 dequeue() {
14 queue.pop()
15 },
16 enqueue(item: T) {
17 queue.unshift(item)
18 },
19 isEmpty() {
20 return queue.length === 0
21 },
22 get length() {
23 return queue.length
24 },
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!

Share this post on Twitter