[TOC]

Abstract

This paper masters four classic application scenarios of stack: parenthesis pairing, expression evaluation, browser forward and backward, function call; Hand by hand to implement a simple version of the calculator.

What is a stack

Let’s take a look at the definition of stack in Baidu Encyclopedia: stack (stack), also known as stack, is a linear table with limited operations. Defines linear tables that only perform insert and delete operations at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack.

Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element. To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element.

The realization of the stack

Stacks, like arrays and linked lists, are linear data structures. Some programming languages do not have a stack as a data structure, but it is easy to implement a stack using arrays or linked lists.

Through arrays

In Java, the Stack (Stack class) is implemented through arrays. Here we use arrays to implement a simple Stack:

package com.lonely.wolf.note.stack;

import java.util.Arrays;

/** * implements a custom stack */ based on arrays
public class MyStackByArray<E> {
    public static void main(String[] args) {
        MyStackByArray stack = new MyStackByArray();
        stack.push(1);
        System.out.println("Stack number of valid elements:" + stack.size);/ / output 1
        System.out.println("View top element on stack:" + stack.peek());/ / output 1
        System.out.println("Is the stack empty?" + stack.isEmpty());/ / output is false
        System.out.println("Pop top element on stack:" + stack.pop());/ / output 1
        System.out.println("Is the stack empty?" + stack.isEmpty());/ / output true
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("Stack number of valid elements:" + stack.size);3 / / output
        System.out.println("Pop top element on stack:" + stack.pop()); / / output 4
    }

    private Object[] element;// An array of elements
    private int size;// Valid elements in the stack
    private int DEFAULT_SIZE = 2;// Default array size

    public MyStackByArray(a) {
        element = new Object[DEFAULT_SIZE];
    }

    /** * check whether the array is empty@return* /
    public boolean isEmpty(a){
        return size == 0;
    }

    /** * view the top element *@return* /
    public synchronized E peek(a) {
        if (size == 0) {return null;
        }
        return (E)element[size-1];
    }


    /** * view and pop the top element *@return* /
    public E pop(a) {
        if (size == 0) {return null;
        }
        E obj = peek();
        size--;// Use the size attribute to omit element removal
        return obj;
    }

    /** ** stack *@param item
     * @return* /
    public E push(E item) {
        ensureCapacityAndGrow();
        element[size++] = item;
        return item;
    }

    /** ** */
    private void ensureCapacityAndGrow(a) {
        int len = element.length;
        if (size + 1 > len){/ / capacity
            element = Arrays.copyOf(element,len * 2); }}}Copy the code

Through queues

In addition to arrays, linked lists and other data structures can also be implemented. The key to implementing a stack is to pay attention to the last-in, first-out nature of the stack.

# 225 in Leetcode is to implement a stack using two queues, as follows:

You can implement a LIFO stack with only two queues and support all four operations of a normal stack (push, top, POP, and Empty). You can only use the basic operations of queues (i.e. push to Back, peek/pop from Front, size, and is empty).

Before solving this problem, we should first understand the characteristics of queues. One of the most important characteristics of queues is fifO, so no matter which queue we put the elements in first, the last element out is still fifO, which seems to be unable to implement the last-in-first-out feature of stacks.

Implementation approach

In order to satisfy the nature of the stack, we must make the first element to be queued last, so we can do this:

Using one queue as the main queue, fetching elements from the main queue (mainQqueue) on each stack, and another queue as the secondary queue (secondQueue), storing only elements, each time storing elements in the secondQueue. The mainQueue elements are then placed in the secondQueue, and the two queues are switched so that each time the queue exits, only the mainQueue elements are retrieved.

Let’s draw a flow chart to help understand this process:

  1. In the element1.

We put the element in secondQqueue first, and mainQueue is empty, so we don’t need to move the element, just swap the two queues, so we still get an element 1 in mainQueue and no element in secondQueue:

  1. Let’s go ahead and add elements2.

If the mainQueue has an element in it, it will be queued in secondQueue. If the mainQueue has an element in it, it will be queued in secondQueue.

  1. Let’s go ahead and add elements3 。

The same is true for element 3, again placing the elements in secondQqueue, then placing the two elements in mainQueue back to secondQueue at once, and finally swapping the two queues:

Most algorithms are like this, the key is to clear up the idea, and the rest is the process of code translation, which is relatively easy to achieve as long as the boundary control and other considerations are well done:

package com.lonely.wolf.note.stack;

import java.util.LinkedList;
import java.util.Queue;

public class MyStackByTwoQueue {
    public static void main(String[] args) {
        MyStackByTwoQueue queue = new MyStackByTwoQueue();
        queue.push(1);
        queue.push(2);
        System.out.println(queue.pop());
    }

    private Queue<Integer> mainQueue = new LinkedList<>();
    private Queue<Integer> secondQueue = new LinkedList<>();


    public void push(int e){
        secondQueue.add(e);
        if(! mainQueue.isEmpty()){ secondQueue.add(mainQueue.poll()); }// The new element e is the header of the mainQueue
        Queue temp = mainQueue;
        mainQueue = secondQueue;
        secondQueue = temp;
    }


    public int top(a){
        return mainQueue.peek();
    }

    public int pop(a){
        return mainQueue.poll();
    }

    public boolean empty(a) {
        returnmainQueue.isEmpty(); }}Copy the code

Classic stack application scenario

Because the stack is a data structure with limited operation, it is also used in a limited number of scenarios. Here are a few classic application scenarios.

Browser Forward and Back

The forward and backward of the browser is typically fifin and fifout, because there is forward and backward, we need to define two stacks: forwardStack and backStack. When we go from page 1 to page 4, we push the visited pages into backStack one by one:

When backStack is empty, it can’t go back. And when the page is pushed from backStack to forwardStack at the same time, it can be pushed from forwardStack as it goes:

Brackets pairs

Using the stack to verify that the parentheses in a string are perfectly paired is very simple, because the close parentheses must be paired with the closest left parentheses, which satisfies the lifO feature. So we can traverse the string directly, meet the left parenthesis stack, met right parenthesis and see if the current matching brackets on the top of the stack, if does not match the illegal, if matching elements will stack stack, and continue to cycle, until the cycle after the whole string, if the stack is empty it happens to all matching brackets, the string is valid.

Leetcode 20 questions

Question 20 in Leetcode is a pair of parentheses, and the title looks like this:

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order.

Knowing the above solution, the code is relatively simple to implement:

public static boolean isValid(String s){
       if (null == s || s.length() == 0) {return false;
       }

       Stack<Character> stack = new Stack<>();
       Map<Character,Character> map = new HashMap<>();
       map.put(') '.'(');
       map.put('] '.'[');
       map.put('} '.'{');
       for (int i=0; i<s.length(); i++){char c = s.charAt(i);
           if (c == '(' || c == '[' || c == '{'){
               stack.push(c);// open parenthesis on the stack
           }else{
               if(stack.isEmpty() || map.get(c) ! = stack.peek()){return false;
               }
               stack.pop();// If the match is successful, the stack is removed}}return stack.isEmpty();
   }
Copy the code

Expression evaluation

Algorithmic expressions are also a classic use of stacks. For the sake of explanation, we assume that the expression contains only +, -, *, and /. Then we want to solve the representation 18-12/3+5*4.

In fact, this problem can also be implemented using two stacks, one for holding operands, called the operand stack, and the other for holding operators, called the operator stack. Specific ideas are as follows:

  1. Iterates through the expression, and when it encounters an operand, pushes it onto the operand stack.
  2. When an operator is encountered, it is pushed directly into the operator stack if the stack is empty.
  3. If the operator stack is not empty, then comparing with operator stack elements: if the current operator precedence is higher than the top operator, continued to press it into the stack operator, if the current operator precedence is lower than the top operator or equal, from take two operands operator stack elements, removed from the stack operations operator, press the operation result and into the operand stack.
  4. Continue comparing the current operator to the element at the top of the operator stack.
  5. Continue to follow the above steps for traversal, when the traversal is over, the current two stack elements are taken out for operation to get the final result.

Leetcode questions 227

Given a valid string expression s, please implement a basic calculator to evaluate and return its value. Integer division preserves only integer parts. S consists of integers and operators (‘+’, ‘-‘, ‘*’, ‘/’) separated by some Spaces.

This problem can be solved using the ideas described above, but in addition, we should consider two points when examining the problem:

  1. There’s whitespace in the expression, and we need to get rid of whitespace
  2. Operands can have multiple bits, which means we need to compute the operands first.

Use two stacks to solve

If we follow the above ideas and use two stacks to do this problem, although the code is a bit cumbersome, the idea is still clear, the specific code is as follows:

public static int calculateByTwoStack(String s){
       if (null == s || s.length() == 0) {return 0;
       }
       Stack<Integer> numStack = new Stack<>();// Operand stack
       Stack<Character> operatorStack = new Stack<>();// Operator stack

       int num = 0;
       for (int i = 0; i<s.length(); i++){char c = s.charAt(i);
           if (Character.isDigit(c)){/ / digital
               num = num * 10 + (c - '0');
               if (i == s.length() - 1 || s.charAt(i+1) = =' ') {// If the last digit or the next digit is a space, the number needs to be pushed
                   numStack.push(num);
                   num = 0;
               }
               continue;
           }
           if (c == '+' || c == The '-' || c == The '*' || c == '/') {if (s.charAt(i-1) != ' ') {// If the preceding digit is not a space, the integer needs to be pushed onto the stack
                   numStack.push(num);
                   num = 0;
               }
               if (c == The '*' || c == '/') {// If it is multiplication and division, then the current stack of multiplication and division need to be calculated first
                   while(! operatorStack.isEmpty() && (operatorStack.peek() ==The '*' || operatorStack.peek() == '/')){
                       numStack.push(sum(numStack,operatorStack.pop()));// Push the calculated result onto the stack again}}else {// In addition and subtraction, the priority is already the lowest, so all data in the current stack needs to be computed
                   while (!operatorStack.isEmpty()){
                       numStack.push(sum(numStack,operatorStack.pop()));
                   }
               }
               operatorStack.push(c);
           }
       }
       // Finally start traversal: two operands, one operator to compute
       while(! numStack.isEmpty() && ! operatorStack.isEmpty()){ numStack.push(sum(numStack,operatorStack.pop()));// The calculated result is pushed again
       }
       return numStack.pop();// There must be one result left in the stack
   }

   private static int sum(Stack<Integer> numStack,char operator){
       int num1 = numStack.pop();
       int num2 = numStack.pop();
       int result = 0;
       switch (operator){
           case '+':
               result = num2 + num1;
               break;
           case The '-':
               result = num2 - num1;
               break;
           case The '*':
               result = num2 * num1;
               break;
           case '/':
               result = num2 / num1;
               break;
           default:}return result;
   }
Copy the code

In the preceding question, we can also use the re to remove all Spaces in the expression

Use a stack to solve

In fact, this problem because there is only addition, subtraction, multiplication and division, so we can actually cheat, using only one stack can also be implemented.

Because multiplication and division must take precedence over addition and subtraction, we can first calculate multiplication and division and then put the result back into the expression, and finally get the whole expression is addition and subtraction operation, the specific method is:

We iterate over the string S and record the operator that precedes each number using the variable preOperator. For the first number in the expression, we can default the operator that precedes it to plus. Each time we iterate to the end of a number (i.e., read an operator, or read a space, or iterate to the end of a string), we use the preOperator to determine the calculation:

  • Plus sign: Pushes the number directly onto the stack.
  • Minus sign: pushes the corresponding negative number onto the stack.
  • Multiply/divide: Computes the number and the top of the stack and replaces the top of the stack with the calculated result.

In the end, you just need to add all the data in the stack to get the result, as shown in the following code example:

public static int calculateOneStack(String s){
    if (null == s || s.length() == 0) {return 0;
    }
    Stack<Integer> stack = new Stack<>();
    char preOperator = '+';// The previous operator is plus by default
    int num = 0;
    for (int i = 0; i<s.length(); i++){char c = s.charAt(i);
        if (Character.isDigit(c)){
            num = num * 10 + (c - '0');
        }
        if((! Character.isDigit(c) && c ! =' ') || i == s.length()-1) {// Determine whether the number processing is finished. If it is finished, the number or calculation result needs to be pushed onto the stack
            switch (preOperator){
                case '+':
                    stack.push(num);// Add adds numbers directly to the stack
                    break;
                case The '-':
                    stack.push(-num);// Subtraction pushes negative numbers onto the stack
                    break;
                case The '*':
                    stack.push(stack.pop() * num);// The multiplication rule requires the calculation to be pushed
                    break;
                case '/':
                    stack.push(stack.pop() / num);// The division rule requires the calculation result to be pushed
                    break;
                default:
            }
            preOperator = c;
            num = 0; }}int result = 0;
    while(! stack.isEmpty()){// Add all the data in the stack to get the result
        result+=stack.pop();
    }
    return result;
}
Copy the code

A function call

In addition to the above three classic scenarios, in fact, our ordinary method call is also realized by using the stack. Every time we call a new method, we will define a temporary variable and push it onto the stack as a stack frame. When the method execution is completed, the corresponding stack frame of the current method will be pushed off the stack.

conclusion

This article focuses on the stack, a restricted data structure, and implements a simplified version of the stack through arrays. It also shows how to implement a stack through two queues. Finally, we list the four classic application scenarios of stack: bracket pairing, expression evaluation, browser forward and backward, function call, etc., and the two scenarios of bracket pairing and expression evaluation will generate different algorithm problems.