Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Hello, I’m Yang Chenggong.

In the last two articles, we learned about the simplest data structure — arrays. Arrays are the most basic data sets. They provide very flexible ways to add, change, and delete items at will.

Starting with this article, we’ll learn about a new data structure, the stack. The stack is essentially an array, but it is not as flexible as an array. The stack has its own rules for storing and manipulating data, which adds a layer of restrictions on the basis of the array.

You must be familiar with this rule, summed up in four words – last in, first out.

What is a stack?

Definition: A stack is an ordered collection that follows lifO.

LIFO is called LIFO. Remember that, too. Don’t be surprised if your interviewer is going to ask you about LIFO.

Last-in, first-out means that a set of data is added to the array in order of precedence, and when it is time to fetch (delete), the last data to enter is fetched first, and the first data to enter is fetched last.

In addition to the last in, first out rule, there is also the “ordered collection”. Ordered means that the collection is ordered, not out of order, like the sorting of arrays, and certainly not in stacks, because stacks are not allowed to change order.

For example, when you go to the canteen to get food, you see a stack of dinner plates, which can be considered a typical stack.

There are two ends of a stack. Take a stack of dinner plates for example. The top plate is at the top of the stack, and the bottom plate is at the bottom of the stack. So whether you put a plate or take a plate, the top end of the stack is always used first and the bottom end is used last.

This also confirms the stack principle: last in first out, advanced last out.

We use an array [‘ Beijing ‘,’ Shanghai ‘,’ Chengdu ‘] to represent the stack, and draw a picture to get a clearer picture of the stack structure:

So, in an array, the first element is the bottom of the stack, and the last element is the top of the stack, so don’t get confused.

In addition, the stack is also used in programming languages to hold variables and method calls. For example, the “function call stack” in JavaScript and the browser’s return record are all applications of stacks.

Implementing a stack

Above we introduced the concept of stack, and what the characteristics and principles of stack are. However, JavaScript does not provide the data type “stack” natively, so we will implement a stack class based on the array.

class Stack {
  constructor() {
    this.lists = []
  }
}
Copy the code

The code above uses a Lists property to hold the data in the stack. The default value is an empty array. Following LIFO principles, you also need to create methods in this class that specify the in/out operations of the stack. The method is as follows:

  • push(): Adds a new element to the top of the stack
  • pop(): Removes new elements at the top and bottom of the stack
  • peek(): returns the top and bottom elements of the stack
  • isEmpty(): Checks whether there are elements in the stack, and returns true if there are none
  • clear(): Clears all elements in the stack
  • size(): Returns the number of elements in the stack

In fact, these methods are relatively simple, we directly on the code:

class Stack {
  constructor() {
    this.lists = []
  }
  / / into the stack
  push(item) {
    this.lists.push(item)
  }
  / / out of the stack
  pop() {
    this.lists.pop()
  }
  peek() {
    this.lists[this.lists.length - 1]}isEmpty() {
    return this.lists.length == 0
  }
  clear() {
    this.lists = []
  }
  size() {
    return this.lists.length
  }
}
Copy the code

Worth mentioning here are JavaScript’s native push and pop methods, which are designed with stack principles in mind. Push is called pushing, adding new elements to the top of the stack; Pop calls out the stack and removes the first element at the top of the stack, so we just use those two methods.

With the Stack class defined, let’s use it:

var stack = new Stack()
console.log(stack.isEmpty()) // true
Copy the code

Then perform the push operation:

stack.push('Beijing')
stack.push('Shanghai')
console.log(stack.size()) / / 2
console.log(stack.peek()) // 'Shanghai'
Copy the code

Add one more:

stack.push('chengdu')
console.log(stack.size()) / / 3
console.log(stack.peek()) // select * from *;
console.log(stack.lists) // [' Beijing ', 'Shanghai ',' Chengdu ']
Copy the code

There are currently three elements in the stack. Let’s do a stack exit:

stack.pop()
console.log(stack.size()) / / 2
console.log(stack.lists) // [' Beijing ', 'Shanghai ']
Copy the code

You see, “Chengdu” was the last to be added and the first to be removed.

Is there room for improvement?

Above we based on ES6 Class syntax, the data stored in an array, simulated the stack operation method, the basic implementation of a custom stack.

But there is one more question to consider: if the array is very large, with 1000 pieces of data, is there a problem?

Here’s a quick reminder: searching through an array, manipulating elements, whatever you do, essentially iterates through the array until you find the target element. This way, if the array is very large, the query will be inefficient. In addition, arrays ensure that the elements are sorted in order, thus taking up more memory.

Is there a way to get and manipulate elements directly, without iterating, and implement all the functions of the stack? Of course there is, which is our JavaScript object.

In the next article, we’ll implement a stack using JavaScript objects.

Join a study group

This article source public number: programmer success. This is the third chapter of learning JavaScript data structures and algorithms, this series will be updated for a month, welcome to pay attention to the public account, click “add group” to join our learning team ~