Queues and Deques in TypeScript: Concepts and Implementations

Welcome to our exploration of queues and deques. These structures are pivotal in programming, managing everything from system processes to printer queues. In this lesson, our goal is to understand and implement queues and deques using TypeScript. Let's dive in!

A queue, much like waiting in line at a store, operates on the "First In, First Out," or FIFO, principle. Using TypeScript, we can implement queues with arrays. This involves methods such as push() for adding items and shift() for removing them.

// Create a queue and add items
let queue: string[] = [];
queue.push("Apple");
queue.push("Banana");
queue.push("Cherry");

// Remove an item
console.log(queue.shift());  // Expects "Apple"

The dequeued item, "Apple", was the first item inserted, showcasing the FIFO nature of queues.

Before calling shift(), which removes the first element from the queue, it's important to verify that the queue isn't empty. This check (queue.length > 0) prevents errors that occur when trying to remove an element from an empty array, as shift() returns undefined when the array is empty.

// Create a queue and enqueue items
let queue: string[] = [];
queue.push("Item 1");
queue.push("Item 2");

// Check if the queue is non-empty, then dequeue an item
if (queue.length > 0) {
    console.log(queue.shift());  // Expects "Item 1"
}

In TypeScript, arrays are often chosen for implementing queues due to their simple syntax and the availability of built-in methods like push() and shift() for adding and removing elements. However, the choice of arrays comes with trade-offs in terms of time complexity and performance, especially for larger data sets.

• Enqueue (push): Adding an element to the end of an array with push() has a time complexity of $O(1)$, as this operation typically only appends the element without moving existing elements.
• Dequeue (shift): Removing the first element from the array with shift() has a time complexity of $O(n)$, as it requires shifting each remaining element one index to the left. This becomes inefficient as the queue size grows, leading to potential performance issues in large-scale applications.
• Is Empty Check: Checking if an array is empty (e.g., queue.length === 0) is an $O(1)$ operation, as it only requires reading the array’s length property.

For small or moderate-sized queues, arrays are efficient and convenient. However, in performance-critical applications or large queues, the $O(n)$ complexity of shift() can become problematic due to the need to shift elements with each dequeue. In such cases, a linked list can be a better choice, as it can provide $O(1)$ time complexity for both enqueue and dequeue operations without shifting elements.