Leetcode 1670: Design Front Middle Back Queue
Design a queue that supports operations at the front, middle, and back. Implement the
FrontMiddleBackQueue class with methods for adding and removing elements from these positions.Problem
Approach
Steps
Complexity
Input: The input consists of a series of commands to initialize the queue and perform operations on it.
Example: ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[ ], [10], [20], [30], [40], [], [], [], [], []]
Constraints:
• 1 <= val <= 10^9
• At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.
Output: The output consists of the results of the `pop` operations. For each `pop` operation, return the value removed from the queue or `-1` if the queue is empty.
Example: [null, null, null, null, null, 10, 30, 40, 20, -1]
Constraints:
• Each `pop` operation returns the element removed or `-1` if the queue is empty.
Goal: Implement a queue that allows insertion and removal of elements at the front, middle, and back efficiently.
Steps:
• Use two deques to manage the front and back operations efficiently.
• The middle position is calculated dynamically based on the size of the deques.
• For each `pop` operation, handle the front, middle, or back removal appropriately based on the current state of the queue.
Goal: The queue operations should be performed efficiently even with a large number of operations.
Steps:
• The queue must be able to handle up to 1000 operations.
• Operations should be performed with optimal time complexity.
Assumptions:
• The input will always follow the format specified in the examples.
• All input values are valid and within the specified constraints.
• Input: [null, null, null, null, null, 10, 30, 40, 20, -1]
• Explanation: This example demonstrates how each of the operations behaves, including adding elements to the front, middle, and back, and removing them from the front, middle, and back.
Approach: The solution uses two deques to manage the queue's operations efficiently. One deque handles the front and the other handles the back. The middle element is adjusted dynamically based on the size of the two deques.
Observations:
• Operations on the front and back are easy to handle using deques.
• The middle element needs dynamic management to ensure efficient insertion and removal.
• Use two deques to split the queue and balance the middle position.
Steps:
• Initialize two deques for handling the front and back of the queue.
• Use `pushFront`, `pushMiddle`, and `pushBack` methods to manipulate the deques.
• For `popFront`, `popMiddle`, and `popBack`, ensure that elements are removed correctly while maintaining the integrity of the queue.
Empty Inputs:
• Ensure that `pop` operations return `-1` when the queue is empty.
Large Inputs:
• Ensure that the solution performs efficiently with up to 1000 operations.
Special Values:
• Ensure correct behavior when performing operations on a queue of size 1.
Constraints:
• Handle up to 1000 operations.
void a2b() {
if (a.size() <= b.size()) return;
b.push_front(a.back());
a.pop_back();
}
/* keep operations around front of b and back of a */
void b2a() {
if (b.size() <= a.size() + 1) return;
a.push_back(b.front());
b.pop_front();
}
public:
FrontMiddleBackQueue() {}
void pushFront(int val) {
a.push_front(val);
a2b();
}
void pushMiddle(int val) {
a.push_back(val);
a2b();
}
void pushBack(int val) {
b.push_back(val);
b2a();
}
int popFront() {
if(a.empty() && b.empty()) return -1;
int ans;
if(a.empty()) {
ans = b.front();
b.pop_front();
} else {
ans = a.front();
a.pop_front();
b2a();
}
return ans;
}
int popMiddle() {
if(a.empty() && b.empty()) return -1;
int ans;
if(a.size() == b.size()) {
ans = a.back();
a.pop_back();
} else {
ans = b.front();
b.pop_front();
}
return ans;
}
int popBack() {
if(a.empty() && b.empty()) return -1;
int ans = b.back();
b.pop_back();
a2b();
return ans;
}
};
/**
* Your FrontMiddleBackQueue object will be instantiated and called as such:
* FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
* obj->pushFront(val);
* obj->pushMiddle(val);
* obj->pushBack(val);
* int param_4 = obj->popFront();
* int param_5 = obj->popMiddle();
* int param_6 = obj->popBack();
1 : Helper Functions
void a2b() {
Helper function that moves elements from the back of `a` to the front of `b` to balance the size of the deques.
2 : Helper Functions
if (a.size() <= b.size()) return;
Checks if the size of `a` is less than or equal to the size of `b`. If true, no operation is performed.
3 : Helper Functions
b.push_front(a.back());
Moves an element from the back of `a` to the front of `b`.
4 : Helper Functions
a.pop_back();
Removes the element that was just moved from the back of `a`.
5 : Helper Functions
void b2a() {
Helper function that moves elements from the front of `b` to the back of `a`.
6 : Helper Functions
if (b.size() <= a.size() + 1) return;
Checks if the size of `b` is less than or equal to the size of `a` plus 1. If true, no operation is performed.
7 : Helper Functions
a.push_back(b.front());
Moves an element from the front of `b` to the back of `a`.
8 : Helper Functions
b.pop_front();
Removes the element that was just moved from the front of `b`.
9 : Constructor
public:
Access specifier indicating that the following methods are public and can be accessed outside the class.
10 : Constructor
FrontMiddleBackQueue() {}
Constructor for the `FrontMiddleBackQueue` class, initializes the deques `a` and `b`.
11 : Push Operations
void pushFront(int val) {
Method that adds a value to the front of the queue.
12 : Push Operations
a.push_front(val);
Adds the value `val` to the front of deque `a`.
13 : Push Operations
a2b();
Calls the `a2b` helper function to balance the deques.
14 : Push Operations
void pushMiddle(int val) {
Method that adds a value to the middle of the queue.
15 : Push Operations
a.push_back(val);
Adds the value `val` to the back of deque `a`.
16 : Push Operations
a2b();
Calls the `a2b` helper function to balance the deques.
17 : Push Operations
void pushBack(int val) {
Method that adds a value to the back of the queue.
18 : Push Operations
b.push_back(val);
Adds the value `val` to the back of deque `b`.
19 : Push Operations
b2a();
Calls the `b2a` helper function to balance the deques.
20 : Pop Operations
int popFront() {
Method that removes a value from the front of the queue.
21 : Pop Operations
if(a.empty() && b.empty()) return -1;
Checks if both `a` and `b` are empty. If true, returns -1 to indicate that the queue is empty.
22 : Pop Operations
int ans;
Declares a variable `ans` to store the value being removed from the queue.
23 : Pop Operations
if(a.empty()) {
Checks if `a` is empty. If true, removes the front element from `b`.
24 : Pop Operations
ans = b.front();
Assigns the front element of `b` to `ans`.
25 : Pop Operations
b.pop_front();
Removes the front element from `b`.
26 : Pop Operations
} else {
If `a` is not empty, removes the front element from `a`.
27 : Pop Operations
ans = a.front();
Assigns the front element of `a` to `ans`.
28 : Pop Operations
a.pop_front();
Removes the front element from `a`.
29 : Pop Operations
b2a();
Calls the `b2a` helper function to balance the deques.
30 : Pop Operations
return ans;
Returns the value removed from the front of the queue.
Best Case: O(1) for operations when the size of the queue is small.
Average Case: O(1) for `push` and `pop` operations, as deques allow constant time insertions and deletions.
Worst Case: O(1) for all operations.
Description: The time complexity for each operation is O(1), making the solution highly efficient.
Best Case: O(n), as the space complexity depends on the total number of elements.
Worst Case: O(n), where n is the number of elements in the queue.
Description: The space complexity is linear in terms of the number of elements in the queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus