JavaScript Data Structure — Stack (2)

Make writing a habit together! This is the fifth 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 article we learned what a stack is and how to implement a stack using classes and arrays. If you are not familiar with the concept of “stack”, please move on to the previous article: Angry Liver JavaScript Data Structures – Stack (1).

As we discussed at the end of the last article, one of the problems with implementing stacks in arrays is that array queries can be time-consuming and perform very poorly when the data volume is large. So in this article we’ll implement a stack using JavaScript objects.

Implement a stack with objects

The Stack class is initialized as follows:

class Stack {
  constructor() {
    this.count = 0;
    this.items = {}; }}Copy the code

Following the LIFO principles, create the same method in this class as in the previous article, as follows:

• push(): Adds a new element to the top of the stack
• pop(): Removes the new element at the top of the stack
• peek()Returns the element at the top 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

Just to clarify, in arrays, there are subscripts and array lengths by default, so you only need to store one value. So now we have an object, which is a key->value format, so can we simulate the access of an array by setting key as an index and value as a value?

So where does the index come from? It’s the count property defined at initialization.

The count attribute represents not only the number of elements on the stack, but also the key of the items object. When count is 0, items is an empty object; When count is 1, items indicates that there is already a key-value pair, and so on.

So let’s start with the simplest isEmpty and size methods:

size() {
  return this.count;
}
isEmpty() {
  return this.count == 0;
}
Copy the code

Then implement the push method to add elements:

push(value) {
  this.items[this.count] = value;
  this.count++;
}
Copy the code

The push method “pushes” the object by adding new key-value pairs and incrementing count.

Pop = pop; pop = pop;

pop() {
  if(this.isEmpty()) {
    return undefined;
  }
  this.count--;
  let item = this.items[this.count];
  delete this.items[this.count];
  return item;
}
Copy the code

The POP method needs to be said. If the object is empty, undefind is returned. If it is not empty, subtract count by one, either to match the last property of the object, or by one if the deletion succeeds.

Then find the value of the last attribute, use a variable to temporarily store, and then delete the attribute, and finally return the deleted value, and you are done.

Let’s try it and see if it works:

var stack = new Stack();
stack.push('Beijing');
stack.push('Shanghai');
Copy the code

The stack value is as follows:

{
   count: 2.items: {
     0: 'Beijing'.1: 'Shanghai'}}Copy the code

Then perform two more exits:

console.log(stack.pop()) // 'Shanghai'
console.log(stack.pop()) // 'Beijing'
console.log(stack.pop()) // undefined
console.log(stack)
// {count: 0, items: {}}
Copy the code

From the test results, the method written above is not a problem. Then add the remaining two methods:

peek() {
  if(this.isEmpty()) {
    return undefined;
  }
  return this.items[this.count - 1]}clear() {
  this.count = 0;
  this.items = {};
}
Copy the code

Implement the toString method

Arrays have toString methods by default. When we want to represent arrays as strings, we call arr.toString() and the array becomes a comma-separated string.

var arr = ['Beijing'.'Shanghai']
console.log(arr.toString()) // 'Beijing, Shanghai'
Copy the code

The toString method of an object returns ‘[object object]’. So we’ll also define a toString method that returns an array.

ES6’s object. values method converts the value of an Object directly into an array, which is easy to implement:

toString() {
  let arr = Object.values(this.items);
  return arr.toString();
}
Copy the code

The complete Stack class code is as follows:

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }
  push(value) {
    this.items[this.count] = value;
    this.count++;
  }
  pop() {
    if(this.isEmpty()) {
      return undefined;
    }
    this.count--;
    let item = this.items[this.count];
    delete this.items[this.count];
    return item;
  }
  size() {
    return this.count;
  }
  isEmpty() {
    return this.count == 0;
  }
  peek() {
    if(this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1]}clear() {
    this.count = 0;
    this.items = {};
  }
  toString() {
    let arr = Object.values(this.items);
    returnarr.toString(); }}Copy the code

At this point, we are almost done implementing stacks with objects, have you learned?

Join a study group

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