【数据结构】Java实现栈

1. 概念

2. 栈的使用

3. 自己动手实现栈（使用动态数组实现栈）

1. 创建一个MyStack类

2. push入栈

3. pop出栈

4. 查看栈顶元素

5. 判断栈是否为空与获取栈长

6. toString方法

4. 整体实现

4.1 MyStack类

4.2 Test类

4.3 测试结果

1. 概念

栈：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

2. 栈的使用

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
//        将e入栈，并返回e
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
//        将栈顶元素出栈并返回
        System.out.println(stack.pop());
//        获取栈顶元素
        System.out.println(stack.peek());
//        检测栈是否为空
        System.out.println(stack.empty());
//        获取栈中有效元素个数
        System.out.println(stack.size());
        System.out.println(stack);
    }

3. 自己动手实现栈（使用动态数组实现栈）

1. 创建一个MyStack类

思路图：

import java.util.Arrays;
import java.util.NoSuchElementException;
//使用泛型
public class MyStack<E> {
    private Object[] data;
    private int size;

    public MyStack(int capacity){
        this.data = new Object[capacity];
    }
    public MyStack(){
        this.data = new Object[10];
    }
    
}

2. push入栈

public E push(E val){
        data[size ++] = val;
        if(size == data.length){
            data = Arrays.copyOf(data,data.length<<1);
        }
        return val;
    }

3. pop出栈

public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot pop!");
        }
        E oldVal = (E)data[size - 1];
        size --;
        return oldVal;
    }

4. 查看栈顶元素

public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot peek!");
        }
        return (E)data[size - 1];
    }

5. 判断栈是否为空与获取栈长

public boolean isEmpty() {
        return size == 0;
    }
    public int size(){
        return size;
    }

6. toString方法

public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("bottom [");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i < size - 1){
                sb.append(",");
            }
        }
        sb.append("] top");
        return sb.toString();
    }

4. 整体实现

4.1 MyStack类

package seqlist.stack_queue;

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MyStack<E> {
    private Object[] data;
    private int size;

    public MyStack(int capacity){
        this.data = new Object[capacity];
    }
    public MyStack(){
        this.data = new Object[10];
    }
    public E push(E val){
        data[size ++] = val;
        if(size == data.length){
            data = Arrays.copyOf(data,data.length<<1);
        }

        return val;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    public int size(){
        return size;
    }
    public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot pop!");
        }
        E oldVal = (E)data[size - 1];
        size --;
        return oldVal;
    }
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empy,cannot peek!");
        }
        return (E)data[size - 1];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("bottom [");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i < size - 1){
                sb.append(",");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}

4.2 Test类

public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
//        将e入栈，并返回e
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println("将栈顶元素出栈并返回");
        System.out.println(stack.pop());
        System.out.println("获取栈顶元素");
        System.out.println(stack.peek());
        System.out.println("检测栈是否为空");
        System.out.println(stack.isEmpty());
        System.out.println("获取栈中有效元素个数");
        System.out.println(stack.size());
        System.out.println(stack);
    }