What is a Stack?

FIFO queue, or stack queue, is a collection model based on FIFO policy.

Usage scenarios

Stacks are a common data structure in everyday life, if you notice.

You have a stack of files on your desk. Putting and fetching files is a simple stack operation.

You open your email account and the latest message comes first. If someone sends you a new message and you click accept, the new message is at the top of your unread list, that’s pushing. You click on the messages from top to bottom to read them, and those unread messages, one by one, are removed from your unread list, and that’s the unstack operation.

You click on a page, then click on a link in the page, and so on until you want to go back to the previous page, you start clicking on the back button, and the previous pages go out of the stack again. Similarly, the editor’s fallback function is an example of pushing in and out of the stack.

Java implementation

Stack

We first define the stack interface, a complete stack interface, should contain the following four methods, namely:

  • Into the stack
  • Out of the stack
  • Whether the stack is empty
  • Number of elements in the stack

Here is the stack interface definition:

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack;

public interface Stack<Item> {

    /**
     * add an item
     *
     * @param item
     */
    void push(Item item);

    /**
     * remove the most recently added item
     *
     * @return
     */
    Item pop();

    /**
     * is the stack empty?
     *
     * @return
     */
    boolean isEmpty();

    /**
     * number of items in the stac
     */
    int size();

}

Copy the code

FixedCapacityStackOfStrings

First, we implement the simplest stack: a constant volume stack, that is, a stack with a fixed capacity, and the elements of the stack are all strings.

A stack implementation needs a place to hold elements of the stack, so we use arrays.

It also has a variable N that marks the number of elements in the current stack.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack; import java.util.Iterator; import java.util.Spliterator; import java.util.function.Consumer; / * * * String constant volume stack: * fixed capacity type String stack * / public class FixedCapacityStackOfStrings {private String [] a; // stack entries private int N; // size public FixedCapacityStackOfStrings(intcap) {
        a = new String[cap];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void push(String item) {
        a[N++] = item;
    }

    public String pop() {
        returna[--N]; }}Copy the code
  • test
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;

public class FixedCapacityStackOfStringsTests {

    public  static void main(String[] args){

        FixedCapacityStackOfStrings fixedCapacityStackOfStrings=new FixedCapacityStackOfStrings(10);
        System.out.println("fixedCapacityStackOfStrings : size="+fixedCapacityStackOfStrings.size()+",isEmpty="+fixedCapacityStackOfStrings.isEmpty());

        fixedCapacityStackOfStrings.push("A");
        fixedCapacityStackOfStrings.push("Aaha");
        System.out.println("fixedCapacityStackOfStrings : size="+fixedCapacityStackOfStrings.size()+",isEmpty="+fixedCapacityStackOfStrings.isEmpty());

        System.out.println("poped="+fixedCapacityStackOfStrings.pop());
        System.out.println("fixedCapacityStackOfStrings : size="+fixedCapacityStackOfStrings.size()+",isEmpty="+fixedCapacityStackOfStrings.isEmpty()); }}Copy the code
  • Test output
fixedCapacityStackOfStrings : size=0,isEmpty=true
fixedCapacityStackOfStrings : size=2,isEmpty=false
poped=Aaha
fixedCapacityStackOfStrings : size=1,isEmpty=false
Copy the code

FixedCapacityStack

FixedCapacityStackOfStrings disadvantage is that can handle only String object, then we are using generics, let our stack implementations can handle arbitrary objects.

Where Item is the type parameter of our generic.

For historical reasons, Java arrays generally do not support generics, so we use a strong cast to convert an array of type Object to a generic array type.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack; @param <Item> */ public class FixedCapacityStack<Item> implements Stack<Item> {private Item[] a; private int N; public FixedCapacityStack(intcap){
        a = (Item[]) new Object[cap];
    }

    @Override
    public void push(Item item) {
        a[N++] = item;
    }

    @Override
    public Item pop() {
        return a[--N];
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        returnN; }}Copy the code
  • test
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;

public class FixedCapacityStackTests {

    public  static void main(String[] args){
        FixedCapacityStack<Double> fixedCapacityStack=new FixedCapacityStack<>(10);
        System.out.println("fixedCapacityStack : size="+fixedCapacityStack.size()+",isEmpty="+fixedCapacityStack.isEmpty()); FixedCapacityStack. Push (new Double (10.01)); FixedCapacityStack. Push (new Double (202.22)); System.out.println("fixedCapacityStack : size="+fixedCapacityStack.size()+",isEmpty="+fixedCapacityStack.isEmpty());

        System.out.println("poped="+fixedCapacityStack.pop());
        System.out.println("fixedCapacityStack : size="+fixedCapacityStack.size()+",isEmpty="+fixedCapacityStack.isEmpty()); }}Copy the code
  • Test output
fixedCapacityStack : size=0,isEmpty=true
fixedCapacityStack : size=2,isEmpty=falsePoped = 202.22 fixedCapacityStack: size = 1, isEmpty =false
Copy the code

ResizingArrayStack

The biggest disadvantage of FixedCapacityStack is the fixed capacity, which requires us to estimate the maximum capacity of the stack before using it, which is very inconvenient.

Let’s implement a variable volume stack.

We expand the stack by replacing the old array with a new one. There are two points to note here:

  • If the stack is full, its capacity is doubled to ensure that it can be pushed multiple times. Because expanding capacity frequently is also very memory intensive.
  • If you find that only a quarter of the stack capacity is used when you unload the stack, reduce the stack capacity by half. Because arrays, if left empty, consume memory.

In addition, it is important to assign the element at the specified position to NULL after exiting the stack to prevent objects from drifting.

Java’s garbage collection strategy is to reclaim the memory of all objects that cannot be accessed. If the element at the specified location is not assigned to null after being removed from the stack, then saving a reference to such an unwanted object is called object dissociation.

By assigning null to the out-of-stack position, we overwrite the invalid references so that the GC can reclaim the memory.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack; ** @param <Item> */ public class ResizingArrayStack<Item> implements Stack<Item> {private Item[] a = (Item[]) new Object[1]; private int N = 0; ** @param Max */ private void resize(int Max) {// Move stack to a new array of size Max. Item[] temp = (Item[]) new Object[max];for(int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } @override public void push(Item Item) {// If the stack is full, double its capacityif (N == a.length) {
            resize(2 * a.length);
        }
        a[N++] = item;
    }

    @Override
    public Item pop() { Item item = a[--N]; // Prevent object (loitering) a[N] = null; // If only 1/4 of the stack is used, reduce the stack size by halfif (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        returnN; }}Copy the code
  • test
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;

import java.math.BigDecimal;

public class ResizingArrayStackTests {
    public  static void main(String[] args){

        ResizingArrayStack<BigDecimal> resizingArrayStack=new ResizingArrayStack<>();

        System.out.println("resizingArrayStack : size="+resizingArrayStack.size()+",isEmpty="+resizingArrayStack.isEmpty()); ResizingArrayStack. Push (new BigDecimal (100.001)); ResizingArrayStack. Push (new BigDecimal (202.022)); System.out.println("resizingArrayStack : size="+resizingArrayStack.size()+",isEmpty="+resizingArrayStack.isEmpty());

        System.out.println("poped="+resizingArrayStack.pop());
        System.out.println("resizingArrayStack : size="+resizingArrayStack.size()+",isEmpty="+resizingArrayStack.isEmpty()); }}Copy the code
  • Test output
resizingArrayStack : size=0,isEmpty=true
resizingArrayStack : size=2,isEmpty=falsePoped = 202.02199999999999135980033315718173980712890625 resizingArrayStack: size = 1, isEmpty =false
Copy the code

IterableResizingArrayStack

Next we will add the iterator feature to our stack implementation.

In fact, foreach is more than just a shorthand for for. Foreach and the while loop are equivalent:

for(String s:collection){
    s ...
}
Copy the code
while(collection.hasNext()){ collection.next(); . }Copy the code

As you can see from the above example, an iterator is an object that implements the hasNext() and next() methods.

If a class is Iterable, the first step is to declare that you implement the Iterable interface.

We then implement Iterator’s hasNext() and next() methods via an inner class to support iterative operations.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack; import java.util.Iterator; import java.util.NoSuchElementException; / * * * can be based on array of iteration variable storage Stack to realize * * @ param < Item > * / public class IterableResizingArrayStack < Item > implements Stack < Item >. Iterable<Item> { private Item[] a = (Item[]) new Object[1]; private int N = 0; ** @param Max */ private void resize(int Max) {// Move stack to a new array of size Max. Item[] temp = (Item[]) new Object[max];for(int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } @override public void push(Item Item) {// If the stack is full, double its capacityif (N == a.length) {
            resize(2 * a.length);
        }
        a[N++] = item;
    }

    @Override
    public Item pop() { Item item = a[--N]; // Prevent object (loitering) a[N] = null; // If only 1/4 of the stack is used, reduce the stack size by halfif (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        returnnew ReverseArrayIterator(); } // Support iterative methods, Private Class ReverseArrayIterator implements Iterator<Item> {// Support LIFO iteration. Private int I = N; @Override public booleanhasNext() {
            return i > 0;
        }

        @Override
        public Item next() {
            if(i<=0){
                throw new NoSuchElementException();
            }

            return a[--i];
        }

        @Override
        public void remove() { throw new UnsupportedOperationException(); }}}Copy the code
  • test
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;

import java.math.BigDecimal;

public class IterableResizingArrayStackTests {
    public static void main(String[] args) {

        IterableResizingArrayStack<Float> resizingArrayStack = new IterableResizingArrayStack<>();

        System.out.println("resizingArrayStack : size=" + resizingArrayStack.size() + ",isEmpty="+ resizingArrayStack.isEmpty()); ResizingArrayStack. Push (new Float (100.001)); ResizingArrayStack. Push (new Float (202.022)); System.out.println("resizingArrayStack : size=" + resizingArrayStack.size() + ",isEmpty=" + resizingArrayStack.isEmpty());

        System.out.println("resizingArrayStack all items:");
        for (Float f:resizingArrayStack) {
            System.out.println(f);
        }

        System.out.println("poped=" + resizingArrayStack.pop());
        System.out.println("resizingArrayStack : size=" + resizingArrayStack.size() + ",isEmpty="+ resizingArrayStack.isEmpty()); }}Copy the code
  • Test output
resizingArrayStack : size=0,isEmpty=true
resizingArrayStack : size=2,isEmpty=falseResizingArrayStack All items: 202.022 100.001 POPed =202.022 resizingArrayStack: size=1,isEmpty=false
Copy the code

The sample application

Determine if parentheses occur in pairs

It requires that in a string, all parentheses, if any, must come in pairs.

Write an inspector to check that the specified string conforms to the above rules.

According to TDD(test driven development) development method, first write unit tests:

package net.ijiangtao.tech.algorithms.algorithmall.algorithm.stack.evaluation; import net.ijiangtao.tech.algorithms.algorithmall.algorithm.stack.checker.LegalParenthesesChecker; import org.junit.Assert; import org.junit.Test; import org.junit.runner.RunWith; import org.springframework.boot.test.context.SpringBootTest; import org.springframework.test.context.junit4.SpringRunner; /** * brackets must appear in pairs, this program based on the stack structure, used to detect whether common brackets appear in pairs, and expression output is legitimate. */ @RunWith(SpringRunner.class) @SpringBootTest public class LegalParenthesesCheckerTests { @Test public voidtestChecker(){

        Assert.assertFalse(LegalParenthesesChecker.check("1}"));
        Assert.assertFalse(LegalParenthesesChecker.check("[1}"));
        Assert.assertFalse(LegalParenthesesChecker.check("[1]}"));
        Assert.assertFalse(LegalParenthesesChecker.check("(((1 + 1) + 2) + 3"));
        Assert.assertFalse(LegalParenthesesChecker.check("< ((1 + 1) + 2) + 3"));

        Assert.assertTrue(LegalParenthesesChecker.check(""));
        Assert.assertTrue(LegalParenthesesChecker.check(""));
        Assert.assertTrue(LegalParenthesesChecker.check("1"));
        Assert.assertTrue(LegalParenthesesChecker.check("[]"));
        Assert.assertTrue(LegalParenthesesChecker.check("[1]"));
        Assert.assertTrue(LegalParenthesesChecker.check("{(((<1+1>)+ [2])+ "3)}")); }}Copy the code

So let’s start writing the implementation.

package net.ijiangtao.tech.algorithms.algorithmall.algorithm.stack.checker; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack; import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl.IterableResizingArrayStack; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * brackets must appear in pairs, this program based on the stack structure, used to detect whether common brackets appear in pairs, and expression output is legitimate. */ public class LegalParenthesesChecker { private static final String BRACKET="< > () () < > ‹ holds the {}", "[] [] [] [] {}" "" "【 】 ︵ ︶ ︷ ︸ ︿ ﹀ ︹ ︺ "" ﹂ parting ﹃ ﹄ ︻ ︼"; Public static Boolean check(String expression) {// If the expression passed is empty, no parentheses are requiredif (null == expression || expression.length() < 1) {
            return true; Char [] expressionsChars = expression.tochararray (); Brackets = BRACKET. ToCharArray (); brackets = brackets (); brackets = brackets (); brackets = brackets (); // Before using binarySearch, you need to sort array. Sort (brackets); Map<Character, Stack> Map = new HashMap<>(); // Iterate over each character of the expressionforInt index = Array. binarySearch(brackets, C); // Negative numbers, not parentheses, need not be handledif (index < 0) {
                continue; } // The even number, which is the left parenthesis, is placed on the stackif(index % 2 == 0) {Stack<Character> Stack = map.get(c); // Create a stack container if the key corresponding to the open bracket is the first to be stored in the mapif (null == stack) {
                    stack = new IterableResizingArrayStack<>();
                }
                stack.push(c);
                map.put(c, stack);
            } else// Add extra brackets to the brackets. Add extra brackets to the brackets. Add extra brackets to the brackets. Stack<Character> Stack = map.get(left); // If the closing parenthesis does not match the corresponding opening parenthesis, the parentheses in the expression are not paired and invalidif (null == stack || stack.size() < 1) {
                    return false;
                } else {
                    stack.pop();
                    continue; }}} // If there are left parentheses in the map, indicating that there are more left parentheses than right parentheses, returnfalse
        for (char k : map.keySet()) {
            if(! map.get(k).isEmpty()){return false; }}return true; }}Copy the code

After unit test, the inspector meets the requirements.

Double stack arithmetic expression evaluation algorithm

Dijkstra’s two-stack Algorithm for Expression Evaluation is a very simple algorithm invented by E.W.Dijkstra in the 1960s. It uses two stacks: One holds operators and one holds operands to perform operations on an expression.

In fact, the whole algorithm idea is very simple:

  • Ignore the open bracket
  • Push operands onto the operand stack
  • Pushes the operator onto the operator stack
  • When a close parenthesis is encountered, an operator is popped from the operand stack, the desired operand is popped from the operand stack, and the result of the operation is pushed into the operand stack
package net.ijiangtao.tech.algorithms.algorithmall.algorithm.stack.evaluation;

import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack;
import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl.IterableResizingArrayStack;

public class DijkstrasTwoStackAlgorithmForExpressionEvaluation {

    public Double cal(String expression) {

        String[] expressionArr = expression.split("");

        Stack<String> ops = new IterableResizingArrayStack<String>();
        Stack<Double> vals = new IterableResizingArrayStack<Double>();

        for (String s : expressionArr) {
            // Read token, push if operator.
            if (s.equals("(")) {; }else if (s.equals("+")) {
                ops.push(s);
            } else if (s.equals("-")) {
                ops.push(s);
            } else if (s.equals("*")) {
                ops.push(s);
            } else if (s.equals("/")) {
                ops.push(s);
            } else if (s.equals("sqrt")) {
                ops.push(s);
            } else if (s.equals(")")) {
                // Pop, evaluate, and push result if token is ")"
                String op = ops.pop();
                double v = vals.pop();

                if (op.equals("+")) {
                    v = vals.pop() + v;
                } else if (op.equals("-")) {
                    v = vals.pop() - v;
                } else if (op.equals("*")) {
                    v = vals.pop() * v;
                } else if (op.equals("/")) {
                    v = vals.pop() / v;
                } else if (op.equals("sqrt")) {
                    v = Math.sqrt(v);
                }

                vals.push(v);
            }
            // Token not operator or paren: push double value.
            else{ vals.push(Double.parseDouble(s)); }}returnvals.pop(); }}Copy the code
  • test
package net.ijiangtao.tech.algorithms.algorithmall.algorithm.stack.evaluation;

public class DijkstrasTwoStackAlgorithmForExpressionEvaluationTests {

    public  static void main(String[] args){
        DijkstrasTwoStackAlgorithmForExpressionEvaluation expressionEvaluation=new DijkstrasTwoStackAlgorithmForExpressionEvaluation();
        System.out.println(expressionEvaluation.cal("(1 + (2 + 3) * (4 * 5))")); }}Copy the code
  • Test output:
101.0
Copy the code