Queue Data Structure

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.

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.

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.

Add an item to the queue; The method should accept the item and should not return anything (void)

Remove an item from the queue. The method does not accept any argument and should remove the first (oldest) item from the queue.

Check if the queue is empty. The method does not accept any argument and returns a boolean value.

Check the length of the queue. If the queue is empty, the method returns 0. Otherwise, the length of the array will be returned.

Returns the first (oldest) item from the queue. If the queue is empty, it should return undefined.

As we know the requirements for the queue, we can create a type definition first to make our lives easier later in the process.

// as we want to support various item types, we are making our type `CreateQueueReturnType` generic by accepting a `T` type variable
type CreateQueueReturnType<T> = {
  // add a new item to the queue, do not return anything
  enqueue: (item: T) => void
  // remove the first (oldest) item from the queue, do not return anything
  dequeue: () => void
  // check if queue is empty
  isEmpty: () => boolean
  // check the length of the queue
  length: number
  // retrieve the first (oldest) item from the queue
  peek: () => T
}

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.

// `createQueue` factory function accepts generic `T` type variable
// `T` type variable will be used within `CreateQueueReturnType` and inside of factory function
export function createQueue<T>(): CreateQueueReturnType<T> {
  // the queue itself will be an array of items
  // the type of item is dynamic, controlled by the `T` type variable
  const queue: Array<T> = []

  return {
    enqueue() {},
    dequeue() {},
    isEmpty() {},
    // we need to use `get` to access the latest `length` property of the queue
    get length() {},
    peek() {},
  }
}

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.

import { createQueue } from './queue'

describe('queue', () => {
  const queue = createQueue<string>()

  it('should be empty initially', () => {
    // initially queue is empty
    expect(queue.length).toBe(0)
    expect(queue.isEmpty()).toBe(true)
  })

  it('should enqueue and dequeue', () => {
    // enqueue (add) 'First item' to the queue
    queue.enqueue('First item')
    expect(queue.length).toBe(1)
    expect(queue.isEmpty()).toBe(false)
    expect(queue.peek()).toBe('First item')

    // enqueue (add) 'Second item' to the queue
    queue.enqueue('Second item')
    expect(queue.length).toBe(2)
    expect(queue.isEmpty()).toBe(false)
    // queue is FIFO (first in, first out) data structure
    expect(queue.peek()).toBe('First item')

    // dequeue (remove) 'First item' from the queue
    queue.dequeue()
    expect(queue.length).toBe(1)
    expect(queue.isEmpty()).toBe(false)
    expect(queue.peek()).toBe('Second item')

    // dequeue (remove) 'Second item' from the queue
    queue.dequeue()
    expect(queue.length).toBe(0)
    expect(queue.isEmpty()).toBe(true)
    expect(queue.peek()).toBe(undefined)
  })
})

All tests are failing, but that is the process of test-driven-development. Now, let's implement methods to fix the failing tests.

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    enqueue(item: T) {
      // `unshift` inserts an item at the start of our queue
      queue.unshift(item)
    },
    dequeue() {},
    isEmpty() {},
    get length() {},
    peek() {},
  }
}

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    enqueue(item: T) {
      // `unshift` method inserts an item at the start of our queue
      queue.unshift(item)
    },
    dequeue() {
      // `pop` method removes the last item from our queue
      queue.pop()
    },
    isEmpty() {},
    get length() {},
    peek() {},
  }
}

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    enqueue(item: T) {
      // `unshift` inserts an item at the start of our queue
      queue.unshift(item)
    },
    dequeue() {
      // `pop` method removes the last item from our queue
      queue.pop()
    },
    isEmpty() {
      // checks if queue is empty and returns corresponding `boolean` value
      return queue.length === 0
    },
    get length() {},
    peek() {},
  }
}

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    enqueue(item: T) {
      // `unshift` inserts an item at the start of our queue
      queue.unshift(item)
    },
    dequeue() {
      // `pop` method removes the last item from our queue
      queue.pop()
    },
    isEmpty() {
      // checks if queue is empty and returns corresponding `boolean` value
      return queue.length === 0
    },
    get length() {
      // returns length (number of items) of the queue
      return queue.length
    },
    peek() {},
  }
}

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    enqueue(item: T) {
      // `unshift` inserts an item at the start of our queue
      queue.unshift(item)
    },
    dequeue() {
      // `pop` method removes the last item from our queue
      queue.pop()
    },
    isEmpty() {
      // checks if queue is empty and returns corresponding `boolean` value
      return queue.length === 0
    },
    get length() {
      // returns length (number of items) of the queue
      return queue.length
    },
    peek() {
      // returns first (oldest) queue item
      return queue[queue.length - 1]
    },
  }
}

type CreateQueueReturnType<T> = {
  dequeue: () => void
  enqueue: (item: T) => void
  isEmpty: () => boolean
  length: number
  peek: () => T
}

export function createQueue<T>(): CreateQueueReturnType<T> {
  const queue: Array<T> = []

  return {
    dequeue() {
      queue.pop()
    },
    enqueue(item: T) {
      queue.unshift(item)
    },
    isEmpty() {
      return queue.length === 0
    },
    get length() {
      return queue.length
    },
    peek() {
      return queue[queue.length - 1]
    },
  }
}

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