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.

TypeScript
Copy to clipboard
1// Create a queue and add items
2let queue: string[] = [];
3queue.push("Apple");
4queue.push("Banana");
5queue.push("Cherry");
6
7// Remove an item
8console.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.

TypeScript
Copy to clipboard
1// Create a queue and enqueue items
2let queue: string[] = [];
3queue.push("Item 1");
4queue.push("Item 2");
5
6// Check if the queue is non-empty, then dequeue an item
7if (queue.length > 0) {
8    console.log(queue.shift());  // Expects "Item 1"
9}

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.

A deque, or "double-ended queue," allows the addition and removal of items from both ends. We can utilize TypeScript array methods to achieve this functionality, using push() for the right end and unshift() for the left, while pop() and shift() remove elements from the right and left ends, respectively.

TypeScript
Copy to clipboard
1// Create a deque and add items
2let deque: string[] = [];
3deque.push("Middle");
4deque.push("Right end");
5deque.unshift("Left end");
6
7// Remove an item
8console.log(deque.pop());  // Expects "Right end"
9
10// Remove an item from the left
11console.log(deque.shift()); // Expects "Left end"

While arrays in TypeScript do not have a built-in rotation method, we can implement rotation manually using a loop and appropriate array methods.

TypeScript
Copy to clipboard
1// Create a deque
2let deque: string[] = [];
3deque.push("Apple");
4deque.push("Banana");
5deque.push("Cherry");
6
7// Rotate the deque to the right by 1 place
8for (let i = 0; i < 1; i++) {
9    deque.unshift(deque.pop() as string);
10}
11
12console.log(deque);  // Expects ["Cherry", "Apple", "Banana"]

Here, the loop shifts all items to the right by one position.

Deque Operations with Arrays:

• Add to the End (push): Adding an element to the end with push() is $O(1)$.
• Add to the Front (unshift): Inserting an element at the start with unshift() has a time complexity of $O(n)$, as it requires shifting all existing elements one position to the right.
• Remove from the End (pop): Removing the last element with pop() is $O(1)$.
• Remove from the Front (shift): Removing the first element with shift() is $O(n)$ for the same reason as the dequeue operation in queues—it involves shifting elements.

While arrays work well for deques in smaller datasets, the $O(n)$ cost for unshift() and shift() can become a bottleneck for larger deques. For applications requiring frequent additions and removals at both ends in constant time, a doubly linked list may be preferable. Doubly linked lists can provide $O(1)$ complexity for additions and removals at both ends by directly linking nodes without shifting.

Congratulations on finishing this detailed study of queues and deques using TypeScript! You've learned their operating principles and how to construct and manipulate them with arrays. Moving forward, we aim to explore additional data structures similar to these. This opens a world of opportunities for expressing your ideas and solving complex problems. Are you ready for forthcoming practice exercises to consolidate this new knowledge? Let's continue our exploration!