Data structure: stack principle and Implementation

I. Introduction

Stack is a data structure of first-in-first-out, then-in-first-out.

If the figures 10, 15, 6, 9 are stored on the stack, the data from the stack will be 9, 6, 15, 10 in order. The stack structure is like the box in our life. The first item to be put in will be at the bottom of the box. The last data to be put in will be at the top. When we pick up the item, we also need to pick it up from the top.

2. Code Implementation

1. Create MyStack class as a custom stack

public class MyStack {

}

2. Attributes required for declaration

The underlying uses arrays to store data, or java generics to replace Object types.

private Object[] arr;//Store data
private int top;//Location of the top of the stack

The top of the stack: The top (last) element of the entire stack, which is the last element stored in the array.

The bottom of the stack: The element at the bottom of the entire stack (the first to be stacked), that is, the element stored first in the array.

3. The Construction Method of Stack

public MyStack(){
    arr = new Object[10];
    top = -1;
}

/**
 * The parameter is the initial length of the array
 * @param maxSize
 */
public MyStack(int maxSize){
    arr = new Object[maxSize];
    top = -1;
}

4. Pressing data into the stack

The underlying operation is to store data into the array. Since the top variable records the position of the top of the stack, the value of top increases by 1, which is the latest top of the stack.

 public void push(Object value) {
    arr[++top] = value;
}

5. Data on pop-up stack top

Get the data at the top of the stack and remove it from the stack. Pressing data into the stack requires adding a variable top to record the location of the top of the stack. Similarly, removing top data requires subtracting top by 1.

public Object pop(){
    return arr[top--];
}

6. View stack top data

public Object peek(){
    return arr[top];
}

7. Judging whether it is empty

public boolean isEmpty(){
    return top == -1;
}

8. Judging whether it is full or not

The value of top equals the position of the last element of the array, which is full.

public boolean isFull(){
    return top == arr.length-1;
}

9. Complete code

public class MyStack {
    private Object[] arr;//Store data
    private int top;//Location of the top of the stack

    public MyStack() {
        arr = new Object[10];
        top = -1;
    }

    /**
     * The parameter is the initial length of the array
     *
     * @param maxSize
     */
    public MyStack(int maxSize) {
        arr = new Object[maxSize];
        top = -1;
    }

    public void push(Object value) {
        arr[++top] = value;
    }

    /**
     * Pop-up stack top data
     * @return
     */
    public Object pop(){
        return arr[top--];
    }

    public Object peek(){
        return arr[top];
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public boolean isFull(){
        return top == arr.length-1;
    }
}

Three, validation

public static void main(String[] args) {
    MyStack stack = new MyStack(4);
    stack.push("a");
    stack.push("b");
    stack.push("c");
    stack.push("d");

    System.out.println("Is it empty?" + stack.isEmpty());
    System.out.println("Is it full?" + stack.isFull());

    System.out.println("Top of stack:"+stack.peek());
    System.out.println("Top of stack:"+stack.peek());

    //All data in the pop-up stack
    while (!stack.isEmpty()){
        System.out.println(stack.pop());
    }

    System.out.println("Is it empty?" + stack.isEmpty());
    System.out.println("Is it full?" + stack.isFull());
}

Tags: Programming Java

Posted on Sat, 05 Oct 2019 20:53:16 -0700 by snascendi