Data structure – Learning notes integration
Data Structures – Stacks (Study Notes)
Data Structures – Queues (Study Notes)
Data Structures – Linked Lists (Study Notes)
Data Structures – Collections (Study Notes)
| dictionary and hash table data structure (front end call it objects)
Data structures – binary trees and binary search trees
| binary heap data structure
What is a queue
Queues are data structures. Queues are also known as “waiting lines” and, as the name implies, they can easily be imagined as a group of people waiting in line. In the queue, the earlier the queue, the higher the priority. When adding data to the queue, the data comes last. When data is fetched from the queue, it is fetched from the earliest data added. The operation of fetching data from a queue is called dequeuing. A queue is an ordered set of items that follow a first-in, first-out (FIFO, also known as first come, first served) principle. Queues add new elements at the tail and remove elements from the top. The most recently added element must be at the end of the queue.
Queues in real life: queues, print queues for printers
The queue
Code implementation
/** * a queue is an ordered group of items that follow a first-in, first-out (FIFO, also known as first come, first served) principle. Queues add new elements at the tail and remove elements from the top. The most recently added element must be at the end of the queue. * Common queues in life: queue, printer print queue */
export class Queue {
constructor() {
this.count = 0; // Since objects are used, use the count attribute to control the queue size.
this.lowestCount = 0; // Since the element needs to be removed from the front of the queue, lowestCount is needed to help track the first element
this.items = {}; // You can use arrays, or you can use data structures such as objects. Object implementations of queues are more algorithmatically complex than arrays in most cases
}
/** * Adds one (or more) new items to the end of the queue. *@param {*} Element The item to add */
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
/** * removes the first item in the queue and returns the removed element. *@returns {*} The removed element */
dequeue() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
const result = this.items[this.lowestCount]; // Hold the value of the queue header for return
delete this.items[this.lowestCount]; // Remove the element in the queue header
this.lowestCount++; // The attribute of the pointer to the queue head element is incremented because the queue head element does not exist after being removed
return result; // Returns the removed element
}
/** * returns the first element in the queue -- the first element added and will be the first element removed. The queue does nothing (no element is removed, only element information is returned -- very similar to the PEEK method of the Stack class). This method can also be called the front method in other languages. *@returns {*} The removed element */
peek() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
return this.items[this.lowestCount]; // Returns the first element in the queue
}
/** * Return true if the queue contains no elements, false otherwise. *@returns {Boolean}* /
isEmpty() {
return this.size() === 0;
}
/** * Clear the queue */
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
/** * returns the number of elements in the queue, similar to the length property of an array. *@returns {Number} Number of elements in the queue */
size() {
return this.count - this.lowestCount;
}
/** * Outputs the queue value * as a string@returns {Array}* /
toString() {
if (this.isEmpty()) { // Check whether the queue is empty
return ' '; // Returns an empty string if it is empty
}
// If the queue is not empty
let objString = `The ${this.items[this.lowestCount]}`; // Use the first element in the queue as the initial value of the string
// Since the first index in Queue is not necessarily 0, we need to start iterating through the Queue at lowestCount
for (let i = this.lowestCount + 1; i < this.count; i++) {
// Add a comma (,) and the next element
objString = `${objString}.The ${this.items[i]}`;
}
// Outputs the queue value as a string
returnobjString; }}Copy the codedeque
concept
A deque, or double-ended queue, is a special queue that allows you to add and remove elements from both the front end and the back end.
Double – ended queues are common in life
Examples of double-ended queues in real life include queues in cinemas and restaurants. For example, a person who has just bought a ticket can go straight back to the head of the line if they just need to ask a few more simple questions. In addition, the person at the end of the line can just leave the line if he is in a hurry.
In computer science, a common use of double-endian queues is to store a series of undo operations. Every time a user performs an operation in the software, the operation is stored in a double-ended queue (like in a stack). When the user clicks the undo button, the action is ejected from the two-end queue, indicating that it has been removed from behind. After performing a predefined number of operations,
The first operation is removed from the front of the two-ended queue. Since the two-ended queue complies with both fifO and LIFO principles, it can be said that it is a kind of data structure combining queue and stack.
Code implementation
/** * A deque, or double-ended queue, is a special queue that allows you to add and remove elements from both the front end and the back end. * Dual-ended queues are common in real life: * Dual-ended queues are examples of queues in cinemas, restaurants, etc. For example, a person who has just bought a ticket can go straight back to the head of the line if they just need to ask a few more simple questions. In addition, the person at the end of the line can just leave the line if he is in a hurry. * In computer science, a common use of double-endian queues is to store a series of undo operations. Every time a user performs an operation in the software, the operation is stored in a double-ended queue (like in a stack). When the user clicks the undo button, the action is ejected from the two-end queue, indicating that it has been removed from behind. After a predefined number of operations have been performed, * the first operation is removed from the front of the two-end queue. Since the two-ended queue complies with both fifO and LIFO principles, it can be said that it is a kind of data structure combining queue and stack. * /
export class Deque {
constructor() {
this.count = 0; // Since objects are used, use the count attribute to control the size of the double-ended queue.
this.lowestCount = 0; // Since the element needs to be removed from the front of the two-ended queue, lowestCount is needed to help track the first element
this.items = {}; // You can use arrays or data structures such as objects. In most cases, the algorithm complexity of object implementation is better than that of array
}
/** * Adds a new element * to the front of the double-ended queue@param {*} Element The item to add */
addFront(element) {
if (this.isEmpty()) { // If the queue is empty
this.addBack(element); // Add to the back end of a double-ended queue
} else if (this.lowestCount > 0) { // If an element has been removed from the front end of a double-endian queue
this.lowestCount--; // The lowestCount attribute is greater than or equal to 1, so decrement lowestCount
this.items[this.lowestCount] = element; // Place the value of the new element in the position of the key
} else {
// We can set a negative key and update the logic used to calculate the length of the double-ended queue to include a negative key. In this case, the operation of adding a new element still keeps the computational cost to a minimum.
// It is still treated as an array
// To add a new element to the first place, we need to move all elements back one bit to make space for the first place
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++; // Increments the size of the two-ended queue
this.items[0] = element; // After all the elements have been moved, the first element in the queue will be idle}}/** * Add a new element to the back end of the Queue (implemented in the same way as the enqueue method in Queue) *@param {*} Element The item to add */
addBack(element) {
this.items[this.count] = element;
this.count++;
}
/** * Removes the first element from the front of the Queue (same as the dequeue method in Queue) *@returns {*} The removed element */
removeFront() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
const result = this.items[this.lowestCount]; // Hold the value of the header of the double-ended queue for return
delete this.items[this.lowestCount]; // Remove the element in the header of the double-ended queue
this.lowestCount++; // The attribute of the pointer to the double-ended queue header element is incremented because the double-ended queue header element does not exist after being removed
return result; // Returns the removed element
}
/** * Removes the first element from the back end of the double-ended queue (implemented in the same way as the POP method in the Stack class) *@returns {*} The removed element */
removeBack() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
this.count--; // The number of elements in the double-endian queue is reduced by 1
const result = this.items[this.count]; // Save the value at the end of the double-ended queue (for return)
delete this.items[this.count]; // Remove the element at the end of the double-ended queue
return result; // Returns the removed element
}
/** * Returns the first element at the front of the Queue (implemented in the same way as peek in Queue) *@returns {*} The first element at the front of a double-ended queue */
peekFront() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
return this.items[this.lowestCount]; // Returns the first element at the top of a double-ended queue
}
/** * Returns the first element at the back of a double-ended queue (implemented in the same way as the PEEK method in the Stack class) *@returns {*} The first element */ at the back of a double-ended queue
peekBack() {
if (this.isEmpty()) { // Check whether the queue is empty
return undefined; // If empty, undefined is returned
}
// If the queue is not empty
return this.items[this.count - 1]; // Returns the first element on the back end of a double-ended queue
}
/** * Return true if the double-ended queue contains no elements, false otherwise. *@returns {Boolean}* /
isEmpty() {
return this.size() === 0;
}
/** * Clear the queue */
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
/** * Returns the number of elements in a double-ended queue, similar to the length property of an array. *@returns {Number} Number of elements in a double-ended queue */
size() {
return this.count - this.lowestCount;
}
/** * Outputs the value of a double-ended queue * as a string@returns {Array}* /
toString() {
if (this.isEmpty()) { // Check whether the queue is empty
return ' '; // Returns an empty string if it is empty
}
// If the queue is not empty
let objString = `The ${this.items[this.lowestCount]}`; // Use the first element in the double-ended queue as the initial value of the string
// Since the first index in the Deque class is not necessarily 0, we need to start iterating through the queue at lowestCount
for (let i = this.lowestCount + 1; i < this.count; i++) {
// Add a comma (,) and the next element
objString = `${objString}.The ${this.items[i]}`;
}
// Outputs the value of a double-ended queue as a string
returnobjString; }}Copy the code