First, stack data structure

A stack is an ordered collection of elements that follow the last-in, first-out (LAST-in, first-out) principle. New elements added or to be deleted are stored at the same end of the stack, called the top, and the other end is called the bottom. In the stack, the new elements are near the top of the stack, and the old elements are near the bottom of the stack. 2. Implement an array-based stack

/** * Create a library of javascript data structures and algorithms * stack data structures * Add elements to the stack * Remove elements from the stack * how to use the stack class ** // stack is an ordered collection of first in, last out { Constructor () {this.items = [] // {1}} get() {return this.items} // Implement adding one or more elements to the top of stack push(ele) {this.items. Push (ele) Pop () {return this.items. Pop ()} // Return the element at the top of the stack, Peek () {return this.items[this.items. Length-1]} // If there are no elements in the stack, return true. Return this.items. Length === 0} clear() {this.items = []} // Return the number of elements in the stack. Size () {return this.items. Length}} size() {return this.items. Length}} Const stact = new Stack() stact.push(1) stact.push(2) stact.push(3) stact.push(4) stact.push(5) // console.log( 'pop',stact.pop()) //1 console.log( 'peek',stact.peek()) //1 console.log( 'get',stact.get()) //1 console.log( 'size',stact.size()) console.log( 'isEmpty',stact.isEmpty())Copy the code

3. Implement a Stack class based on javascript objects

/** * Create a library of javascript data structures and algorithms * stack data structures * Add elements to the stack * Remove elements from the stack * how to use the stack class ** // stack is an ordered collection of first in, last out { Constructor () {this.items = {} // {1}} get() {return this.items} // Return the number of elements in the stack. Size () {return this.count} // Insert element push(ele) {this.items[this.count] = ele this.count++} // Remove elements from the stack, pop elements from the stack, Pop () {if (this.isempty ()) {return undefined} this.count-- const result = this.items[this.count]; Delete this.items[this.count]; // Save the top value of the stack before deleting it and return the deleted element after deleting it. Return result} // Returns the top element of the stack, Peek () {if (this.isempty ()) {return undefined} // because count is from return this.items[this.count-1] // } // Return true if there are no elements in the stack, Clear () {this.items = {} this.count = 0} // Tostring () {if (this.isEmpty()) {return ''} let objString = '${this.items[0]}' for (let I = 1; i < this.count; I ++) {objString = '${objString},${this.items[I]}'} return objString}} Const stact = new Stack() stact.push(1) stact.push(2) stact.push(3) stact.push(4) stact.push(5) console.log( 'get',stact.get()) //1 // console.log('pop', stact.pop()) //1 // console.log( 'get',stact.get()) //1 console.log('peek', stact.peek()) //1 console.log('toString', stact.toString()) //1 // console.log( 'size',stact.size()) // console.log( 'isEmpty',stact.isEmpty())Copy the code

Second, queue data structure

1. Definition of queues

A queue is an ordered group of items following the principle of advanced kitchen. 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.

Examples: movie theaters, cafeterias, grocery checkout counters.

2. Implement a queue

/** * This file implements the objective * queue data structure * double-endided queue data structure * add elements to queue and double-endided queue * Add elements from queue and double-endided queue * simulate loop queue with drum pass game * check whether a phrase constitutes a palindrome ** // Class Queue {constructor() {this.count = 0; This.lowestcount = 0; Get () {return this.items} // declare some methods available for queues // Add one or more items to the end of the queue enqueue(ele) { This.items [this.count] = ele this.count++} // Remove the first item in the queue and return the removed element dequeue() {if (this.isempty ()) {return undefined } const result = this.items[this.lowestCount]; // Save the first element delete this.items[this.lowestcount]; // Delete the first element this.lowestCount++; // this.count--; Peek () {if (this.isempty ()) {return undefined} return this.items[this.lowestcount]} // Returns true if the queue contains no elements, Otherwise return false isEmpty() {return this.size() === 0} // Return the number of elements in the queue size() {return this.count - this.lowestCount} // Empty the queue clear() { this.items = {}; this.count = 0; This.lowestcount = 0} toString() {if (this.isEmpty()) {return "} let objString = `${this.items[this.lowestCount]}` for (let i = this.lowestCount + 1; i < this.count; I ++) {objString = '${objString},${this.items[I]}'} return objString}} const queue = new Queue() queue.enqueue(' first ') Queue.enqueue (' 2nd ') queue.enqueue(' 3rd ') queue.enqueue(' 4th ') console.log(' View queue header information ',queue.peek()) Console.log (' check queue size ',queue.size()) console.log(' check whether it isEmpty ', queue.isempty ()) console.log(' remove heap column information ', Queue.dequeue ()) console.log(' View queue header information ',queue.peek()) console.log(' format toString', queue.tostring ()) Console.log (' View queue size ', queue.size()) console.log(' Remove heap information ', queue.dequeue()) console.log(' Remove heap information ', Queue.dequeue ()) console.log(' remove heap information ', queue.dequeue()) console.log(' View queue size ', queue.size()) module.exports = queueCopy the code

3. Double-endian queue data structures

A double-endian queue is a special queue that allows us to add and a cluster of elements from both the front end and the back end.

Examples of double – end queues in the display of life are movie theaters, restaurants and so on. For example, a person who has just bought a ticket can go straight back to the head of the line if he or she needs to ask a few more simple questions. In addition, if the person at the end of the line is in a hurry, he can just leave the line.

Implement a two-ended queue

/** * This file implements the objective * queue data structure * double-endided queue data structure * add elements to queue and double-endided queue * Add elements from queue and double-endided queue * simulate loop queue with drum pass game * check whether a phrase constitutes a palindrome ** // Constructor () {this.count = 0; class Deque {constructor() {this.count = 0; This.lowestcount = 0; Get () {return this.items} // Add the element addFrot(ele) {if (this.isempty ()) {// to the front of the queue This.addback (ele)} else if (this.lowestCount > 0) {// The first element was removed by lowestCount! == 0 this.lowestCount--; This. Items [this.lowestCount] = ele} else {// Start moving all elements one bit for (let I = this.count; i > 0; i-- ) { this.items[i] = this.items[i - 1]; } this.count++; this.lowestCount = 0; This.items [0] = ele}} // Add one or more items to the end of the queue addBack(ele) {this.items[this.count] = ele this.count++} // RemoveFront () {if (this.isempty ()) {return undefined} const result = remove the first item in the queue and return the removed element this.items[this.lowestCount]; // Save the first element delete this.items[this.lowestcount]; // Delete the first element this.lowestCount++; If (this.isempty ()) {this.isempty () {this.isempty ();}} this.count-- const result = this.items[this.count]; Delete this.items[this.count]; // Save the top value of the stack before deleting it and return the deleted element after deleting it. Peek () {if (this.isempty ()) {return undefined} return this.items[this.lowestcount]} // Returns true if the queue contains no elements, Otherwise return false isEmpty() {return this.count === 0} // Return the number of elements in the queue size() {return this.count} // Clear the queue clear() {this.items = {}; this.count = 0; This.lowestcount = 0} toString() {if (this.isEmpty()) {return "} let objString = `${this.items[this.lowestCount]}` for (let i = this.lowestCount + 1; i < this.count; i++) { objString = `${objString},${this.items[i]}` } return objString } } const queue = new Deque() // Queue. AddFrot (' first ') / / queue addBack (' 2 ') / / queue. AddFrot (' 3 ') / / queue. AddBack (' 4 ') / / Console. log(' view queue header information ',queue.peek()) // console.log(' view queue size ',queue.size()) // console.log(' check whether it isEmpty ', queue.isempty ()) // Console. log(' Remove heap information ', queue.dequeue()) // console.log(' View queue header information ',queue.peek()) // console.log(' Remove last element ', Queue. Peek ()) // console.log(' view queue size ',queue.size()) // console.log(' format toString', queue.removeback ()) module.exports = DequeCopy the code

Use queues to solve real-world problems

1, implement a drum pass flower game

In this game, children circle around a circle and pass flowers as quickly as possible to the person next to them. At some point the message stops, and whoever spends that time in their hands rolls out the circle and ends the game. Repeat the process until there is only one child left (winner).

/** * queue = require("./ queue "); Function hotPhtato (elementList,num) {const queue = new queue (); const elimitatedList = []; For (let I = 0; i < elementList.length; i++) { queue.enqueue(elementList[i]) } while (queue.size() > 1) { for (let i = 0; i < num; I++) {// console.log('queue.dequeue()',queue.dequeue()) queue.enqueue(queue.dequeue()) // console.log('queue.enqueue()',queue.get())} elimitatedList.push(queue.dequeue()); } return { elimitated: ElimitatedList, winner:queue.dequeue()}} const names = [' Guan Yu ', 'Zhang Fei ',' Liu Bai ', 'Yellow Zhong ', 'Zhuge Liang '] const result = hotPhtato(names, 7) result. Elimitated. ForEach (name = > {the console. The log (` ${name} were knocked out in the game of musical chairs `)}) console. The log (` winner ${result. The winner} `)Copy the code

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 different algorithms that check whether a phrase or string is palindrome. The easiest way is to reverse the string and check that it is the same as the source string. If the two are the same, then it is a palindrome. We could also do this with a stack, but the easiest way to solve this problem with data structures is to use a double-endian queue.

/** */ var Deque = require(". "); Function palindromeChecker(aString) {const deque = new deque (); Const lowerString = aString. ToLocaleLowerCase (). The split (' '). The join (' ') / / remove the blank space console. The log (" lowerString." lowerString) let isEqual = true; let firstChar, lastChar; for (let i = 0; i < lowerString.length; i++){ deque.addBack(lowerString.charAt(i)) } while (deque.size() >1 && isEqual) { firstChar = deque.removeFront(); lastChar = deque.removeBack(); console.log("firstChar",firstChar) console.log("lastChar",lastChar) if (firstChar ! == lastChar) { isEqual = false; } } return isEqual } console.log(palindromeChecker('abcdyydcba'))Copy the code