Series article guide
- Kiner algorithm brush topic (a) : linked list and linked list ideas
- Kiner algorithm: Recursion and stack (solve the expression evaluation problem)
- Kiner algorithm brush topic (3) : thread pool and task queue
- Do you really know binary trees?
- Do you really know binary trees?
- Kiner algorithm: Heap and Priority queue
- Kiner algorithm brush topic (five) : Heap (priority queue)
The open source project
All articles in this series will be collected and managed in GitHub. Welcome ISSUE and Star.
GitHub portal: Kiner algorithm
concept
There is a contiguous store for arbitrary structures, with a head pointer and a tail pointer, which typically points to the next bit of the last element
First in, first out (FIFO)
Basic operation
A simple queue structure should support at least two operations:
Team (push)
The tail pointer moves back one step and inserts the element
The team (pop)
- Logical out of stack: Move the head pointer back one step
- Real stack: If you use arrays to simulate queues, you call arrays
shiftEject the first element of the array
Common variants of queues
Circular queue
Since most languages operate on queues with a header and tail pointer, this can cause a problem:
Join an empty queue with length 10. The * in the following queue indicates that the queue is empty[*, *, *, *, *, *, *, * * *]# execute multiple join and leave operations successively
push 1
push 2
pop
push 3
# After the above operation, our queue looks like this, where the head pointer points to position 2 and the tail pointer points to position 3, which is the * after 3
# Since the queue is a first-in, first-out structure, a POP operation is performed above, so 1 is ejected from the queue, with <1> indicating that the 1x logic is removed.[< > 1, 2, 3, *, *, *, *, *, * *]The size of the queue is limited to 10 bits, and every time we perform a pop operation, there are many elements that are logically deleted.
<1> <1> <1> <1> <1> <1> <1> <1> <1> <1> <1>[< 1 >, < 2 >, < > 3, 4,5,6,7,8,9,10]# this queue as those listed above, it looks as if the queue is full, can't place the next element in the, however, we can find that the previous < 1 >, < 2 >, < 3 > is logic has been deleted, it is no use for us elements, actually, we did not really this queue overflow, Fake overflow just because these guys are squatting in the manger.
Copy the codeSo, if we want to solve the problem of queue false overflow, we derive a variant of queue called circular queue. Circular queue is in order to effectively use of the space of the queue, when the queue tail pointer at the end of the day, if need to insert elements, so the tail pointer will be returned to the queue first, which is < 1 > position above, as long as the head of the tail pointer does not meet, we can go on network queue to insert elements inside, such as the queue, if you are using a circular queue implementation, It could end up like this:
The following queue is the true full queue, where the first queue is 4 and the last queue is 13,12,13,4,5,6,7,8,9,10 [11]Copy the codecircular-queuedTypescriptVersion of the implementation
// LeetCode [622] designs the loop queue
// In order to simulate the implementation of most languages, so in addition to using arrays to store data, do not use some methods of multiple groups, such as pop and push, directly use header and tail pointer implementation
class MyCircularQueue {
// This is used to record how many elements are actually stored in the queue
private count: number = 0;
// use arrays to simulate queues in js
private queue: number[];
/ / the head pointer
private head: number = 0;
/ / the tail pointer
private tail: number = 0;
// Initializes an array control of length k
constructor(private k: number) {
this.queue = new Array<number>(k);
}
/ / team
enQueue(value: number): boolean {
// Return false if the queue is full
if(this.isFull()) return false;
// console.log(this.isFull(), this.count, this.k);
// Assign the element to the position pointed to by the tail pointer
this.queue[this.tail] = value;
// To join a queue, increment the number of elements by one
this.count++;
// The tail pointer moves back one bit. Since the current queue is a circular queue, if it moves back just one bit beyond the length of the array, an exception occurs
// A trick can be used to get the real position of the tail pointer by moving it back one bit and mod the length of the array at initialization
// If k=10 and the current tail pointer points to 9, then the tail pointer moves back one bit to the first element of our array
this.tail = (this.tail + 1) % this.k;
return true;
}
// queue operation
deQueue(): boolean {
// Return false when the queue is empty
if(this.isEmpty()) return false;
// The number of elements is reduced by one
this.count--;
// The head pointer is moved back one bit, so as not to exceed the length of the array
this.head = (this.head + 1) % this.k;
return true;
}
// Return team leader Yuan Shu
Front(): number {
if(this.isEmpty()) return -1;
return this.queue[this.head];
}
// return the last element of the queue
Rear(): number {
if(this.isEmpty()) return -1;
// Since the tail pointer always points to the next bit of the last element in the queue, tail-1 is negative if tail is exactly 0
// To solve this problem, we can add an array length to the end of the pointer, and then mod to the array length.
// For example, k=10, (0-1 + 10) % 10 = 9, so the last element in the array index is 9
const idx = (this.tail - 1 + this.k) % this.k;
return this.queue[idx];
}
// Check whether the queue is empty
isEmpty(): boolean {
return this.count === 0;
}
// Check whether the queue is full
isFull(): boolean {
return this.count === this.k; }}Copy the codeBidirectional loop queue
Bidirectional circular queue is a special queue which can enter the queue at the head or tail and exit the queue at the head or tail
Two-way circular queueTypescriptversion
// LeetCode [641] designs a loop double-ended queue
class MyCircularDeque {
private head: number = 0;
private tail: number = 0;
private count: number = 0;
private queue: number[];
constructor(private k: number) {
this.queue = new Array<number>(k);
}
// Insert the element at the head of the queue
insertFront(value: number): boolean {
if(this.isFull()) return false;
// Since the front of the team may have elements, and the back of the team does not have elements, so
// To insert an element at the head of the queue, move head one bit to the left (note that head is 0).
this.head = (this.head - 1 + this.k) % this.k;
this.queue[this.head] = value;
this.count++;
return true;
}
// Insert elements at the end of the queue
insertLast(value: number): boolean {
if(this.isFull()) return false;
this.queue[this.tail] = value;
this.tail = (this.tail + 1) % this.k;
this.count++;
return true;
}
// Delete the element at the head of the queue
deleteFront(): boolean {
if(this.isEmpty()) return false;
this.head = (this.head + 1) % this.k;
this.count--;
return true;
}
// Delete the element at the end of the queue
deleteLast(): boolean {
if(this.isEmpty()) return false;
this.tail = (this.tail - 1 + this.k) % this.k;
this.count--;
return true;
}
// Get the first element
getFront(): number {
if(this.isEmpty()) return -1;
return this.queue[this.head];
}
// Get the tail of the team with Anna Sui
getRear(): number {
if(this.isEmpty()) return -1;
const idx = (this.tail - 1 + this.k) % this.k;
return this.queue[idx];
}
// Check whether the queue is empty
isEmpty(): boolean {
return this.count === 0;
}
// Check whether the queue is full
isFull(): boolean {
return this.count === this.k; }}Copy the codeFront, middle, back queue
Front, middle and back circular queue On the basis of the bidirectional circular queue, a new queue can enter and exit from the middle of the queue
Front, middle and back queueTypescriptversion
// leetCode: [1670] design the front, middle and back queues
// Use a bidirectional list to implement a front, middle and back queue
/ / such as: 1 - > 2 - > 3 - > 4
// Can be seen as: 1->2 -> 3->4
// The two lists are linked together, so that when we want to insert into the middle, we just need to decide whether to insert after list 1 or before list 2
// Bidirectional list list node object
class Node {
constructor(public val=0,public prev: Node=null, public next: Node=null){}
// Insert a node before the current node
insertPrev(node: Node) {
node.prev = this.prev;
node.next = this;
this.prev && (this.prev.next = node);
this.prev = node;
}
// Insert a node after the current node
insertNext(node: Node) {
node.next = this.next;
this.next && (this.next.prev = node)
this.next = node;
node.prev = this;
}
// Pops up the previous node of the current node
popPrev(): void {
if(!this.prev) return;
let p = this.prev;
this.prev = p.prev;
this.prev && (this.prev.next = this);
}
// The next node of the current node is displayed
popNext(): void {
if(!this.next) return;
let p = this.next;
this.next = p.next;
this.next && (this.next.prev = this); }}// Implement a circular double-ended queue using a bidirectional list
class MyQueue {
// Since it is a double-endian queue, elements can be added and removed from the head or from the tail
// So we need to define the first and last two virtual nodes to help us operate the list
private head: Node = new Node();
private tail: Node = new Node();
private count: number = 0;// Is used to record the actual number of elements in the queue, the key of the loop queue
constructor(){
// To start with, let's connect the end to the head
// head -> tail
// We need to insert elements from the front, just after the head node
// When we need to insert elements from behind, we only need to insert elements from before the tail node
this.head.next = this.tail;
this.head.prev = null;
this.tail.next = null;
this.tail.prev = this.head;
}
// Insert the element at the end of the queue
public pushBack(val: number) {
this.tail.insertPrev(new Node(val));
this.count++;
}
// Insert elements at the head of the queue
public pushFront(val: number) {
this.head.insertNext(new Node(val));
this.count++;
}
// Remove the element at the end of the queue
public popBack(): number {
if(this.isEmpty()) return -1;
let res = this.tail.prev.val;
this.tail.popPrev();
this.count--;
return res;
}
// Delete the element at the head of the queue
public popFront(): number {
if(this.isEmpty()) return -1;
let res = this.head.next.val;
this.head.popNext();
this.count--;
return res;
}
// Get the first element
public front(): number{
return this.head.next.val;
}
// Get the last element of the pair
public back(): number{
return this.tail.prev.val;
}
// Queue element coral grain
public size(): number{
return this.count;
}
// Whether the queue is empty
public isEmpty(): boolean{
return this.head.next === this.tail; }}class FrontMiddleBackQueue {
private q1: MyQueue;
private q2: MyQueue;
constructor() {
this.q1 = new MyQueue();
this.q2 = new MyQueue();
}
// After each element addition or deletion, to always keep the number of elements in Q1 greater than or equal to the number of elements in Q2, call this method for correction
update(): void {
// 1 -> 2 -> 3 -> 4
// Always ensure that the length of Q1 is greater than or equal to q2, and that the difference between the two nodes is at most 1
// When q1 is less than q2, remove a node from the head of Q2 and place it at the end of Q1
if(this.q1.size() < this.q2.size()) {
this.q1.pushBack(this.q2.popFront());
}
// If the number of Q2 is two less than the number of Q1, take one from the tail of Q1 and place it in the head of Q2
if(this.q2.size() === this.q1.size() - 2) {
this.q2.pushFront(this.q1.popBack()); }}// To add elements to the first queue, add elements directly to Q1, and then modify both queues
pushFront(val: number): void {
this.q1.pushFront(val);
this.update();
}
If q1 has more elements than q2, place the element at the head of Q2, or at the tail of Q1
pushMiddle(val: number): void {
if(this.q1.size() > this.q2.size()) {
this.q2.pushFront(this.q1.popBack());
}
this.q1.pushBack(val);
this.update();
}
/ / in the line add elements, add elements at the end of the q2 can directly, and then fixed two queues
pushBack(val: number): void {
this.q2.pushBack(val);
this.update();
}
// Remove the element from the head of the queue, delete and fix the two queue interfaces in the head of Q1
popFront(): number {
if(this.isEmpty()) return -1;
let res = this.q1.popFront();
this.update();
return res;
}
Q1 is always greater than or equal to Q2, so we simply remove the last element of Q1 from the queue
popMiddle(): number {
if(this.isEmpty()) return -1;
let res = this.q1.popBack();
this.update();
return res;
}
// Remove the element from the end of the queue. If q2 is empty, remove the element from the head of q1, otherwise from the head of Q2
popBack(): number {
if(this.isEmpty()) return -1;
let res;
if(this.q2.isEmpty()){
res = this.q1.popBack();
} else{
res = this.q2.popBack();
}
this.update();
return res;
}
// Check whether the queue is empty
isEmpty(): boolean {
return this.q1.size() === 0; }}Copy the codePriority queue
As we all know, ordinary queue is a strictly follow the principle of first in first out (FIFO) data structure, but in some special occasions, such as our task queue, there is a high priority tasks need to be priority, so, this time is about to jump the queue, and support this operation jumped the queue queue, we call it the priority queue, namely: Queues that support priority
Typical application scenarios of queues
CPU hyperthreading technology
The CPU continuously processes incoming instructions through instruction queues
Virtual quad-core is essentially just two cores, with two instruction queues added
A CPU contains multiple computing cores
The task queue of the thread pool
It is equivalent to the buffer of the task. Generally, when there is no time to process, it is put in the queue for a while, and then it is fetched from the queue
A process can be understood as a person
Threads are things that this person is going to do
One person can do more than one thing at a time, so a process can contain several threads
LeetCode brush problem
LeetCode 933 number of recent requests
Their thinking
This problem is the use of the queue of first in first out principle to achieve, this problem is relatively simple, we directly look at the concrete implementation.
Code implementation
/* * @lc app=leetcode.cn id=933 lang=typescript * * [933] Number of recent requests */
// @lc code=start
class RecentCounter {
// Use an array stack
private queue: number[];
constructor() {
// Initialize the array
this.queue = new Array<number>();
}
ping(t: number): number {
// queue t on each request
this.queue.push(t);
// Unqueue all elements whose time is greater than 3000
while(t - this.queue[0] > 3000) this.queue.shift();
// The length of the last remaining array is our most recent request
return this.queue.length; }}/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
// @lc code=end
Copy the codeLeetcode 622 designs circular queues
Refer to the common variants of queues above for code parsing
Leetcode 641 designs looping double-ended queues
Refer to the common variants of queues above for code parsing
Leetcode: 1670 Design the front, middle and back queues
Refer to the common variants of queues above for code parsing