Java implementation stack (linked list and linear list)

1, Introduction to stack
Any data structure is a rule

Stack is formed by defining rules on the most basic structure linear structure and chain structure

If you have any questions about the basic data structure (linear list and linked list), please refer to my previous blog: https://www.cnblogs.com/yxm2020/p/12762888.html

The rules are as follows:

To restrict the insertion and extraction of linked list or linear table elements, you can only operate at the same end. The section running the insertion is called the top of the stack, and the other end is the fixed end, which becomes the bottom of the stack.

Illustration: (in stack and out stack)

characteristic:

First in last out (Filo), the data put in the stack first, can only come out last, which is the opposite of the queue

Application scenario of stack:

Save the code or value in the running program, such as:

Subroutine call
Handle recursive calls
Conversion of expression (infix to suffix)
Traversal of binary tree
Depth first traversal of graph
2, The realization of code
1. Thinking

Determine a structure to store data, linear list or linked list
Since you can only operate at the top of the stack, define a top flag
The two most basic methods, in stack and out stack
After entering the stack, add an element at the top of the stack, and move a unit up the top
After leaving the stack, delete an element at the top of the stack, and move a unit down at the top
2. Java implementation

Simulating stack with Java array
java linked list implementation stack
3, Java array simulation stack
public class ArrayStack {

//Stack top flag
private int top;
//java array
private T[] stack;
//Maximum length
private int maxsize;
public ArrayStack(int maxsize,Class<T> type){
    this.maxsize = maxsize;
    this.top = -1;
    stack = (T[]) Array.newInstance(type,maxsize);
}
//length
public int size(){
    return top+1;
}
//Stack full
public boolean isFull(){
    return top == maxsize-1;
}
//Stack space
public boolean isEnpty(){
    return top == -1;
}
//Push
public void push(T t){
    if(isFull()){
        throw new RuntimeException("Stack full");
    }
    top++;
    stack[top] = t;
}
//Stack out
public T pop(){
    if(isEnpty()){
        throw new RuntimeException("Stack space");
    }
    T value = stack[top];
    top--;
    return value;
}
//ergodic
public void show(){
    if(isEnpty()){
        System.out.println("Stack space");
    }
    int temp = top;
    while (temp != -1){
        System.out.println(stack[temp]);
        temp--;
    }
}

}
4, Java linked list implementation stack
public class LinkedStack {

//Define a stack top flag with
private Node top;
private class Node{
    private Node next;
    private T t;
    public Node(T t){
        this.t = t;
    }
}
//Establish
public LinkedStack(){
    top = new Node(null);
}
//Stack space
public boolean isEnpty(){
    if(top.next == null){
        return true;
    }
    return false;
}
//Push
public void push(T t){
    Node newNode = new Node(t);
    //From the top of the stack
    newNode.next = top.next;
    top.next = newNode;
}
//Stack out
public T pop(){
    if(isEnpty()){
        System.out.println("Stack space");
        return null;
    }
    T value = top.next.t;
    top.next = top.next.next;
    return value;
}
//show
public void show(){
    Node temp = top;
    if(temp.next == null){
        System.out.println("Stack space");
    }
    while (temp.next!=null){
        temp = temp.next;
        System.out.println(temp.t);
    }
}

}

Original address https://www.cnblogs.com/yxm2020/p/12859000.html