One, foreword

It’s easy to use JavaScript arrays to implement front, middle and back queues because JavaScript arrays support front, middle and back operations. You can do it with one array, but it doesn’t make a lot of sense to do it with two arrays. I’m going to implement front, middle and back queues using a circular two-ended queue. I’ve implemented a circular double-ended queue with an array, so I’m going to implement a circular double-ended queue with a two-way list.

2. Title Description

Design a queue that supports push and POP operations in the front, middle, and back positions.

Please complete the FrontMiddleBack class:

  • FrontMiddleBack() initializes the queue.
  • Void pushFront(int val) adds val to the front of the queue.
  • Void pushMiddle(int val) adds val to the middle of the queue.
  • Void pushBack(int val) adds val to the end of the queue.
  • Int popFront() removes the uppermost element from the queue and returns the value, or -1 if the queue was empty before the deletion.
  • Int popMiddle() removes the middle element from the queue and returns the value, or -1 if the queue was empty before deletion.
  • Int popBack() removes the last element from the queue and returns the value, or -1 if the queue was empty before deletion.

Note that when there are two middle positions, select the front position for operation. For example:

  • Add 6 to the middle of [1, 2, 3, 4, 5], resulting in an array of [1, 2, 6, 3, 4, 5].
  • Pop the element from the middle of [1, 2, 3, 4, 5, 6], return 3, and the array becomes [1, 2, 4, 5, 6].

Example:

Input:  ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "" popFront popBack", "] [[], [1], [2], [3], [4], [], [], [], [], []] output: [NULL, null, NULL, null, 1, 3, 4, 2, -1] FrontMiddleBackQueue q = new FrontMiddleBackQueue(); q.pushFront(1); // [1] q.pushBack(2); // [1, 2] q.pushMiddle(3); // [1, 3, 2] q.pushMiddle(4); // [1, 4, 3, 2] q.popFront(); // Return 1 -> [4, 3, 2] q.popmiddle (); // Return 3 -> [4, 2] q.popmiddle (); // Return 4 -> [2] q.popback (); // Return 2 -> [] q.popfront (); // Return -1 -> [] (queue empty)Copy the code

For a more detailed solution, see the leetcode address

Third, the problem solving

3.1 Implementation of linked list node classes

Annotated, the class is a constructor plus four methods

Class Node {constructor(val = 0, next = null, Pre = null) {this.val = val this.next = next this.pre = pre} insertBefore(node) { Pre = this.pre. Next = this if(this.pre) this.pre. Next = node this.pre = node} // Insert node after the current node InsertAfter (node) { Next = this.next if(this.next) this.next. Pre = node this.next = node} // Delete the previous node of the current node DeleteBefore () {if(this.pre) {this.pre = this.pre. Pre if(this.pre) this.pre. Next = this} deleteAfter() { if(this.next) { this.next = this.next.next if(this.next) this.next.pre = this } } }Copy the code

3.2 Using linked lists to achieve simplified circular double-ended linked lists

Just watch out for false heads and false tails

Class CircularDoubleEndQueue {constructor() {this.count = 0 this.dummyHead = new Node() // This.dummytail = new Node() Next = this.dummyhead this.dummytail this.dummytail. Pre = this.dummyhead} pushFront(val) { This. DummyHead. InsertAfter (new Node (val) enclosing count++} / / of the increased pushBack (val) {this. DummyTail. InsertBefore (new Node(val)) this.count++} // popFront() {if(this.isempty ()) return -1 // Save the deleted Node value const ret = Enclosing dummyHead. Next. Val / / remove this. DummyHead. DeleteAfter () this. Count - return ret} / / of the delete popBack (val) {/ / the queue is empty If (this. IsEmpty ()) return 1 / delete/save node value const ret = this. DummyTail. Pre. Val / / remove this. DummyTail. DeleteBefore () This.count -- return ret} // empty isEmpty() {// this.count === 0 // this.dummytail.pre === this.dummyHead return this.dummyHead.next === this.dummyTail } }Copy the code

3.3 Implement front, middle and back queues with circular double-ended queues

I don’t want to go into too much detail here, but look at the code and think about whether it’s satisfying to do this:

  • The number of left queues is less than or equal to the number of right queues
  • The minimum number of left queues is 1
  • The maximum number of right queues is + 1
Function () {this.leftque = new CircularDoubleEndQueue() this.rightque = new CircularDoubleEndQueue() }; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. PushFront = function (val) {/ / before PushFront (val) {this.leftque.count > rightque.count if(this.leftque.count > this.rightque.count) this.rightQue.pushFront(this.leftQue.popBack()) }; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. PushMiddle = function (val) {/ / add points, When leftque. count = rightque. count the first increment of the right queue; Leftque. count < rightque. count left queue end increment, In both cases leftque. count < rightque. count - 1, If (this.leftque.count === this.rightque.count) {this.rightque.pushfront (val)} else {this.leftque.pushback (val) }}; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. The pushBack = function (val) {/ / tail PushBack (val) this.rightque. count < this.rightque. count - 1 if(this.leftque. count < this.rightque. count) this.rightQue.count - 1) this.leftQue.pushBack(this.rightQue.popFront()) }; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopFront = function () {/ right/left queue queue is empty, If (this.rightque.isempty ()) return -1 // right queue is not empty, left queue isEmpty, Return this.rightque.popFront () if(this.leftque.isempty ()) return this.rightque.popFront () This.leftque.count < this.rightque.count - 1 let ret = this.leftque.popfront () if(this.leftque.count < this.rightque.count - 1 let ret = this.leftque.popfront () if(this.leftque.count < this.rightque.count) this.rightQue.count - 1) this.leftQue.pushBack(this.rightQue.popFront()) return ret }; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopMiddle = function () {/ right/left queue queue is empty, If (this.leftque.count === this.rightque.count) return -1 if(this.leftque.count) Return this.leftque.popback () // Return this.rightque.popfront ()}; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopBack = function () {/ right/left queue queue is empty, If (this.rightque.isempty ()) return -1 // Let ret = this.rightque.popback (); May this.leftque.count > this.rightque.count if(this.leftque.count > this.rightque.count) this.rightQue.pushFront(this.leftQue.popBack()) return ret }; /** * 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() */Copy the code

3.4 Complete Code

In fact, I was going to put this pile of code up, but I was afraid that I wouldn’t want to see it when I reviewed it. It took me 2 hours to write this code, and I’m still too bad.

Class Node {constructor(val = 0, next = null, Pre = null) {this.val = val this.next = next this.pre = pre} insertBefore(node) { Pre = this.pre. Next = this if(this.pre) this.pre. Next = node this.pre = node} // Insert node after the current node InsertAfter (node) { Next = this.next if(this.next) this.next. Pre = node this.next = node} // Delete the previous node of the current node DeleteBefore () {if(this.pre) {this.pre = this.pre. Pre if(this.pre) this.pre. Next = this} DeleteAfter () {if(this.next) {this.next = this.next. Next if(this.next) this.next CircularDoubleEndQueue {constructor() {this.count = 0 // This.dummyHead = new Node() // This.dummyTail = new Node() // Initially, Next = this.dummyhead this.dummytail this.dummytail. Pre = this.dummyhead} pushFront(val) { This. DummyHead. InsertAfter (new Node (val) enclosing count++} / / of the increased pushBack (val) {this. DummyTail. InsertBefore (new Node(val)) this.count++} // popFront() {if(this.isempty ()) return -1 // Save the deleted Node value const ret = Enclosing dummyHead. Next. Val / / remove this. DummyHead. DeleteAfter () this. Count - return ret} / / of the delete popBack (val) {/ / the queue is empty If (this. IsEmpty ()) return 1 / delete/save node value const ret = this. DummyTail. Pre. Val / / remove this. DummyTail. DeleteBefore () This.count -- return ret} // empty isEmpty() {// this.count === 0 // this.dummytail.pre === this.dummyHead return This. DummyHead. Next = = = this. DummyTail}} / / * * * * * * * * * * * * * * * * * * * * * with the ground in front of, Now before the implementation of queue after * * * * * * * * * * * * * * * * * * * * * * * * * * * var FrontMiddleBackQueue = function () {/ / initializes the two loops deque enclosing leftQue = new CircularDoubleEndQueue() this.rightQue = new CircularDoubleEndQueue() }; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. PushFront = function (val) {/ / before PushFront (val) {this.leftque.count > rightque.count if(this.leftque.count > this.rightque.count) this.rightQue.pushFront(this.leftQue.popBack()) }; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. PushMiddle = function (val) {/ / add points, When leftque. count = rightque. count the first increment of the right queue; Leftque. count < rightque. count left queue end increment, In both cases leftque. count < rightque. count - 1, If (this.leftque.count === this.rightque.count) {this.rightque.pushfront (val)} else {this.leftque.pushback (val) }}; / * * * @ param {number} val * @ return void * / FrontMiddleBackQueue. Attach the prototype. The pushBack = function (val) {/ / tail PushBack (val) this.rightque. count < this.rightque. count - 1 if(this.leftque. count < this.rightque. count) this.rightQue.count - 1) this.leftQue.pushBack(this.rightQue.popFront()) }; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopFront = function () {/ right/left queue queue is empty, If (this.rightque.isempty ()) return -1 // right queue is not empty, left queue isEmpty, Return this.rightque.popFront () if(this.leftque.isempty ()) return this.rightque.popFront () This.leftque.count < this.rightque.count - 1 let ret = this.leftque.popfront () if(this.leftque.count < this.rightque.count - 1 let ret = this.leftque.popfront () if(this.leftque.count < this.rightque.count) this.rightQue.count - 1) this.leftQue.pushBack(this.rightQue.popFront()) return ret }; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopMiddle = function () {/ right/left queue queue is empty, If (this.leftque.count === this.rightque.count) return -1 if(this.leftque.count) Return this.leftque.popback () // Return this.rightque.popfront ()}; / * * * @ return {number} * / FrontMiddleBackQueue prototype. PopBack = function () {/ right/left queue queue is empty, If (this.rightque.isempty ()) return -1 // Let ret = this.rightque.popback (); May this.leftque.count > this.rightque.count if(this.leftque.count > this.rightque.count) this.rightQue.pushFront(this.leftQue.popBack()) return ret }; /** * 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() */Copy the code