Queues : From Waiting in Line to Queuing Up

I don’t really enjoy waiting but I understand the importance of queues and their role in real life. Queues are important for managing crowds. They provide structure and order, helping businesses serve customers and visitors better. Waiting in line can be frustrating, but it's necessary. Queues are used in banks, hospitals, and airports to manage traffic and ensure that everyone is served in an orderly manner.

Web development uses queues to manage multiple user requests simultaneously. Queues organize requests into a queue and the server processes them in the order they were received. This ensures that each request is handled in a timely manner without overwhelming the server. Queues are critical in ensuring that web applications can handle multiple requests without experiencing performance issues, allowing web applications to run smoothly and provide a positive user experience.

Queues can be used for task management in web development. For example, a queue can manage background jobs such as sending emails or processing images. This ensures that these tasks are executed in a specific order, and resources are allocated efficiently. Additionally, queues can be used to implement a print spooler, where print jobs are added to a queue and printed in the order they were received. They are also used in network routing algorithms, where packets are added to a queue and sent in the order they were received.

Furthermore, queues are often used in multi-threaded programs to synchronize access to shared resources. By using a queue to manage access to a shared resource, we can ensure that only one thread has access to the resource at a time and prevent conflicts, thus ensuring the resource is used correctly.

Operations on a queue

A queue is a data structure that supports two operations formally: enqueue and dequeue. The enqueue operation adds a new element to the back of the queue, while the dequeue operation removes the element from the front of the queue and returns it. This is a first-in, first-out (FIFO) data structure, meaning that the oldest elements are at the front of the queue and the newest elements are at the back.

Queues in an Array

Queues can be implemented using an array. In this implementation, the front of the queue is represented by the first element in the array, and the back of the queue is represented by the last element in the array. When an element is enqueued, it is added to the back of the queue. When an element is dequeued, the first element in the array is removed and returned,

When you take an element out of a queue made with an array, there will be an empty space left at the front of the queue. This space cannot be used for new elements, even though it's still part of the queue. To not waste space, some implementations use a circular buffer. In this type of buffer, the last element in the array goes back to the beginning. This way, the queue can use the empty space at the front of the array again when elements are dequeued.

// empty queue
[]
// queue elements
[1,]
...,
[1,2,3,4,5,6,7,8]


// dequeue an element
[ ,2,3,4,5,6,7,8]
// dequeue an element
[ , ,3,4,5,6,7,8]
// dequeue an element
[ , , ,4,5,6,7,8]

Queue with Linked List Implementation in TypeScript

Let's dive into how we can use a linked list to create a queue.

We have two classes: Node and Queue. Node is a simple class that holds the node value and has two pointers: next and prev. These pointers point to the next and previous nodes in the linked list. If you want more on how to build a linked list check out my other blog: Dynamic data structures from Arrays to Linked List

class Node {
  value: string;
  next: Node | null;
  prev: Node | null;
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}
class Queue {
  head: Node | null;
  tail : Node | null;
  length: number;
  constructor() {
    this.head = null;
    this.length = 0;
  }

The Queue used to represent a queue and has three important parts: head, tail, and length. The head property points to the first item in the queue, the tail property points to the last item, and length to keep track of items in the queue.

enqueue adds a new element to the end of the queue. If empty, the new node becomes the head and tail. If not, the new node becomes the head and the previous head becomes the next node.

  enqueue(value) {
    let newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.length += 1;
      this.tail = newNode
      return newNode;
    }else{
        this.tail = newNode
        this.head.prev = newNode
        newNode.next = this.head
        this.head = newNode
        this.length +=1;
    }
  }

The dequeue method removes the first element from the queue and returns its value. It checks if the queue is empty first. If it is empty, it returns null. Otherwise, it removes the first element by setting the next node as the new head and decreasing the length by 1.

  dequeue() {
    if (!this.head) {
      return null;
    }
    let currentNode = this.head;
    this.head = currentNode.next;
    this.head.prev = null;
    this.length -= 1;
    return currentNode.value;
  }

Time and Space Complexity of a Queue

The time and space complexity of a queue is O(1) for enqueue and dequeue operations. The enqueue operation takes constant time because we only need to add an element to the end of the queue.

Similarly, the dequeue operation takes constant time because we only need to remove the first element from the front of the queue. The space complexity of a queue is also O(1) because we only use a constant amount of memory to store the queue elements, regardless of the number of elements in the queue.

Related Articles