Introduction: Why study data structure, what can it help us? Can solve what problems, home page data structure is not a specific programming language, it teaches us is a way of thinking, that is, how to store data in a better way and solve some problems, through learning data structure, can greatly broaden our thinking mode. Master the data structure and algorithm, we will look at the depth of the problem, the Angle of solving the problem will be greatly different, for the improvement of personal logical thinking, is also a qualitative leap.
The following points show the principles and scenarios of their implementation:
What is a stackWhat is a queue- What is a linked list
- What is a set
- What is a dictionary
- What is a binary tree
What is a stack
When introducing the stack, we need to understand the concept of arrays and the common methods of arrays to better understand the principle of the stack.
Array: JavaScript arrays are used to store multiple values in a single variable, essentially objects.
How to create arrays:
let arr1 = [1.2.3] // [element0, element1, ..., elementN]
let arr2 = new Array(1.2.3) // new Array(element0, element1[, ...[, elementN]])
let arr3 = new Array(3); // new Array(arrayLength)
Copy the codeWhat are the common methods for arrays?
console.log(Object.getOwnPropertyNames(Array.prototype);)
// ["length", "constructor", "concat", "copyWithin", "fill", "find", "findIndex", "lastIndexOf", "pop", "push", "reverse", "shift", "unshift", "slice", "sort", "splice", "includes", "indexOf", "join", "keys", "entries", "values", "forEach", "filter", "flat", "flatMap", "map", "every", "some", "reduce", "reduceRight", "toLocaleString", "toString"]
Copy the codeA few chestnuts to warm up
const arrs = ['basketball'.'football'.Table tennis];
Copy the codeAccessing an array element
console.log(arrs[0]) / / basketball
console.log(arrs[arrs.length - 1]) / / table tennis
Copy the codeAdds elements to the end of the array
const arrs = ['basketball'.'football'.Table tennis];
arrs.push('badminton')
console.log(arrs) // [" basketball ", "football "," table tennis ", "badminton "]
Copy the codeStack principle: LAST in first Out (LIPO)
New and removed elements are at the top of the stack, and the other end is called the bottom of the stack. In the stack, new elements are near the top of the stack, and old elements are near the top of the stack. You can think of it as a stack of books, or a stack of dishes, as long as you can understand what it means.
So how do you implement a stack?
First we need to consider a few things: what methods do stacks have or what they do:
Push () :Adds one or more new elementsPop () :Removes the element at the top of the stack and returns the removed elementPeek () :Returns the element at the top of the stack without making any changes to the stackIsEmpty () :Checks whether the stack is empty and returns a Boolean valueClear () :Clear elements of the stackThe size () :Returns the number of elements on the stack
Implement a Stack:
class Stack {
constructor () {
this.items = []
}
push(data){
this.items.push(data)
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1]}isEmpty(){
return this.items.length === 0
}
size () {
return this.items.length
}
clear() {
this.items = []
}
}
Copy the codeTesting:
const foo = new Stack()
foo.push(1) / / [1]
foo.push(2) / / [1, 2]
foo.push(3) / / [1, 2, 3]
foo.push(4) / / [1, 2, 3, 4]
foo.pop() / / [1, 2, 3]
foo.clear() / / []
Copy the codeThat’s the easy way to do it.
But if the presence of large amounts of operation data in an array that may not be the most efficient, most of the methods of time complexity is O (n), know to find the means to iterate the whole array element, n represents the length of the array, if there are lots of elements of the array, so the time will be longer, so is there a better way to achieve?
A: Yes. Use objects instead of storage and declare variables to record the current stack size.
class Stack {
constructor () {
this.items = {}
this.count = 0
}
push(data){
this.items[this.count] = data
this.count ++
}
pop() {
if(this.isEmpty()) {
return undefined
}
this.count --
const result = this.items[this.count]
delete this.items[this.count]
return result
}
peek() {
if(this.isEmpty()) {
return undefined
}
return this.items[ this.count - 1]}isEmpty(){
return this.count === 0
}
size () {
return this.count
}
clear() {
this.items = {}
this.count = 0}}Copy the codeIn fact, the above version is not perfect, if we directly change the structure of the data or the object will lead to confusion of the data structure, such as:
const foo = new Stack()
foo.items = null
foo.push(1) // TypeError
Copy the codeJavaScript does not have the concept of private attributes, but can be simulated using the Symbol attribute or using the WeakMap data structure. Please refer to the following simple code example:
Simulate private property: Symbol
const _items = Symbol('item') // Declare a key
class Stack {
constructor () {
// The convention is underlined and named [private attributes].
this[_items] = {}
this._count = 0
}
push(data){
this[_items][this._count] = data
this._count ++
}
...
}
Copy the codeSimulate the private property: WeakMap
const _items = new WeakMap(a)class Stack {
constructor () {
// Store items with Stack as its own reference
_items.set(this[])},push(data){
const list = _items.get(this)
list.push(data)
}
pop(){
const list = _items.get(this)
const result = list.pop()
return result
}
...
}
Copy the codeNone of the above is perfect, but you can’t have your cake and eat it, so make some trade-offs according to your application scenario.
What problems can be solved with stacks?
Reference force buckle of the original subject example, try to use stack thinking to solve
From the power buttonProblem 20 valid parentheses:
/ * * *@param {string} s
* @return {boolean}* /
var isValid = function(s) {
let stack = []
let left = ['('.'['."{"]
for (let i = 0; i< s.length; i++) {
let ch = s[i]
if(left.includes(ch)) {
stack.push(ch)
}
if(stack.length === 0) return false
if (ch == ') '&& stack.pop() ! ='(') return false
if (ch == '] '&& stack.pop() ! ='[') return false
if (ch == '} '&& stack.pop() ! ='{') return false
}
return stack.length === 0
};
Copy the codeWhat is a queue
Queue An ordered group of items following a first-in, first-out (FIFO) principle. New elements are added at the end of the queue and removed from the top. The latest element must be at the end of the queue. Queuing to buy a ticket
Common methods for queues:
The enqueue () :Adds one or more new elements.Dequeue () :Removes the first item in the queue (that is, the first item in the queue) and returns the removed element.Peek () :Returns the first element in the queue – the first to be added and the first to be removed.IsEmpty () :Determines whether the queue is empty and returns a Boolean value.Clear () :Empty the elements of the queue.The size () :Returns the number of elements in the queue.
Implement a Queue:
class Queue {
constructor(){
this.count = 0; // Record the size of the object
this.lowestCount = 0; // Trace the first element
this.items = {} // Initialize the object
}
enqueue(data) {
this.items[ this.count ] = data
this.count ++
}
dequeue(){
if(this.isEmpty()) {
return undefined
}
const result = this.items[ this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount ++
return result
}
peek(){
if(this.isEmpty()) {
return undefined
}
return this.items[this.lowestCount]
}
isEmpty(){
return this.size() === 0
}
size () {
return this.count - this.lowestCount
}
clear(){
this.count = 0;
this.lowestCount = 0;
this.items = {}
}
}
Copy the codeThe application scenario of queues: Think of a javascript event loop, but the underlying implementation principle is fifO.
The advanced version:deque
A special queue that allows us to add and remove elements on both the front end and the back end at the same time can be implemented in a careful way that combines stack and queue methods. Take a look at the following code:
class Deque {
constructor(){
this.count = 0; // Record the size of the object
this.lowestCount = 0; // Trace the first element
this.items = {} // Initialize the object
}
// Add elements to the front of the queue
addFront(data) {
if(this.isEmpty()) {
this.addBack(data)
}else if( this.lowestCount > 0) {
this.lowestCount --
this.items[ this.lowestCount] = data
}else {
for (let i = this.count; i > 0 ; i--) {
this.items[i] = this.items[ i - 1]}this.count ++;
this.lowestCount = 0;
this.items[0] = data
}
}
// Add elements to the back end of the queue
addBack(data) {
this.items[ this.count ] = data
this.count ++
}
// Delete elements at the back end of the queue
removeBack() {
if(this.isEmpty()) {
return undefined
}
this.count --
const result = this.items[this.count]
delete this.items[this.count]
return result
}
// Delete the element at the front of the queue
removeFront(){
if(this.isEmpty()) {
return undefined
}
const result = this.items[ this.lowestCount]
delete this.items[this.lowestCount]
this.lowestCount ++
return result
}
// Returns the first element at the front of the queue
peekBack() {
if(this.isEmpty()) {
return undefined
}
return this.items[ this.count - 1]}// Returns the first element at the back of the queue
peekFront(){
if(this.isEmpty()) {
return undefined
}
return this.items[this.lowestCount]
}
// Whether to return empty
isEmpty(){
return this.size() === 0
}
// Queue size
size () {
return this.count - this.lowestCount
}
// Clear the queue
clear(){
this.count = 0;
this.lowestCount = 0;
this.items = {}
}
}
Copy the codeTake a look at its underlying principle through an example:
Verify a simple palindrome number
let strings = `madam`
function isPalindrome(aString) {
const deque = new Deque()
const lowerString = aString.toLocaleLowerCase().split(' ').join(' ')
let isEqual = true;
let firstChar, lastChar;
for (let i = 0; i < aString.length; i++) {
deque.addBack(lowerString.charAt(i))
}
while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront()
lastChar = deque.removeBack()
if(firstChar ! == lastChar) { isEqual =false}}return isEqual
}
Copy the codeAbove content is the most simple JavaScript data structure is introduced, if plus ca change from the bottom to master a variety of data structure evolution of the form, using the principle of their characteristics and implementation, then meet some hard problems when they have a lot of divergent thinking, of course, we also must master the methodology in the treatment of the data structure.
The last
This article series refers to “learning JavaScript data structure and algorithm 3rd edition” for sorting and induction, hoping to help you.