preface
As a kind of data structure, queue can be applied to movie theaters, cafeterias and other occasions in real life. The first person in line will receive service first.
In computer applications, the printing of multiple documents is a queue, and the first document is printed first.
In this article, we will use TypeScript to implement queue and double-endian queue data structures and solve two classic problems in computer science. Interested developers are welcome to read this article.
Implementation of queues
This article focuses on the implementation of queue code, if the queue is not familiar with the data structure developers can move on to my other article: stacks and queues
Implementation approach
Queues follow the principle of first in, first out (FIFO). According to the characteristics of queues, we can know that to achieve a queue must have the following methods:
- Enqueue to queue a new element (add a key to the object)
- Out of the queue, take the element of the head of the queue (obtained by key), and return the element of the head of the queue.
- Check whether the queue is empty, check whether the number of elements in the queue is 0(queue size – first element position)
- The first queue element gets the first queue element of the current queue and returns it.
- Queue size, gets the number of elements in the queue and returns (queue size – position of the first element in the queue).
- Clear the queue and delete all elements in the queue. Initializes the internal variables of the queue.
- All elements in the queue, concatenate the elements in the queue into a string with commas and return (iterating over the elements in the queue).
The implementation code
With that in mind, we can code.
Next, let’s translate the above implementation idea into code:
- Create a Queue. Ts file
- Use interfaces to declare internal queue object types
interface QueueObj {
[propName: number] : any;
}
Copy the code- Declare and initialize the three variables required by the queue in the constructor: queue size, the first element of the queue, and the queue object
private count: number;
private lowestCount: number;
private items: QueueObj;
constructor() {
this.count = 0;
this.lowestCount = 0; this.items = {}; } Copy the code- Implement enqueue function (enqueue), parameters for any type of data, the size of the queue as the queue object key.
enqueue(item: any) {
// Add an element to the end of the queue: use the size of the queue as the key
this.items[this.count] = item;
this.count++;
}
Copy the code- Implement the queue function (dequeue), store the queue first element, remove the queue first element key in the queue object, the queue first element position increases.
dequeue() {
if(this.isEmpty()){
return undefined;
}
const result = this.items[this.lowestCount];
// Delete the header element delete this.items[this.lowestCount]; // Team head element increases this.lowestCount++; return result; } Copy the code- Check whether the queue isEmpty (isEmpty). Check whether the current queue size – the position of the first element in the queue is equal to 0
isEmpty() {
return this.count - this.lowestCount === 0;
}
Copy the code- Get queue head element (PEEK), gets the value in the queue object with the current queue head element as key and returns it.
peek() {
if(this.isEmpty()){
return undefined;
}
return this.items[this.lowestCount];
} Copy the code- Gets queue size, the current queue size – the position of the first element in the queue
size() {
return this.count - this.lowestCount;
}
Copy the code- Clear the queue, initializing the three variables in the constructor.
clear() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
Copy the code- Gets all the elements in the queue, iterates through the elements in the object, concatenates them with commas into a string and returns.
toString() {
if(this.isEmpty()){
return "";
}
let objString = `The ${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++){ objString = `${objString}.The ${this.items[i]}`; } return objString; } Copy the codeFor the complete code, go to queue.ts
Write test code
Once the queue is implemented, let’s test whether the methods in the queue work properly.
// The queue performs the test
import Queue from "./lib/Queue.ts";
const queue = new Queue();
/ / team
queue.enqueue("First data in the queue"); queue.enqueue("Second data in the queue"); queue.enqueue("Third piece of data in the queue"); / / out of the team queue.dequeue(); // Get the first element console.log(queue.peek()); // Get the queue size console.log(queue.size()); // Get all the elements in the queue console.log(queue.toString()); // Determine whether there is data in the queue console.log(queue.isEmpty()); // Clear the queue queue.clear(); Copy the codeThe result is as follows:
deque
A double-endian queue is a special queue that allows us to add and remove elements from both the front end and the back end.
Double-endian queue complies with both fifO and LIFO principles, so it can be said that it is a kind of data structure combining queue and stack.
In reality, there are many examples of double-ended queues, such as those in cinemas and restaurants. The person waiting in line to buy a movie ticket when he buys a movie ticket and leaves the line, he can go to the front of the line to ask some other small question. The person at the back of the line, who is temporarily unable to buy a ticket, leaves at the end of the line.
In computer science, to store a series of undo is used in the deque, each time the user to the software in an operation, the operation will be stored in a deque, when a user points to cancel the operation, the operation will pop-up, from the end of the queue in the predefined after a certain number of operations, the perform operation will be removed from the team first.
Implementation approach
A two-end queue has more elements than a queue, so the methods of getting the queue size, empting the queue, nulling the queue, and getting all the elements in the queue also exist in a two-end queue and the implementation code is the same.
Since elements can come and go on both ends of a double-ended queue, we need to implement the following function:
- Add an element to the head of the queue to determine whether the queue is empty and whether the head of the queue is 0.
- Adding an element to the end of a queue is equivalent to joining a queue.
- Get the first element of the queue, the same as get the first element of the queue
- Fetching the end of the queue is equivalent to fetching the top of the stack.
- Delete the first element of the queue, equivalent to the queue operation.
- Delete the last element of the team, equivalent to the combat operation.
When we look at the function we are going to implement above, we find that the double end queue is very different from the previous implementation, we have implemented all the other functions before, so we will only explain the implementation of the first queue to add elements.
For more detailed implementations of other functions, please refer to my other article on the difference between an array stack and an object stack
The implementation of the element added by the team leader is as follows:
- If the queue is empty, the append element function is called directly.
- If the first element key is greater than 0, the current first element key-1 needs to be placed in the queue, and then the current element is placed in the queue.
- If the key at the head of the queue is equal to 0, the entire element in the queue needs to be moved back one bit, leaving key 0 empty. The key at the head of the queue is reassigned to 0, and the current element is placed in key 0.
The implementation code
Next, let’s translate this idea into code.
- Create a new deque.ts file
- Declares the type of an object inside a two-ended queue
interface DequeObj {
[propName: number] :any;
}
Copy the code- Declare and initialize the variables needed for the double-ended queue in the constructor
private count: number;
private lowestCount: number;
private items: DequeObj;
constructor() {
this.count = 0;
this.lowestCount = 0; this.items = {}; } Copy the code- Implement the add element function at the head of the queue
addFront(item: any) {
if (this.isEmpty()){
this.addBack(item);
}else if(this.lowestCount > 0) { // The header element is greater than 0
this.lowestCount--; this.items[this.lowestCount] = item; }else{ // The first element of the queue is 0, we need to empty the 0 key in the queue, and move all the other data back one bit. for (let i = this.count; i > 0; i--){ this.items[i] = this.items[i - 1]; } // The queue length increases this.count++; // Set the header element to 0 this.lowestCount = 0; // Add the current element to key 0 at the head of the queue this.items[0] = item; } } Copy the codeFor the complete code, go to deque.ts
Write test code
// Double-ended queue test
import Deque from "./lib/Deque.ts";
const deque = new Deque();
// If the queue is empty, add elements to the head of the queue
deque.addFront("Team leader adds element"); console.log(deque.peekFront()); // Add elements at the end of the queue deque.addBack("Add elements to the end of the queue"); console.log(deque.peekBack()); // Add elements to the head of the queue if the head element is 0 deque.addFront("Team head element equals 0 add element"); console.log(deque.peekFront()); // add an element to the header if the header element is greater than 0 deque.removeFront(); deque.addFront("Team head element greater than 0 adds element"); console.log(deque.peekFront()); // Get the queue size console.log("Queue size :",deque.size()) // Add an element to the end of the queue deque.addBack("Add element to end of queue") // Get all the elements in the queue console.log("All elements in the queue:",deque.toString()) // Remove the header element deque.removeFront(); // Remove the last element of the queue deque.removeBack(); // Get the first element console.log("Team Leader element:",deque.peekFront()); // Get the last element of the queue console.log("Last element of the team:",deque.peekBack()); Copy the codeThe result is as follows:
To solve the problem
We implemented queues and double-endian queues above, so let’s look at two examples to understand these two data structures.
Queue to achieve the drum pass flower game
Since queues are often used in computers and in our real life, there are some modified versions of queues.
For example, loop queues are understood by implementing a game of drum and flower passing.
The rules of the game
The rules of the game are as follows:
- A group of people form a circle and place a flower in the hands of any one of them.
- Start to beat the drum, the person who gets the flowers will pass the flowers to the next person as soon as possible.
- When the drum stops, whoever has the flower in his hand at this time quits the circle and ends the game.
- Repeat the process until there is only one person left, and that person is the winner of the game.
Implementation approach
Now that we know the rules of the game, let’s think about the implementation:
- Declare a function that takes an array of participants as the number of rounds
- Function internally instantiates a queue declaring the elimination list variable.
- Join the team (form a circle)
- Pass flowers through the queue based on the number of times you pass flowers, append the top element of the queue to the end of the queue (if you pass flowers to someone next to you, your threat of elimination is immediately removed).
- The number of times passed in is completed (the drum stops), the first element of the team is removed from the stack, and the first element of the team is appended to the elimination list.
- When only one element is left in the queue, the remaining elements exit and the list of winners and eliminators is returned.
The implementation code
After the implementation is clear, we convert the above ideas into code:
import Queue from "./lib/Queue.ts";
/ * ** Beat the drum to pass the flower function* @param nameList List of participants* @param num How many times is a round * @returns {{eliminates: [], winner: string}} * / const hotPotato = (nameList=[], num=0) = > { // instantiate a queue const queue = new Queue(); // Eliminate the list of people const eliminateList = []; // All participants join the team for (let i = 0; i < nameList.length; i++){ queue.enqueue(nameList[i]); } If the queue size is greater than 1, the execution continues while (queue.size() > 1) { // Simulate a drum pass, given a number, then traverse the queue, remove an item from the beginning of the queue, and add it to the end of the queue. for (let i = 0; i < num; i++){ // Add the first element to the end of the team (if you pass a flower to someone next to you, your threat of elimination is immediately removed) queue.enqueue(queue.dequeue()); } // The drum stops, the flower pass ends, and the person who currently has the flower (team leader element) is eliminated. eliminateList.push(queue.dequeue()); } // Game over, return to eliminator and winner return { eliminates: eliminateList, winner: queue.dequeue() } } Copy the codeWrite test code
Above we realized the function of the game, next we will test whether the function we wrote is correct.
const names = ["Zhang"."Bill"."Fifty"."Zhu six"."Hao qi"."Liu eight"."Peng."];
// Eliminate a round every 9 times
const result = hotPotato(names,9);
for (let i = 0; i < result.eliminates.length; i++){
const name = result.eliminates[i];
console.log(`${name}, be eliminated in the game of drum passing flowers); } console.log('Game winner:${result.winner}`); Copy the codeFor complete code, go to examples.js
The result is as follows:
A two-ended queue implements a palindrome checker
A palindrome is a word, phrase, number, or sequence of characters that can be read forward or backward, such as madam or racecar.
There are several ways to implement palindrome detection. The simplest way is to reverse the string and check if it is the same as the original character. If they’re the same then it’s a palindrome.
We can also solve this problem with stacks, but it is easiest to solve palindrome problems with data structures using double-ended queues.
Implementation approach
The palindrome rule is that both sides are readable, so we can compare the first and last letters of a string. If both are equal, the string is a palindrome.
- Declare a function that takes the string to be tested
- Removes whitespace from the string and converts it to all lowercase letters
- Iterates through the string, adding each character of the string to a double-endian queue.
- Traverse the queue, the first queue and the last queue
- Check whether the characters at the beginning and end of the queue are equal, if not, the palindrome result is false
- If the size of the queue is greater than 1 and the result is true, continue to compare the first and last elements of the queue
The implementation code
Now that we have a clear idea of how to implement palindromes, we can translate the above ideas into code:
import Deque from "./lib/Deque.ts";
/ * ** Palindrome functions* @param sourceString Specifies whether it is a palindrome parameter * @returns {boolean} * / const palindromeDetection = function (sourceString) { // Check whether the parameter is valid if(sourceString === undefined || sourceString === null || sourceString.length === 0) { return false; } // Instantiate a double-ended queue const deque = new Deque(); // Remove whitespace from the string and convert it to lowercase const lowerString = sourceString.toLocaleLowerCase().split("").join(""); // Palindrome check result let isEqual = true; let firstChar,lastChar; // Join the queue for (let i = 0; i < lowerString.length; i++){ // charAt gets the character at the specified index deque.addBack(lowerString.charAt(i)); } // If the queue size is greater than 1 and the palindrome result is true, the validation continues while (deque.size() > 1 && isEqual){ // The first and last elements of the team are out of the team firstChar = deque.removeFront(); lastChar = deque.removeBack(); // Compare the last element and the first element to see if they are equal if(firstChar ! == lastChar){ isEqual = false; } } // Returns the validation result return isEqual; } Copy the codeWrite test code
The above code implements the palindrome function, so let’s see if the above code works
const testString = "madam";
const testStr = "admin";
const results = palindromeDetection(testString);
const testStrResult = palindromeDetection(testStr);
if (results){
console.log(`${testString}Is a palindrome `) }else{ console.log(`${testString}Not palindromes); } if(testStrResult){ console.log(`${testStr}Is a palindrome `); }else{ console.log(`${testStr}Not palindromes); Copy the codeFor complete code, go to examples.js
The result is as follows
Write in the last
- If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
- This article was first published in nuggets. Reprint is prohibited without permission 💌