What is a stack?

I think it’s important to have a model in mind when we think about data structures, for example, when we think about stacks, we think about gun magazines, think about bullets being first in, last in, first out.

And in lifeThe trayThe tray that is placed last is often taken out last when it is placed first. With this concept above, we are proceeding with the next step of summary.

A stack is a limited linear table:

  • LIFO( last in first out)Represents the element entered after the first popup of the stack space.
  • Restrictions allow insert or delete operations only at one end of a linear table. This end is calledTo the top of the stackInstead, call the other end the bottom of the stack.
  • Inserting new elements into a stack is also calledInto the stack,Into the stack, orThe pressure of stackThis operation puts the new element on top of the top element, making it the new top element.
  • Removing an element from a stack is also calledOut of the stackorReturn a stackIt is to delete the top element of the stack, so that its adjacent elements are called the new top element.

Here is a graphical representation of the stack structure

Features of the stack: first in first out, last in first out

The stack structure in a program

  • Function call stack: A(B(C(D()))) : A function call B, B call C, C call D; A is pushed on the stack during the execution of A, then B is pushed on the stack when B is executed, and functions C and D are pushed on the stack when C and D are executed. A->B->C->D (top of the stack); D->C->B->A;
  • Recursion: Why does recursion without a stop condition cause stack overflow? For example, function A is A recursive function that calls itself over and over again (it doesn’t pop the function off the stack because it hasn’t finished executing), pushes the same function over and over again, and queues Overfloat.

practice

There are 6 elements 6, 5, 4, 3, 2, 1 in the stack. Which of the following is not a legal order?

  • A: 5 4 3 6 1 2
  • B: 4 5 3 2 1 6
  • C: 3, 4, 6
  • D: 2

So let’s see. What the topic says by the order into the stack refers to is not one-time all into the stack, but have into have out, into the stack order is 6 -> 5 -> 4 -> 3 -> 2 -> 1.

A 5 4 3 1 6 -> 6 -> 6 -> 6 -> 6 -> 6 -> 2 -> 2 B 4 5 5 3 2 1 6 -> 6 -> 6 -> 6 -> 6 -> 6 -> 6 -> 6 C 3 4 4 5 5 5 ? 5 has not yet out of the stack 6 how can out of the stack ？？？？ 6 -> 6 -> 6 D 2 3 3 4 4 4 1 5 5 5 5 5 5 6 -> 6 -> 6 -> 6 -> 6 -> 6 -> 6Copy the code

Stack structure implementation

Stack common operations

  • push()Add a new element to the top of the stack.
  • pop()Removes the element at the top of the stack and returns the removed element.
  • peek()Returns the element at the top of the stack without making any changes to the stack. (This method does not remove the element at the top of the stack, just returns it.)
  • isEmpty()Returns if there are no elements on the stacktrueOtherwise returnfalse.
  • size()Returns the number of elements in the stack. The method and the arraylengthProperties are similar.
  • print()Returns the contents of the stack structure as a string.

JavaScript code implements the stack structure

// Write in Es5.
// Stack can be abstracted as loading a pistol magazine.
function Stack() {
  // To store data
  this.items = []
}

// Define basic stack operations

//1. Push the element onto the stack
Stack.prototype.push = function (element) {
  this.items.push(element)
}
//2. Pull the element from the stack
Stack.prototype.pop = function () {
  return this.items.pop()
}

//3. Look at the top of the stack
Stack.prototype.peek = function () {
  return this.items[this.items.length - 1]}//4. Check whether the stack is empty
Stack.prototype.isEmpty = function () {
  return this.items.length === 0
}

//5. Obtain the number of elements in the stack
Stack.prototype.size = function () {
  return this.items.length
}

//6. Check the current stack contents

Stack.prototype.print = function () {
  return this.items.join(' ')}module.exports = Stack
Copy the code

Test the stack structure of the package

const Stack = require('./stack')

var stack = new Stack()

stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

console.log(stack)               //Stack { items: [ 1, 2, 3, 4, 5 ] }

stack.pop()

console.log(stack)              //Stack { items: [ 1, 2, 3, 4 ] }

console.log(stack.peek())       / / 4

console.log(stack.isEmpty())    //false

console.log(stack.size())       / / 4

console.log(stack.print())      / / 1 2 3 4
Copy the code

Simple application of stack structure

Using the characteristics of the stack structure to achieve the package of decimal conversion to binary method.

Positive integers are converted to binary. The key points must be remembered: divide by two take mod, and then arrange in reverse order, high fill zero.

Code implementation

function dec2bin(dec) {
  let stack = new Stack()

  while (dec > 0) {
    / / into the stack
    stack.push(dec % 2)
    dec = Math.floor(dec / 2)}let bin = ""
  while(! stack.isEmpty()) { bin += stack.pop(); }return bin
}

let bin = dec2bin(10)

console.log(bin) / / 1010
Copy the code