At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.
Solutions
Solution 1: Two Deques
We use two deques, where $q_1$ stores the first half, and $q_2$ stores the second half. The rebalance function is used to maintain the balance between the two queues, i.e., keeping the length of $q_2$ greater than or equal to the length of $q_1$, and the difference in length does not exceed $1$.
In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to $q_1$ or $q_2$, and call the rebalance function.
For the popFront function, we need to check whether $q_1$ and $q_2$ are empty. If both are empty, return $-1$. Otherwise, we need to check whether $q_1$ is empty. If not, pop the front element of $q_1$, otherwise pop the front element of $q_2$, and call the rebalance function.
For the popMiddle function, we need to check whether $q_1$ and $q_2$ are empty. If both are empty, return $-1$. Otherwise, we need to check whether the lengths of $q_1$ and $q_2$ are equal. If they are equal, pop the last element of $q_1$, otherwise pop the front element of $q_2$, and call the rebalance function.
For the popBack function, we only need to check whether $q_2$ is empty. If it is empty, return $-1$. Otherwise, pop the last element of $q_2$, and call the rebalance function.
The time complexity of the above operations is $O(1)$, and the space complexity is $O(n)$, where $n$ is the number of elements in the queue.
classFrontMiddleBackQueue:def__init__(self):self.q1=deque()self.q2=deque()defpushFront(self,val:int)->None:self.q1.appendleft(val)self.rebalance()defpushMiddle(self,val:int)->None:self.q1.append(val)self.rebalance()defpushBack(self,val:int)->None:self.q2.append(val)self.rebalance()defpopFront(self)->int:ifnotself.q1andnotself.q2:return-1ifself.q1:val=self.q1.popleft()else:val=self.q2.popleft()self.rebalance()returnvaldefpopMiddle(self)->int:ifnotself.q1andnotself.q2:return-1iflen(self.q1)==len(self.q2):val=self.q1.pop()else:val=self.q2.popleft()self.rebalance()returnvaldefpopBack(self)->int:ifnotself.q2:return-1val=self.q2.pop()self.rebalance()returnvaldefrebalance(self):iflen(self.q1)>len(self.q2):self.q2.appendleft(self.q1.pop())iflen(self.q2)>len(self.q1)+1:self.q1.append(self.q2.popleft())# Your FrontMiddleBackQueue object will be instantiated and called as such:# obj = FrontMiddleBackQueue()# obj.pushFront(val)# obj.pushMiddle(val)# obj.pushBack(val)# param_4 = obj.popFront()# param_5 = obj.popMiddle()# param_6 = obj.popBack()
classFrontMiddleBackQueue{privateDeque<Integer>q1=newArrayDeque<>();privateDeque<Integer>q2=newArrayDeque<>();publicFrontMiddleBackQueue(){}publicvoidpushFront(intval){q1.offerFirst(val);rebalance();}publicvoidpushMiddle(intval){q1.offerLast(val);rebalance();}publicvoidpushBack(intval){q2.offerLast(val);rebalance();}publicintpopFront(){if(q1.isEmpty()&&q2.isEmpty()){return-1;}intval=q1.isEmpty()?q2.pollFirst():q1.pollFirst();rebalance();returnval;}publicintpopMiddle(){if(q1.isEmpty()&&q2.isEmpty()){return-1;}intval=q1.size()==q2.size()?q1.pollLast():q2.pollFirst();rebalance();returnval;}publicintpopBack(){if(q2.isEmpty()){return-1;}intval=q2.pollLast();rebalance();returnval;}privatevoidrebalance(){if(q1.size()>q2.size()){q2.offerFirst(q1.pollLast());}if(q2.size()>q1.size()+1){q1.offerLast(q2.pollFirst());}}}/** * 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(); */
classFrontMiddleBackQueue{public:FrontMiddleBackQueue(){}voidpushFront(intval){q1.push_front(val);rebalance();}voidpushMiddle(intval){q1.push_back(val);rebalance();}voidpushBack(intval){q2.push_back(val);rebalance();}intpopFront(){if(q1.empty()&&q2.empty())return-1;intval=0;if(q1.size()){val=q1.front();q1.pop_front();}else{val=q2.front();q2.pop_front();}rebalance();returnval;}intpopMiddle(){if(q1.empty()&&q2.empty())return-1;intval=0;if(q1.size()==q2.size()){val=q1.back();q1.pop_back();}else{val=q2.front();q2.pop_front();}rebalance();returnval;}intpopBack(){if(q2.empty())return-1;intval=q2.back();q2.pop_back();rebalance();returnval;}private:deque<int>q1;deque<int>q2;voidrebalance(){if(q1.size()>q2.size()){q2.push_front(q1.back());q1.pop_back();}if(q2.size()>q1.size()+1){q1.push_back(q2.front());q2.pop_front();}}};/** * 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(); */
classFrontMiddleBackQueue{privateq1:Deque<number>;privateq2:Deque<number>;constructor(){this.q1=newDeque<number>();this.q2=newDeque<number>();}pushFront(val:number):void{this.q1.pushFront(val);this.rebalance();}pushMiddle(val:number):void{this.q1.pushBack(val);this.rebalance();}pushBack(val:number):void{this.q2.pushBack(val);this.rebalance();}popFront():number{if(this.q1.isEmpty()&&this.q2.isEmpty()){return-1;}constval=this.q1.isEmpty()?this.q2.popFront():this.q1.popFront();this.rebalance();returnval!;}popMiddle():number{if(this.q1.isEmpty()&&this.q2.isEmpty()){return-1;}constval=this.q1.getSize()===this.q2.getSize()?this.q1.popBack():this.q2.popFront();this.rebalance();returnval!;}popBack():number{if(this.q2.isEmpty()){return-1;}constval=this.q2.popBack();this.rebalance();returnval!;}privaterebalance():void{if(this.q1.getSize()>this.q2.getSize()){this.q2.pushFront(this.q1.popBack()!);}if(this.q2.getSize()>this.q1.getSize()+1){this.q1.pushBack(this.q2.popFront()!);}}}classNode<T>{value:T;next:Node<T>|null;prev:Node<T>|null;constructor(value:T){this.value=value;this.next=null;this.prev=null;}}classDeque<T>{privatefront:Node<T>|null;privateback:Node<T>|null;privatesize:number;constructor(){this.front=null;this.back=null;this.size=0;}pushFront(val:T):void{constnewNode=newNode(val);if(this.isEmpty()){this.front=newNode;this.back=newNode;}else{newNode.next=this.front;this.front!.prev=newNode;this.front=newNode;}this.size++;}pushBack(val:T):void{constnewNode=newNode(val);if(this.isEmpty()){this.front=newNode;this.back=newNode;}else{newNode.prev=this.back;this.back!.next=newNode;this.back=newNode;}this.size++;}popFront():T|undefined{if(this.isEmpty()){returnundefined;}constvalue=this.front!.value;this.front=this.front!.next;if(this.front!==null){this.front.prev=null;}else{this.back=null;}this.size--;returnvalue;}popBack():T|undefined{if(this.isEmpty()){returnundefined;}constvalue=this.back!.value;this.back=this.back!.prev;if(this.back!==null){this.back.next=null;}else{this.front=null;}this.size--;returnvalue;}frontValue():T|undefined{returnthis.front?.value;}backValue():T|undefined{returnthis.back?.value;}getSize():number{returnthis.size;}isEmpty():boolean{returnthis.size===0;}}/** * Your FrontMiddleBackQueue object will be instantiated and called as such: * var obj = new FrontMiddleBackQueue() * obj.pushFront(val) * obj.pushMiddle(val) * obj.pushBack(val) * var param_4 = obj.popFront() * var param_5 = obj.popMiddle() * var param_6 = obj.popBack() */
classFrontMiddleBackQueue{constructor(){this.q1=newDeque();this.q2=newDeque();}pushFront(val){this.q1.pushFront(val);this.rebalance();}pushMiddle(val){this.q1.pushBack(val);this.rebalance();}pushBack(val){this.q2.pushBack(val);this.rebalance();}popFront(){if(this.q1.isEmpty()&&this.q2.isEmpty()){return-1;}constval=this.q1.isEmpty()?this.q2.popFront():this.q1.popFront();this.rebalance();returnval!==undefined?val:-1;}popMiddle(){if(this.q1.isEmpty()&&this.q2.isEmpty()){return-1;}constval=this.q1.getSize()===this.q2.getSize()?this.q1.popBack():this.q2.popFront();this.rebalance();returnval!==undefined?val:-1;}popBack(){if(this.q2.isEmpty()){return-1;}constval=this.q2.popBack();this.rebalance();returnval!==undefined?val:-1;}rebalance(){if(this.q1.getSize()>this.q2.getSize()){this.q2.pushFront(this.q1.popBack());}if(this.q2.getSize()>this.q1.getSize()+1){this.q1.pushBack(this.q2.popFront());}}}classNode{constructor(value){this.value=value;this.next=null;this.prev=null;}}classDeque{constructor(){this.front=null;this.back=null;this.size=0;}pushFront(val){constnewNode=newNode(val);if(this.isEmpty()){this.front=newNode;this.back=newNode;}else{newNode.next=this.front;this.front.prev=newNode;this.front=newNode;}this.size++;}pushBack(val){constnewNode=newNode(val);if(this.isEmpty()){this.front=newNode;this.back=newNode;}else{newNode.prev=this.back;this.back.next=newNode;this.back=newNode;}this.size++;}popFront(){if(this.isEmpty()){returnundefined;}constvalue=this.front.value;this.front=this.front.next;if(this.front!==null){this.front.prev=null;}else{this.back=null;}this.size--;returnvalue;}popBack(){if(this.isEmpty()){returnundefined;}constvalue=this.back.value;this.back=this.back.prev;if(this.back!==null){this.back.next=null;}else{this.front=null;}this.size--;returnvalue;}frontValue(){returnthis.front?.value;}backValue(){returnthis.back?.value;}getSize(){returnthis.size;}isEmpty(){returnthis.size===0;}}/** * Your FrontMiddleBackQueue object will be instantiated and called as such: * var obj = new FrontMiddleBackQueue() * obj.pushFront(val) * obj.pushMiddle(val) * obj.pushBack(val) * var param_4 = obj.popFront() * var param_5 = obj.popMiddle() * var param_6 = obj.popBack() */