The queue
A queue is a special type of linear table that allows only deletion at one end of the table and insertion at the other end. Like a stack, a queue is a linear table with limited operations. The end that inserts is called the end of the queue, and the end that deletes is called the first or head of the queue.
A queue is an abstract data structure with first-in, first-out characteristics that can be implemented using linked lists.
As shown in the figure below, the first-in, first-out feature of queues is shown through common operations “queue push()” and “queue pop()”.
queue.push(1); // Element 1 joins the team
queue.push(2); // Element 2 joins the team
queue.pop(); // Out of line -> element 1
queue.pop(); // Out of line -> element 2
Copy the code
Yes, it still seems to make sense 🤔, fifO is like waiting in line at the canteen, the first person in line is always the first to eat.
Implementation of queues
As in the case of stacks, any table implementation is legal for queues. Like stacks, linked list and array implementations should give fast O(1) running times for each operation.
List implementation of queues
The linked list implementation of queues is straightforward, and since linked lists allocate memory dynamically, they are suitable for situations where queues have no size limit or confirmed size.
A linked list is a dynamic list unless otherwise specified, i.e. a one-way list implemented using random storage.
With Linked list implementation, we still need to avoid tail deletion, which is the weak point of Linked lists. If you don’t understand why tail deletion is the weak point of Linked lists, you can see the diagram of data structure JS – Linked list structure.
Based on the nature of the queue, we can see that the first queue is always deleting (POP) and the last queue is always adding (push). To avoid using the end of the list for deletion, it is natural to select the head pointer of the list as the beginning of the queue and the tail pointer as the end of the queue.
When you push, you just push rear. Next =pushNode; Rear =rear.next, but when the list is empty you also need to point the header to the node that joins the queue. Of course, you can skip this step if you use virtual headers.
When pop, head=head. Next removes the first node, and there is a special case where read=null is required to point the tail pointer to NULL when the list has only one node.
class LinkedListNode{
constructor(value, next = null) {
this.value = value;
this.next = next; }}class Queue {
constructor() {
this.head = null;
this.rear = null;
}
push(value){
const addNode = new LinkedListNode(value)
// Whether the linked list is empty
if(this.isEmpty()){
this.head = addNode;
}else {
this.rear.next = addNode;
}
this.rear = addNode;
return true;
}
pop(){
if(this.isEmpty()){
return null;
}
const removeNode = this.head
// Determine if the list has only one element
if(this.head === this.rear){
this.rear = null
this.head = null
}else {
this.head = this.head.next;
}
return removeNode.value;
}
isEmpty(){
return !this.head && !this.rear; }}const queue = new Queue();
queue.push(1); // Element 1 joins the team
queue.push(2); // Element 2 joins the team
console.log(queue.pop()); / / 1
console.log(queue.pop()); / / 2
console.log(queue.isEmpty()); // true
Copy the codeArray implementation of a queue
Arrays are ideal for scenarios where the queue size is fixed, but we all know that arrays have high performance costs for adding and removing elements. So why are arrays good for fixed-size queue implementations? Let’s start by looking at the problems with a normal array implementation queue
What’s wrong with ordinary array implementation queues?
If we take the front of the array as the head of the queue and the back as the tail of the queue.
We find that when we queue out, we need to move the following elements forward, the time complexity is O(n), and the queue disk overhead is also huge, which is not desirable, nor does it meet the queue pop operation time of O(1) requirement.
So instead of moving an array element forward, we try to use two variables or Pointers to record the array subscripts at the head and end of the array. When we do pop we just move the head pointer back, and when I do push I just move the tail pointer back and insert the value into the tail. The disadvantage, however, is that the space after pop cannot be utilized, resulting in a reduction in queue size.
But we can not expand the capacity of the array, because for the array, the expansion of the capacity needs to open up a new length of the array, and then transfer the old array to the new array, the cost is huge.
Advantages of ring queue
We can make infinite use of the space in an array by turning its storage logic into a loop. This can solve the above mentioned space can not use the problem.
We use head to point to the first element of the team and rear to the last element of the team. You might wonder why Rear doesn’t just point to the back of the line. Think about it: if rear points to the end of the queue, then head and tail point to the same index when there is only one element in the queue, but if the queue is empty, rear comes before head, which doesn’t seem to make much sense of the relationship between head and rear.
Because of its excellent performance, the ring queue is favored by the bottom layer of the system, and even many hardware have implemented the ring queue.
How do ring queues count full and empty?
We see that head and rear point to the same index when the queue is empty or full, so how do we tell if the current queue is empty or full? There are two common approaches.
Method 1: Append a flag bit empty (any name you want)
Empty =true when head catches rear and the queue is empty, empty=false when rear catches head and the queue is full,
Method 2: Restrict rear to catch up with head, that is, there is at least one element space between the end of the team and the start of the team. Generally, prohibit the first node of the head from storing values.
Empty queue: head===rear Queue full: (rear+1)% MAX_LEN === head
The second method takes up one more element of the array
Both implementations are common, but the first one is used as an example.
You know the idea, and you start implementing it.
class Queue{
constructor(size) {
this.MAX_LEN = size;
this.arr = Array(this.MAX_LEN)
this.head = 0;
this.rear = 0;
this.empty = true;// Flag bits used for full and null
}
push(value){
/ / to full
if(this.rear === this.head && !this.empty){
return false;
}
// Insert in rear position, then rear
this.arr[this.rear] = value
this.rear = this.getNextIndex(this.rear)
// rear catch head: full queue
if(this.rear === this.head){
this.empty = false
}
return true;
}
pop(){
/ / found empty
if(this.isEmpty()){
return false;
}
// Get the element in the current haed position, then move the head back
const popValue = this.arr[this.head]
this.head = this.getNextIndex(this.head)
// head catches rear: empty queue
if(this.rear === this.head){
this.empty = true
}
return popValue;
}
isEmpty(){
return (this.head === this.rear) && this.empty
}
// Specify that you use this method to get the index of the next position to form a logical loop of the array
getNextIndex(index){
return (index+1) % this.MAX_LEN; }}Copy the codeThe second method is relatively simple, also attached to the code
class Queue{
constructor(size) {
// The array length needs to be incremented by one, because we need a position to separate head and read
this.MAX_LEN = size + 1;
this.arr = Array(this.MAX_LEN)
this.head = 0;
this.rear = 0;
}
push(value){
// When the next rear position is head, the queue is full
let newRear = this.getNextIndex(this.rear)
if(newRear === this.head){
return false;
}
// Insert in rear position, then rear
this.arr[this.rear] = value
this.rear = newRear
return true;
}
pop(){
/ / found empty
if(this.isEmpty()){
return false;
}
// Get the element in the current haed position, then move the head back
const popValue = this.arr[this.head]
this.head = this.getNextIndex(this.head)
return popValue;
}
isEmpty(){
return this.head === this.rear;
}
getNextIndex(index){
return (index+1) % this.MAX_LEN; }}Copy the codeQueue expansion
The above is just the concept and implementation of the common queue. In reality, there are many other data structures derived from the common queue, which are more efficient and convenient to solve some specific problems. They can also be seen in Leetcode
Let’s get to know them
The bidirectional queue
Normal queue restrictions allow only delete operations on one end of the table and insert operations on the other end. A two-way queue allows both delete and insert operations on both ends of the table. So there’s no head and tail for a two-way queue. Left and right are generally used to represent both ends of a bidirectional queue.
LeftPop, rightPop, leftPush and Rightpush are also generated to operate the two-way queue because both ends of the queue can be deleted and inserted.
The implementation is similar to a normal queue, so you can try it out.
Both ends of a two-way queue need to be deleted, which makes it impossible to avoid the tail deletion problem of a one-way linked list. Therefore, the list implementation of a two-way queue is generally a two-way linked list
Output restricted queue
Output restricted queues can be inserted at both ends of the table, but restricted queues can be deleted at only one end. You can see that output first queues are two-way queues that restrict output (delete) operations on one end.
Input restricted queue
An input restricted queue is one that can be deleted on either side of the table, but a limit can only be added on one side of the table.
Priority queue (heap)
Priority queues are also an abstract data type. Like a normal queue, a priority queue limits output at one end and input at the other. The difference is that each element in a priority queue has a priority, and those with a higher (or lower) priority will be removed first, while those with the same priority will be removed in the order in which they are in the priority queue.
However, priority queues are often implemented using a heap, so that when we say heap, priority queues naturally come to mind.
The heap structure is planned for the next few articles, so I won’t implement priority queues here (because I don’t know 🤣)
Of course, there are many other implementation methods, such as JS asynchronous task queue is the use of macro task queue and micro task queue two ordinary queue to achieve the priority queue. Each time an asynchronous task is fetched, the first element of the queue with the highest priority (microtask) is always fetched first. This kind of priority queue, which is implemented by creating different queues for different priorities, is a good choice when there are few priorities to choose from.
This multi-task queue implementation is relatively simple, students can try oh ~
Now that we’re done with queues, we can do two simple force problems to get into the game.
Leetcode of actual combat
Use two stacks to simulate queues
Leetcode: leetcode-cn.com/problems/im…
Stacks restrict additions and deletions to one end of the table, and queues restrict additions to one end and deletions to the other. These are two completely different abstract data structures. How can a stack simulate a queue?
When using stacks to simulate queues, we need to create two stacks to use together (negative and negative make positive), called in and out respectively, where in simulates queuing and out simulates queuing.
Ideas:
push:
- Insert in directly
pop:
- Pops the top element of out when out is not empty
- When out is empty, the elements in are ejected and pressed into OUT one by one. Finally pops out of the top element of the stack
Note:
Elements need to comply with the following rules when moving from in to out
- Out must be empty before the transfer
- Out cannot be pushed out of the stack, and IN cannot be pushed onto the stack
- All elements in must be transferred to OUT to complete the transition
Note: one stack must be empty before and after the transfer (stack 2 empty before the transfer, stack 1 empty after the transfer)
Use two queue emulation stacks
Leetcode: leetcode-cn.com/problems/im…
Ideas:
Prepare two queues to implement the stack, conveniently called in and out.
push:
- Add it to queue in
pop:
- Unqueue n-1 elements in queue IN one by one, and enter queue out
- Unqueue (unstack) the last element in queue IN
- Swap in and out roles
We can see that both stack implementation and stack implementation are done in the POP operation phase.
But can you implement a stack only with two queues? Is it possible to use one?
A queue can also simulate a stack
Sure, here’s the idea when we use a first column implementation stack
Ideas:
Push: join the queue directly, and then join the queue after the first element (so that the new element is at the top of the queue)
Pop: Exit the queue directly