# Stack and queue of JavaScript data structure and algorithm

- 2020-12-09 00:43:44
- OfStack

To study the cause of

Once when browsing V2EX, I came across such a post.

Mathematics completely returned to the teacher, want to learn back to 1 some basic mathematics, is probably high school level, what books recommend?

Post of the building of the university does not have a high number of courses, go out to work 1 straight in the front of the work. Feel the lack of mathematical knowledge, so want to make up 1 to make up mathematics.

Looked at the post, and I feel very similar, because my major is not open high number, I learn is also the front end. I also feel the difficulty caused by the lack of mathematical knowledge. At the same time, because their mathematical thinking is not very good, so decided to work hard to cram in the basic knowledge of mathematics and computer.

At that time, some people said, "What data structure and algorithm is needed for the front end?" But I have my own opinion on this matter.

I don't think that the front end does not need knowledge like 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. Instead of a lifetime of primary front end and yard farmers.

It is also an encouragement to myself. After all, the foundation determines the upper limit, plus I am really interested in computers, so even if learning is very tired, but also very happy. Therefore, I went to the Internet to buy the book "Learning JavaScript Data Structure and Algorithm", and started the preliminary study of data structure and algorithm with the book "Big Talk Data Structure" borrowed from the library.

JavaScipt array operation

Next comes the first part of the data structure, the stack.

A stack is an ordered set that follows the last in, first out principle (LIFO, full name Last In First Out). The top of the stack is always the newest element.

For example, a stack is like a stack of books in a box. Before you can take down the books underneath, you have to remove the books on top. (Of course, you can't take the book first.)

Implementation of the JavaScipt stack

First, create a constructor.

```
/**
* The stack's constructor
*/
function Stack() {
// Use arrays to simulate stacks
var item = [];
}
```

The stack needs to have the following approach:

push(element(s)): Add several elements to the top of the stack

pop(): Removes and returns the top element of the stack

peek(): Returns the top element of the stack

isAmpty: Checks if the stack is empty and returns true if it is

clear: Removes all elements from the stack

size: Returns the number of elements in the stack.

print: Displays everything on the stack as a string

Implementation of the push method

Note: You need to add a new element to the stack at the end of the queue. That is, we can simulate the implementation using the array's push method.

Implementation:

```
/**
* The element is pushed onto the stack and placed at the end of the array 1 position
* @param {Any} element Accepts an element of unlimited type
*/
this.push = function(element) {
items.push(element);
};
```

Implementation of the pop method

Note: You need to pop the top element off the stack and return the value that was popped. The pop method of the array can be used to simulate the implementation.

Implementation:

```
/**
* Pop top element
* @return {Any} Returns the value ejected
*/
this.pop = function() {
return items.pop();
};
```

Implementation of the peek method

View the top of the stack elements, can be used to achieve the length of the array.

Implementation:

```
/**
* Look at the top of the stack elements
* @return {Any} Returns the top element of the stack
*/
this.peek = function() {
return items[items.length - 1];
}
```

Implementation of the remaining methods

Note: The first three are the core of the stack method, and the remaining methods are listed here. Because the queues that We're going to talk about, we're going to have a lot of overlap with this.

Implementation:

```
/**
* Determines whether the stack is empty
* @return {Boolean} Returns if the stack is empty true, Returns if it is not null false
*/
this.isAmpty = function() {
return items.length === 0
};
/**
* Clear everything in the stack
*/
this.clear = function() {
items = [];
};
/**
* Returns the length of the stack
* @return {Number} The length of the stack
*/
this.size = function() {
return items.length;
};
/**
* Displays everything in the stack as a string
*/
this.print = function() {
console.log(items.toString());
};
```

The practical application

Stack application is more practical, there is a 10 to 2 hexadecimal function. The following is the source code of the function.

The idea is to input the number you want to convert, divide it by 2 and round it off. Finally, the while loop is used to concatenate all the numbers in the stack into a string output.

```
/**
* will 10 Convert to base number 2 Hexadecimal Numbers
* @param {Number} decNumber To convert 10 Hexadecimal Numbers
* @return {Number} The transformed 2 Hexadecimal Numbers
*/
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 stack is one paragraph long. Because of the comments in the source code, the contents of the source code are not posted here.

The queue

Queues and stacks are much like data structures, except that queues are first in, first out (FIFO:First In First Out).

For example: Waiting in line to buy a ticket at a train station, first come, first served. (queue-jumping does not count), is not very easy to understand ~

Implementation of queues in JavaScipt

Queues are implemented much like stacks. The first is the constructor again:

```
/**
* Queue constructor
*/
function Queue() {
var items = [];
}
```

The queue needs to have the following methods:

enqueue(element(s)): Adds several items to the end of the queue

dequeue(): Removes the first item in the queue (that is, the top item)

front(): Returns the first element of the queue, the most recently added one

The remaining methods are the same as the queue

Implementation of the enqueue method

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

Implementation:

```
/**
* Pushes the element to the end of the queue
* @param {Any} ele The element to push into the queue
*/
this.enqueue = function(ele) {
items.push(ele);
};
```

Implementation of the dequeue method

Description: Removes item 1 of the queue.

Implementation:

```
/**
* Put the number in the queue 1 Element pop up
* @return {Any} Returns the element that was popped
*/
this.dequeue = function() {
return items.shift()
};
```

Implementation of the front method

Description: Returns the first element of the queue, the most recently added one.

Implementation:

```
/**
* View the rows of the queue 1 An element
* @return {Any} Returns the number in the queue 1 An element
*/
this.front = function() {
return items[0];
};
```

These three methods are at the heart of the data structure, queues. It's easy to understand.

The practical application

The book is a small game of drumming and passing flowers. The idea is that when you loop to the appropriate location, the queue pops up that element. The winner is the one who is left.

The source code is as follows:

```
/**
* The element is pushed onto the stack and placed at the end of the array 1 position
* @param {Any} element Accepts an element of unlimited type
*/
this.push = function(element) {
items.push(element);
};
```

0
So much for queues. The next installment will cover another data structure: linked lists.

feeling

Most of the time, reading, directly read the introduction to the algorithm or 1 some data structure books, are very confused. Later found that reading from their own can understand the beginning, from the shallow deep is suitable for their own way of learning.