Lesson

10.2Implement Queue using Array

Create a basic queue using an array in JavaScript. A queue is a linear data structure that follows the First In, First Out (FIFO) principle.

Example: Perform the following operations:

Example Inputs

Input

Output

Brute Force Approach

a. Approach

Use a JavaScript array to represent the queue. Add elements to the end of the array using the push() method and remove elements from the front using the shift() method.

b. Steps

Use an array to store the elements of the queue.
To enqueue, add elements to the end of the array using push().
To dequeue, remove the first element of the array using shift().
Return the dequeued element.

c. Time & Space Complexity

Time Complexity:
- Enqueue: O(1) (constant time)
- Dequeue: O(n) (removing the first element shifts all other elements).
Space Complexity: O(n), where n is the number of elements in the queue.

d. Code Snippet

e. Dry Run

For the input:

Enqueue 1: [1]
Enqueue 2: [1, 2]
Dequeue: Remove 1. Remaining queue: [2]
Output: 1

Efficient Approach

Note - This approach is good in terms of time complexity, but it is not a good approach in terms of space complexity. Because, when dequeue is called, we only move the pointer and never remove the element from the array. So there will be unused space in the array. which will cause memory leak.

a. Approach

Use two pointers (front and rear) to track the position of the first and last elements in the queue. This avoids the costly operation of shifting elements in the array during dequeue.

b. Steps

Initialize a front pointer at the start and a rear pointer at the end of the queue.
To enqueue, add an element at the rear pointer and move the pointer forward.
To dequeue, return the element at the front pointer and move it forward.

c. Time & Space Complexity

Time Complexity:
- Enqueue: O(1) (constant time)
- Dequeue: O(1) (constant time)
Space Complexity: O(n), where n is the number of elements in the queue.

d. Code Snippet

e. Dry Run

For the input:

Enqueue 1: rear = 1, front = 0, items = [1]
Enqueue 2: rear = 2, front = 0, items = [1, 2]
Dequeue: Return items[front], increment front. Output: 1

Complexity Analysis

Approach	Enqueue (Time)	Dequeue (Time)	Space
Brute Force	O(1)	O(n)	O(n)
Efficient Approach	O(1)	O(1)	O(n)

Conclusion

The brute force approach is simple to implement but inefficient for dequeue operations due to the O(n) time complexity caused by array shifting.
The efficient approach uses pointers to avoid array shifts, resulting in O(1) dequeue operations. However, this can lead to extra memory usage as the elements are not removed from the array, only the pointer is moved.
Choosing the efficient approach is essential for scenarios where the queue needs to handle a large number of operations efficiently.

Previous Next