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.