JavaScript Data Structures and Algorithms Stacks and Queues_Basic Knowledge

Cause of learning

I once came across such a post when I was browsing V2EX.
Mathematics is completely left to the teacher. I want to learn some basic mathematics, probably at a high school level. What books do you recommend?
The poster who posted the message did not have advanced mathematics courses at the university and had been engaged in front-end work when he went out to work. I feel that my mathematical knowledge is lacking, so I want to catch up on mathematics.
After reading the post, I feel that it is very similar to me, because my major does not require advanced mathematics, and I also studied front-end. I also felt the difficulties caused by the lack of mathematical knowledge. At the same time, because my mathematical thinking is really not very good, I decided to work hard to learn basic mathematics and computer knowledge.
At that time, some people also said: "What data structures and algorithms are needed for the front end?" But I have my own views on this matter.
I don't think that the front-end does not need knowledge such as algorithms. In my opinion, the front-end has a solid computer foundation, which is extremely beneficial to its own development. I want to be a programmer. Rather than being a lifelong junior front-end and coder.
It can be regarded as an encouragement to myself. After all, the basics determine the upper limit, and I am really interested in computers, so even if it is tiring to learn, it is also very happy. So I went online and purchased the book "Learning JavaScript Data Structures and Algorithms". Together with the "Dahua Data Structures" I borrowed from the library, I started my preliminary study of data structures and algorithms.

Array operations in JavaScipt

The next step is the first part of the data structure, the stack.
The stack is an ordered collection that follows the last-in-first-out principle (LIFO, short for Last In First Out). The top of the stack is always the newest element.
For example: a stack is like a stack of books placed in a box. If you want to take the bottom book, you must first remove the top book. (Of course, you can’t take the book below first.)

Implementation of stack in JavaScipt
First, create a constructor.

/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

The stack needs to have the following methods:
push(element(s)): Add several elements to the top of the stack
pop(): Remove and return the top element of the stack
peek(): Returns the top element of the stack
isAmpty: Check whether the stack is empty, if it is empty, return true
clear: remove all elements from the stack
size: Returns the number of elements in the stack.
print: Display all the contents of the stack as a string
Implementation of push method
Explanation: A new element needs to be added to the stack, and the element position is at the end of the queue. In other words, we can use the push method of the array to simulate the implementation.

Implementation:

/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

Implementation of pop method

Explanation: It is necessary to pop the top element of the stack and return the popped value at the same time. You can use the pop method of the array to simulate the implementation.
Implementation:

/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

Implementation of peek method
Note: Viewing the top element of the stack can be achieved by using the array length.
Implementation:

/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

Implementation of other methods
Note: The first three are the core of the stack method, and the remaining methods are listed here at once. Because the queue to be discussed below will greatly overlap with this part.
Implementation:

/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

Practical Application

There are many practical applications of the stack. There is a function in the book that converts decimal to binary. (If you don’t know how to calculate binary, you can use Baidu.) The following is the source code of the function.
The principle is to enter the number to be converted, continuously divide by two and round. And finally use a while loop to concatenate all the numbers in the stack into a string for output.

/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

At this point, the study of stack comes to an end. Because there are many comments in the source code, the content of the source code will not be posted here.

Queue

Queue and stack are very similar data structures. The difference is that queue is first in first out (FIFO: First In First Out).
For example: When queuing up to buy tickets at the train station, first come first. (Those who jump in line are not counted). Isn’t it easy to understand~

Implementation of queue in JavaScipt

The implementation of queue is very similar to stack. The first is still the constructor:

/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

The queue needs to have the following methods:
enqueue(element(s)): Add several items to the end of the queue
dequeue(): Remove the first item of the queue (that is, the top item)
front(): Returns the first element of the queue, which is the latest added
The rest of the methods are the same as queue

Implementation of enqueue method

Description: Add several items to the end of the queue.
Implementation:

/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

Implementation of dequeue method

Description: Remove the first item from the queue.
Implementation:

/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

Implementation of front method

Description: Returns the first element of the queue, which is the latest one added.
Implementation:

/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:

/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

 for (var i = 0; i < nameList.length; i++) {
  queue.enqueue(nameList[i]);
 }

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。