Topic describes
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].
Thought analysis
We can solve this problem by designing a two-endian queue, which we did before, two two-endian queues to form a front, middle and back queue.
The first and second double-endian queues can be designed to pushMiddle to the end of the first double-endian queue if they are equal, and to put data at the head of the second if the first queue is larger than the second.
So what we’re going to do in this problem is we’re going to encapsulate a double-ended queue, and we can also encapsulate a double-ended queue using a linked list.
So we can implement a list structure, and then use the list to implement a two-ended queue, and then implement this problem.
All right, Russian nesting dolls.
Next, we will implement the encapsulation of linked lists.
Can not transfer the position to learn the chain list, rice to eat a mouthful, the road to go step by step.
List enclosed
Create a TreeNode class with properties pre, Next, and Val.
Contains:
Insert_pre, insert_next, delete_pre, delete_next
insert_pre
insert_next
delete_pre
delete_next
class TreeNode {
constructor(val, next, pre) {
this.val = val;
this.next = next;
this.pre = pre;
}
insert_pre = (node) = > {
node.next = this;
node.pre = this.pre;
if (this.pre) {
this.pre.next = node
}
this.pre = node;
return;
}
insert_next = (node) = > {
next.pre = this;
next.next = this;
if (this.pre) this.next.pre = node;
this.next = node;
}
delete_pre = () = > {
if (!this.pre) return;
const node = this.pre;
this.pre = node.pre;
if (node.pre) node.pre.next = this;
return;
}
delete_next = () = > {
if (!this.next) return;
const node = this.next;
this.next = node.next;
if (node.next) node.next.pre = this;
return; }}Copy the codeDouble-ended queue encapsulation using linked lists
First, a two-endian queue needs to have two nodes, head and tail
At initialization, the first node above the head node is empty, the next node after the tail node is empty, and the next node after the head node is the tail node, and the last node is the head node.
I’m done with dolls! Take a look at the separate implementation of dual – ended queue encapsulation
In addition, there is an auxiliary parameter, count, which stores the size of the current two-ended queue
The class name of a double-ended queue is called DeQueue, and the properties are covered above, so let’s look at the methods needed for a double-ended queue
pushBack
Insert a new object for the virtual tail node
pushFount
Inserts a new object for the virtual header node
popBack
Delete tail nodes
popFront
Delete header node
isEmpty
Empty queue
size
Queue size
front
View the header node
back
View the tail node
Code to arrange
So let’s do that in code
class DeQueue {
constructor() {
this.head = new TreeNode();
this.tail = new TreeNode();
this.head.next = this.tail;
this.tail.pre = this.head;
this.head.pre = null;
this.tail.next = null;
this.count = 0;
}
pushBack = (val) = > {
this.tail.insert_pre(new TreeNode(val));
this.count += 1;
}
pushFront = (val) = > {
this.head.insert_next(new TreeNode(val));
this.count += 1;
}
popBack = () = > {
if (this.isEmpty()) return;
const ret = this.tail.pre.val;
this.tail.delete_pre();
this.count -= 1;
return ret;
};
popFront = () = > {
if (this.isEmpty()) return;
const ret = this.head.next.val;
this.head.delete_next();
this.count -= 1;
return ret;
};
isEmpty = () = > {
return this.head.next === this.tail;
};
size = () = > {
return this.count;
};
front = () = > {
return this.head.next.val;
};
back = () = > {
return this.tail.pre.val;
};
}
Copy the codeImplement our front, middle and back queues using encapsulated double-ended queues
Need to achieve the title has been described, ideas in the beginning of this article about the need to use two double-ended queues to achieve, in addition to normal to achieve our demand method, for the balance of two double-ended queue data we can add an update method.
The update () method is used to update the number of elements in two queues
Let’s implement our FrontMiddleBackQueue
class FrontMiddleBackQueue {
constructor() {
this.q1 = new DeQueue();
this.q2 = new DeQueue();
}
// Two double-ended queues Q1 Q2
// @lc code=start
/ * * *@param {number} val
* @return {void}* /
pushFront = (val) = > {
this.q1.pushFront(val);
this.update();
return;
};
/ * * *@param {number} val
* @return {void}* /
pushBack = (val) = > {
this.q2.pushBack(val);
this.update();
return;
};
/ * * *@param {number} val
* @return {void}* * /
pushMiddle = (val) = > {
if (this.q1.size() > this.q2.size()) {
this.q2.pushFront(this.q1.popBack());
}
this.q1.pushBack(val);
this.update();
return;
};
/ * * *@return {number}* /
popFront = () = > {
if (this.isEmpty()) return -1;
const ret = this.q1.popFront();
this.update();
return ret;
};
/ * * *@return {number}* /
popBack = () = > {
if (this.isEmpty()) return -1;
let ret;
if (this.q2.isEmpty()) {
ret = this.q1.popBack();
} else {
ret = this.q2.popBack();
}
this.update();
return ret;
};
/ * * *@return {number}* /
popMiddle = () = > {
if (this.isEmpty()) return -1;
const ret = this.q1.popBack();
this.update();
return ret;
};
isEmpty = () = > {
return this.q1.size() + this.q2.size() === 0;
};
update = () = > {
// Update the number of elements Q1, odd, even evenly divided
if (this.q1.size() < this.q2.size()) {
this.q1.pushBack(this.q2.popFront());
}
if (this.q1.size() === this.q2.size() + 2) {
this.q2.pushFront(this.q1.popBack()); }}; }Copy the codeOther related
Full code implementation