Review the old and learn the new, the program ape play wild basic skills of data structure ~

The core topic of this article is: Stack.

basis

define

A Stack, also known as a Stack, is a linear table that allows operations to be performed on only one end. The operation is characterized by LIFO (Last In First Out), as shown In the magazine below.

Note the magazine, not the magazine, but the revolver.

Top of the stack: The end of a linear table where operations are allowed.

Bottom of stack: The other end of a linear table, the fixed end on which operations are not allowed.

Empty stack: Contains no elements.

Be careful not to be confused with heap.

In general, defining a stack requires an initial size, which is the initial capacity of the stack. When the number of elements that need to be placed is larger than this amount, it needs to be expanded.

Characteristics of the

Last in, first out, only one end.

Basic operation method

  • Push: Adds an element to the top of the stack (pushes bullets into magazines)
  • Pop: Pops the top element of the stack (the magazine pops a bullet)
  • top: returns the element at the top of the stack. Note: a glance, not a pop)
  • size: returns the number of elements in the stack (counting bullets left)
  • clear: Empty stack (soha, empty)
  • isEmpty: Whether stack is empty (confirm, empty magazine)

implementation

The continuous classification based on storage space can be divided into arrays and linked lists. Their respective characteristics are shown in the head diagram.

Sequential storage (array-based) : The use of a set of contiguous addresses to store elements from the bottom of the stack to the top of the stack, with a pointer to the current top of the stack element position. Can be divided into sequential stack, shared stack.

Sequential stack: A sequential stack is called a sequential stack, which uses a set of storage cells with consecutive addresses to store data elements from the bottom of the stack to the top of the stack, with a pointer (top) indicating the position of the current top of the stack.

Shared stack: Two sequential stacks can share a one-dimensional data space by taking advantage of the relatively unchanged position of the bottom of the stack. The bottom of the two stacks are set at both ends of the shared space, and the top of the two stacks extends to the middle of the shared space.

  • Custom base stack based on arrays
// stack.js // Class MyStack {constructor() {this.stack = []; } // push(ele) {this.stack.push(ele); // return this.stack.length; // No return value is required. } // pop() {return this.stack.pop(); } // return stack length size() {return this.stack.length; IsEmpty () {return this.stack.length === 0; } // clear stack clear() {this.stack = []; } top() {return this.stack[this.stack.length - 1]; } } exports.Stack = MyStack;Copy the code

Chain storage structure (based on linked list) : The stack using chain storage is called chain stack, which has the advantage of sharing storage space and improving efficiency for multiple stacks, and does not have the problem of stack overflow. It is usually in the form of a single linked list, and stipulates that operations are carried out at the head of the single linked list.

The implementation based on linked list will be implemented in the following part of linked list

performance

The main operations of the stack are push and pop, so it mainly summarizes the performance of the in and out of the stack

The array-based stack is loaded and unloaded at the end of the array, so the complexity is O (1).

The stack based on the linked list is in the head of the linked list to push and push operations, so the complexity is O (1);

When the number of operations is small, the performance of the stack implemented in the two ways is not very different. When there is a large amount of data, the stack based on linked list needs to perform new operation, so it has a certain performance disadvantage compared to the stack based on array (with initial capacity).

Case scenario

Implements matching of pairs of symbols

// Check whether the parentheses in the string match properly. // Use the stack, but the implementation of this method does not strictly follow the stack format, just for reference ideas. const Stack = require('./Stack.js') function is_leagal_breaks(string) { let i = 0, stacks = new Stack.Stack(); while (i < string.length) { let ele = string[i]; If (ele === '(') {stacks. Push (ele); } else if (ele === ')') {if (! stacks.isEmpty()) { stacks.pop(); } else { return false; }} i++; } // Return stacks. IsEmpty (); } //test let { log } = console; let str1 = '(3(1)4)f(5)(6)(7)d)d'; let str2 = 'q(w)r(r)t(flak(jhs((diuhivb)zk)xlhuidsf)kjb)'; let str3 = 'e(e)t' log(is_leagal_breaks(str1)) log(is_leagal_breaks(str2)) log(is_leagal_breaks(str3)) // More action -- Undo and restore document editing.Copy the code

A simple calculator based on the inverse Polish expression (integer calculation only).

Under normal circumstances, when calculating ordinary expressions, the calculator has to use the recursive way to determine the priority, which will be inefficient or even crash for complex expressions, while the inverse Polish expression only needs a simple operation in and out of the stack to complete the calculation of any ordinary expressions.

Overall idea: infix expression is transformed into suffix expression, based on the suffix expression calculation. The point is to convert infix expressions into postfix expressions.

A simple comparison between infix expressions and postfix expressions is shown in the following table:

Infix expression Postfix expressions (inverse Polish expressions)
a+b ab+
a+(b-c) abc-+
a+d*(b-c) adbc-*+

Infix expressions are converted to postfix expressions

Ideas:

  • Establish two stacks: operator stack S1 and data transfer stack S2

  • Scan the expression sequentially from left to right,

    • When an operand is encountered, S2 is pushed

    • Encounter operator

      • If S1 is empty or the top element is an open parenthesis’ (‘, the operator is pushed directly onto S1
      • Otherwise, if the priority of the operator is higher than that of the top element on the stack S1, the operator is also pushed onto the stack S1
      • Otherwise, the top element of S1 is popped and pushed into S2, and the operator is again compared to the new top element of S1 until pushed in

    • Encounter parentheses

      • If the opening parenthesis is’ (‘, push the opening parenthesis directly onto the stack S1
      • In the case of the close parenthesis’) ‘, the top operator of stack S1 is successively pushed into stack S2 until the open parenthesis’ (‘ is encountered, at which point the parentheses are discarded.

  • At the end of the scan, the operators in stack S1 are popped and pushed into stack S2

  • Pop the elements in S2 in turn, and the reverse order of the result is the suffix expression corresponding to the infix expression.

Code implementation:

const Stack = require('./Stack.js') const priority_map = { "+": 1, "-": 1, "*": 2, "/": 2}; function infix_exp_2_postfix_exp(exp){ let stack = new Stack.Stack(); let postfix_lst = []; for(let i = 0; i<exp.length; i++){ const item = exp[i]; // If it is a number, put it directly into postfix_lst. isNaN(item)){ postfix_lst.push(item); }else if (item == "("){stack.push(item); }else if (item == ")"){// Open the top element of the stack until the open parenthesis while(stack.top()! = "("){ postfix_lst.push(stack.pop()); } stack.pop(); Else {// When an operator is encountered, pop the operator at the top of the stack until the operator at the top of the stack has a lower priority than the current operator while(! stack.isEmpty() && ["+", "-", "*", "/"].indexof (stack.top()) >= 0 && Priority_map [stack.top()] >= Priority_map [item]){// Add the pop-up operator to postfix_lst postfix_lst.push(stack.pop()); } // The current operator is pushed stack.push(item); }} // After the for loop ends, there may be elements in the stack that pop into postfix_lst while(! stack.isEmpty()) { postfix_lst.push(stack.pop()) } return postfix_lst }; // 12+3 console.log(infix_exp_2_postfix_exp(["12","+", "3"])) // 2-3+2 console.log(infix_exp_2_postfix_exp(["2","-", "3", "+", "2"])) // (1+(4+5+3)-3)+(9+8) var exp = ["(","1","+","(","4","+","5","+","3",")","-","3",")","+","(","9","+","8",")"]; console.log(infix_exp_2_postfix_exp(exp)) // (1+(4+5+3)/4-3)+(6+8)*3 var exp = ['(', '1', '+', '(', '4', '+', '5', '+', '3', ') ', '/', '4', '-', '3', ') ', '+', '(',' 6 ', '+', '8', ') ', '*', '3'] console.log(infix_exp_2_postfix_exp(exp)) console.log(infix_exp_2_postfix_exp(["12","+", "3","*", "5"])) console.log(infix_exp_2_postfix_exp(["12","*", "3","+", "5"]))Copy the code

Computes based on postfix expressions

Ideas:

  • Read from left to right in sequence. When the value is numeric, the operation is pushed.
  • When an operator is encountered, the top two elements are popped and evaluated using the operator, and the result is pushed onto the stack
  • Until the entire expression is evaluated.

Code implementation:

function calc_exp(exp){ let stack = new Stack.Stack(); for(let i = 0; i < exp.length; i++){ const item = exp[i]; If ([" + ", "-", "*", "/"]. IndexOf (item) > = 0) {/ / pop up from the stack two elements const value_1 = stack. Pop (); const value_2 = stack.pop(); Const exp_str = value_2 + item + value_1; Const res = parseInt(eval(exp_str)); // Push the result onto the stack stack.push(res.tostring ()); }else{ stack.push(item); Return stack.pop(); return stack.pop(); return stack.pop(); }; var exp_1 = ["4", "13", "5", "/", "+"]; var exp_2 = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]; var exp_3 = [ '1', '4', '5', '+', '3', '+', '+', '3', '-', '9', '8', '+', '+' ]; console.log(calc_exp(exp_1)); console.log(calc_exp(exp_2)); console.log(calc_exp(exp_3));Copy the code

The complete calculator needs further work

Support + – * / ()

Multidigit, supporting decimals,

Compatible processing, filter any whitespace characters, including Spaces, tabs, feed characters

\