Stack is a common data structure and a linear table with limited operation. Limit linear tables to insert and delete only 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. Inserting a new element into a stack is also called stack entry, stack entry or stack pressing. It puts the new element above the top element of the stack to make it a new top element; Deleting an element from a stack is also called out of stack or out of stack. It deletes the top element of the stack and makes its adjacent elements become new top elements.

  As the name suggests, a stack is a linear table (LIFO structure for short, Last in, First out) that can only be entered and output from one end.

According to the storage structure, it can be divided into sequential stack and chain stack:

Sequential stack uses a group of continuous storage space to store stack elements in turn. When creating sequential stack, it is necessary to specify the length of storage space. Elements are placed in turn from the bottom of the stack to the top of the stack, that is, each entry and exit are completed at the top of the stack. Insert a new element at the end of the sequence table when entering the stack, and take out the end of the table element when outbound.

The chain stack is a chain storage structure. If you select the end of the chain as the top of the stack, that is, add a node element to the end of the chain list every time you enter the stack, and take out the end of the chain element every time you exit. Because the linked list query needs to start from the header, each time the stack and the stack must traverse the whole linked list before finding the top element of the stack, which will lead to low efficiency of the chain stack. Therefore, select the first element of the linked list as the top of the stack. Only the first element needs to be found when entering and leaving the stack. When entering the stack, disconnect the pointer between the header and the first element of the linked list, point the header pointer to the new node element, and then point the pointer of the new node element to the original first element node. When leaving the stack, the out of stack element can be found directly through the header pointer, Delete the first node after exiting the stack.

  How to select sequence stack and chain stack:

When a stack needs to be frequently out of the stack and modified, the sequential stack is selected. The sequential storage structure of the sequential stack has a high time efficiency in searching and modifying;

When a stack needs to be loaded and deleted frequently, select the chain stack, and the chain storage structure has high timeliness in insertion and deletion.

  java implementation sequence stack

/**
 * Stack
 * @author Huzz
 * @created 2021-10-09 16:12
 * @param <T>
 */
public class ArrayStack<T> {

    private static final int DEFAULT_SIZE = 10;

    /**
     * length
     */
    private int count;

    /**
     * An array of stack elements
     */
    private T[] array;

    public ArrayStack(Class<T> type) {
        this(type, DEFAULT_SIZE);
    }

    public ArrayStack(Class<T> type, int size) {
        this.count = 0;
        this.array = (T[]) Array.newInstance(type, size);
    }

    /**Push 
     *
     * @param val
     */
    public void push(T val){
        this.array[count++] = val;
    }

    /**
     * Find stack top element
     * @return
     */
    public T peek(){
        return this.array[count - 1];
    }

    /**
     * Out of stack
     * @return
     */
    public T pop(){
        return this.array[--count];
    }

    /**
     * Stack length
     * @return
     */
    public int size(){
        return this.count;
    }

    /**
     * Is it empty
     * @return
     */
    public boolean isEmpty(){
        return this.count == 0;
    }

    /**
     * Print stack
     */
    public void printArrayStack(){
        if (this.count == 0) {
            System.out.println("The Stack is Empty.");
            return;
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        for (int i = 0; i < count; i++) {
            stringBuilder.append(this.array[i] + ", ");
        }
        stringBuilder.replace(stringBuilder.lastIndexOf(", "), stringBuilder.length(), "]");
        System.out.println(stringBuilder);
    }
}

  java implementation chain stack

/**
 * Chain stack
 * @author Huzz
 * @created 2021-10-15 11:38
 * @param <T> 
 */
public class LinkedStack<T> {

    private int count;

    private LinkedList<T> link;

    public LinkedStack() {
        link  = new SingleLinkedList<T>();
    }



    /**Push 
     *
     * @param val
     */
    public void push(T val){
        link.insertFirst(val);
        count++;
    }

    /**
     * Find stack top element
     * @return
     */
    public T peek(){
        return link.getFirst();
    }

    /**
     * Out of stack
     * @return
     */
    public T pop(){
        T result = link.getFirst();
        link.deleteFirst();
        return result;
    }

    /**
     * Stack length
     * @return
     */
    public int size(){
        return count;
    }

    /**
     * Is it empty
     * @return
     */
    public boolean isEmpty(){
        return count == 0;
    }

    /**
     * Print stack
     */
    public void printArrayStack(){
        if (count == 0) {
            System.out.println("The Stack is Empty.");
            return;
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        for (int i = 0; i < count; i++) {
            stringBuilder.append(link.get(i) + ", ");
        }
        stringBuilder.replace(stringBuilder.lastIndexOf(", "), stringBuilder.length(), "]");
        System.out.println(stringBuilder);
    }
}