Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the stack and queue of Javascript data structure". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to implement the stack and queue of Javascript data structures.

Stack (stack)

Stack is an abstract data structure with last-in-first-out (Last-in-First-Out,LIFO) characteristics.

To know what the stack looks like, the most common examples are a stack of plates and a bullet-loaded magazine. And for example, the browsers we use on the Internet have "back" and "forward" buttons. The back operation is to unstack the address of the page (top of the stack) you are currently browsing and go back to the previous address. The editing software we use, such as IDE,Word,PhotoShop, their undo operation is also implemented by stack, the specific implementation code of the software may be quite different, but the principle is the same.

Because of the characteristics of last-in-first-out, only the elements at the top of the stack can be operated at a time, and any elements that are not at the top of the stack cannot be accessed. To access the following elements, you must first remove the upper elements. So it is an efficient data structure.

Use Javascript to implement a stack, usually we can use an array. You can make a simple package.

Stack implementation

The stack usually needs to implement the following common functions:

Push (insert a new element and make it the top of the stack)

Pop (the top element of the stack goes off the stack and returns the top element of the stack)

Peek (if you want to know which one is added at the end of the stack, use this method. Returns the element at the top of the stack without leaving the stack. It is an auxiliary method)

Clear (clear stack)

IsEmpty (returns true if the stack is empty, false otherwise)

Size (returns the number of stack elements)

Class Stack {constructor () {this.items = [];} push (item) {this.items.push (item);} pop () {return this.items.pop ();} peek () {return this.items [this.items.length-1];} clear () {this.items = [] } isEmpty () {return this.items.length = 0;} size () {return this.items.length;}} const stack = new Stack (); stack.push ('caterpillar'); stack.push ('swift'); stack.push (' python'); stack.push ('javascript'); console.log (stack.isEmpty ()); / / falseconsole.log (stack.size ()); / / 4console.log (stack.peek ()) / / javascriptconst removedItem = stack.pop (); console.log (removedItem); / / javascriptconsole.log (stack.peek ()); / / pythonstack.clear (); console.log (stack.isEmpty ()); / / trueconsole.log (stack.size ()); / / 0 solve practical problems

So here is an example of how the stack can be applied to solve practical problems.

An example of converting decimal to binary:

Function transitionToBin (decNumber) {const stack = new Stack (); do {/ / the low values calculated in each cycle are put into the stack stack.push (decNumber% 2); decNumber = Math.floor (decNumber / 2);} while (decNumber > 0); let result =''; / / at this time, the converted binary values are stored in stack, and the top of the stack is high, down in turn. While (stack.size () > 0) {/ / from the top of the stack to result + = stack.pop ();} return result;} const binNumber = transitionToBin (321); console.log ('binNumber:', binNumber); other applications of the stack

Stacks are also used to hold variables and method calls in memory. When the function is called, the stack is pressed, and when the result is return, the stack is released. For example, recursion, which we often use, is an example of stack applications.

For example, the following example of calculating factorial:

Function factorial (n) {return n > 1? N * factorial (n-1): n;} console.log (factorial (4))

Simple queue (Queue)

In addition to the stack, queues are also a common data structure. A queue is a linear data structure made up of sequential elements, and unlike a Last-in-First-Out,LIFO, it follows a first-in, first-out (First-In-First-Out,FIFO).

The queue adds a new element at the end of the queue and removes the element at the top.

In reality, the most common example of queuing is queuing.

Queues are also widely used in computers. For example, computer CPU job scheduling (Job Scheduling), peripheral online concurrency (spooling), breadth-first search of trees and graphs (BFS)

Queue implementation

A queue data structure, mainly to implement two operations:

Enqueue pushes a new element into the queue

Dequeue removes an existing element from the queue

We create a class to encapsulate a queue. We can use javascript's native array to store the data contents, and javascript's own functions to implement queue operations.

Class Queue {constructor () {this.items = [];} / push enqueue (item) {this.items.push (item);} / remove dequeue () {return this.items.shift ();} / / queue header element peek () {return this.items [0] } / / null judge isEmpty () {return this.items.length = 0;} size () {return this.items.length;}} queue application-breadth-first search (breadth-first search,BFS) of the tree

When we traverse a tree, we can use stack ideas for depth-first traversal, or we can use queue ideas for breadth-first traversal. Suppose we have the following tree-shaped data structure, and we look for all its node values.

Const treeData = {node: {value: 12, children: [{value: 30, children: [{value: 22, children: null}, {value: 10, children: [{value: 5] Children: null}, {value: 4, children: null}]}]}, {value: 6, children: [{value: 8, children: null} {value: 70, children: null}]}]}}

We traverse it with the breadth-first idea of the queue. The code and diagram are as follows:

Function bfs (tree) {/ / prepare an empty queue const queue = new Queue (); queue.enqueue (tree); / / an array used to display the results const result = []; do {/ / dequeue let node = queue.dequeue (); result.push (node.value) If (node.children & & node.children.length > 0) {node.children.forEach (sub = > {queue.enqueue (sub);});}} while (queue.size () > 0); / / display the traversal result console.log ('result:', result.join (',');} bfs (treeData.node) / / result: 12, 30, 6, 22, 10, 8, 70, 5, 4

Priority queue

In practice, some queues need some special processing methods, and those who leave the queue rules are not necessarily the first to enter the queue and the first to leave the queue. For example:

The triage of patients in the hospital, giving priority to the treatment of severe cases.

When we sell a commodity, we can sell it according to the purchase price of the goods in stock, and give priority to those with high purchase price.

Thus, there is a priority queue. A priority queue is an extension of a normal queue, which differs from a normal queue in that the elements in the queue have a specified priority (or weight). Let the high priority line up in front of the queue and give priority to leaving the queue. Priority queues have all the features of a queue, including basic operations, except that an internal sort is added.

Priority queue implementation

Because some rules are set, we can store queues in sequential storage instead of chained storage. In other words, all nodes can be stored in an array.

To meet the above conditions, we can use the linear data structure to implement it, but the time complexity is high, so it is not the best way.

Linear data structure to implement priority queue

If we want to implement the priority queue, there will be two ways.

The first is to insert at the end of the queue without considering anything else. When removing, it is necessary to find the appropriate element in the queue according to the priority to remove.

The second is that when inserting an element, the appropriate location is found according to priority, and when removed, it is removed directly from the front of the queue.

Let's take the second case as an example to implement a priority queue:

Class QItem {constructor (item, priority) {this.item = item; this.priority = priority;} toString () {return `${this.item}-${this.priority}`;} class PriorityQueue {constructor () {this.queues = [];} / push enqueue (item, priority) {const Q = new QItem (item, priority) Let contain = false; / / the queue itself is always based on priority, from big to small / / so find the first position for (let I = 0; I) that is smaller than the value to be inserted.

< this.queues.length; i++) { if (this.queues[i].priority < q.priority) { this.queues.splice(i, 0, q); contain = true; break; } } // 都比它大，放最后 if (!contain) { this.queues.push(q); } } // 移除 dequeue() { return this.queues.shift(); } // 队列头元素 peek() { return this.queues[0]; } isEmpty() { return this.queues.length === 0; } size() { return this.queues.length; }}const queue = new PriorityQueue();queue.enqueue('K40', 3100);queue.enqueue('K50', 5000);queue.enqueue('K10', 6100);queue.enqueue('K10', 6000);queue.enqueue('K10', 5600);queue.enqueue('K50', 4600);queue.enqueue('K40', 5900);console.log(queue.dequeue());console.log(queue.dequeue());console.log(queue.dequeue());console.log(queue.dequeue());console.log(queue.dequeue());console.log(queue.dequeue());console.log(queue.dequeue());/*QItem { item: 'K10', priority: 6100 }QItem { item: 'K10', priority: 6000 }QItem { item: 'K40', priority: 5900 }QItem { item: 'K10', priority: 5600 }QItem { item: 'K50', priority: 5000 }QItem { item: 'K50', priority: 4600 }QItem { item: 'K40', priority: 3100 }*/Heap（堆）数据结构实现优先队列 上面是简单的使用一个线性数据结构，实现了一个优先队列。我们也可以用实现。这种堆数据存储的时候也是一个线性的，只是这些数据的存放位置有一定规则。 堆可以理解为可以迅速找到一堆数中的最大或者最小值的数据结构 堆是具有特殊特征的完全二叉树（也叫二叉堆）。 二叉堆特点： 它是一个完全二叉树（complete binary tree） 的数据结构。所谓完全二叉树（complete binary tree）,就是整个二叉树，除了底层的叶子节点，其他的层都是填满的，而且底层的叶子节点，从左到右不能有空的。（这样一个完全二叉树就能使用 Array 这种线性结构来存储） 大顶堆（Max heap） ：父节点的值大于或者等于子节点的值，堆顶是这个堆的最大元素 小顶堆（Min heap） ：父节点的值小于或者等于子节点的值，堆顶是这个堆的最小元素 因为完全二叉树的特性，我们可以用一个数组来存储二叉堆 二叉堆是实现堆排序和优先队列的基础。二叉堆常用的应用场景就是优先队列，它处理最大、最小值效率很高。同时堆排序算法也用到了二叉堆。 代码实现一个二叉堆 二叉堆的插入和删除操作比较复杂，我们用 max-heap 举例说明。 插入（enqueue）操作 新元素一律先插入到堆的尾部 依次向上调整整个堆的结构（一直到根即可） HeapifyUp 删除（dequeue）操作 取出顶部元素（因为它永远是最大那个） 将尾元素替换到顶部（先不用管它的大小） 依次从根部向下调整整个堆的结构（一直到堆尾即可） HeapifyDown 下面是一个 max-heap 的实现。comparator 函数里面修改一下，就可以变成一个 min-heap class Heap { constructor(comparator = (a, b) =>

A-b) {this.arr = []; this.comparator = (iSource, iTarget) = > {const value = comparator (this.arr [iSource], this.arr [iTarget]); if (Number.isNaN (value)) {throw new Error (`Comparator should evaluate to a number. Got ${value}! `);} return value;}} enqueue (val) {/ / insert into the end this.arr.push (val); / / Bubble up to find the appropriate location this.siftUp ();} dequeue () {if (! this.size) return null; const val = this.arr.shift () Const rep = this.arr.pop (); this.arr.splice (0,0, rep); this.siftDown ();} get size () {return this.arr.length;} siftUp () {/ / New element index let index = this.size-1 / / according to the rules of the complete binary tree, here we can obtain the index value of the corresponding parent node const parent = (I) = > Math.floor ((I-1) / 2) according to the value of the element index index; if (parent (index) > = 0 & this.comparator (parent (index), index)

< 0) { // 如果父节点存在，并且对比值比当前值小，则交互位置 this.swap(parent(index), index); index = parent(index); } } siftDown() { let curr = 0; const left = (i) =>

2 * I + 1; const right = (I) = > 2 * I + 2; const getTopChild = (I) = > {/ / if the right node exists and the value of the right node is larger than that of the left node return (right (I))

< this.size && this.comparator(left(i), right(i)) < 0) ? right(i) : left(i); }; // 左节点存在，并且当前节点的值，小于子节点中大的那个值，交换 while (left(curr) < this.size && this.comparator(curr, getTopChild(curr)) < 0) { const next = getTopChild(curr); this.swap(curr, next); curr = next; } } // 交换位置 swap(iFrom, iTo) { [this.arr[iFrom], this.arr[iTo]] = [this.arr[iTo], this.arr[iFrom]]; }}const heap = new Heap();heap.enqueue(56);heap.enqueue(18);heap.enqueue(20);heap.enqueue(40);heap.enqueue(30);heap.enqueue(22);console.log('heapify: ', heap.arr.join(', '));heap.dequeue();console.log('step 1: ', heap.arr.join(', '));heap.dequeue();console.log('step 2: ', heap.arr.join(', '));heap.dequeue();console.log('step 3: ', heap.arr.join(', '));// heapify: 56, 40, 22, 18, 30, 20// step 1: 40, 30, 22, 18, 20// step 2: 30, 20, 22, 18// step 3: 22, 20, 18 如上面代码所示，数据进入队列是无序的，但在出队列的时候，总是能找到最大那个。这样也实现了一个优先队列。 小顶堆在 React Scheduler 事务调度的包应用 Scheduler 存在两个队列，timerQueue（未就绪任务队列） 和 taskQueue（就绪任务队列）。当有新的未就绪任务被注册，就会 push 到 timerQueue 中，并根据开始时间重新排列任务顺序。 push 方法是在一个叫 schedulerMinHeap.js 的文件中基于最小堆（min-heap）来实现的。schedulerMinHeap 源码 export function push(heap: Heap, node: Node): void { const index = heap.length; heap.push(node); siftUp(heap, node, index);} 看到代码中，在 push 之后，调用了 siftUp 来重新整理顺序 function siftUp(heap, node, i) { let index = i; while (index >

0) {const parentIndex = (index-1) > 1; const parent = heap [parentIndex]; if (compare (parent, node) > 0) {/ / The parent is larger. Swap positions. Heap [parentIndex] = node; heap [index] = parent; index = parentIndex;} else {/ / The parent is smaller. Exit. Return;}

Here the parentIndex is calculated by using the method of displacement (equivalent to dividing by 2 and then tailing), handsome!

At this point, I believe you have a deeper understanding of "how to implement the stack and queue of Javascript data structures". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.