手动实现栈和队列

1. 手动实现栈

import java.util.Arrays;

public class MyStack<T> {
    private T[]stack;//数组
    private int top;//当前可以存放数据元素的下标——>栈顶指针

    //用构造函数给定一个初始容量10的数组
    public MyStack( ){
        this.stack = (T[])new Object[10];//泛型不能实例化对象，但是可以类型转换
    }

    //判断栈是否满了
    public boolean isFull(){
        return (stack.length == this.top);
    }

    //判断栈是否为空
    public boolean empty(){
        return this.top == 0;
    }

    //入栈操作
    public void push(T value) {
        //判断栈是否已经满了
        if (isFull()){
            this.stack = Arrays.copyOf(stack,2*stack.length);//满了就扩容成原来容量的两倍
        }

        this.stack[this.top] = value;//给top位置添加元素
        this.top++;//top指针指向下一可用空间
    }

    //出栈操作，并返回弹出（删除）栈顶元素
    public T pop() {
        //先判断栈是否为空
        if (empty()) {
            throw new IllegalStateException("栈为空！");
        }

        //弹出元素
        T ret = this.stack[this.top-1];
        this.top--;
        return ret;//返回删除的元素
    }

    //得到栈顶元素，但是不删除
    public T peek() {

        //判断是否为空
        if (empty()){
            throw new IllegalStateException("栈为空！");
        }
        //返回栈顶元素，不删除
        return this.stack[top-1];
    }

    //展示栈元素
    public void show() {
        for (int i = top-1; i>=0 ; i--){
            System.out.print(stack[i]+" ");
        }
        System.out.println();
    }
}

2.手动实现队列

public class Node {
    private int val;
    private Node next;

    public Node(int val){
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getNext() {
        return next;
    }
    
    public void setNext(Node next) {
        this.next = next;
    }
}

public class MyQueue {
    private Node first;
    private Node last;
    //队列是否为空
    public boolean isEmpty() {
        return this.first == null;
    }
    //入队
    public void offer(int value){
        Node node = new Node(value);
        //尾插法，要判断是否第一次插入
        if (this.first == null){
            this.first = node;
            this.last = node;
        }else{
            this.last.setNext(node);
            this.last = node;
        }
    }
    //出队
    public int poll(){
        //判断是否为空
        if (isEmpty()){
            throw new IllegalStateException("队列为空");
        }
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;//返回出队元素
    }
    //得到队头元素但是不删除
    public int peek() {
        //不要移动first
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        return this.first.getVal();
    }
    //展示队列
    public void show() {
        Node cur = this.first;
        while(cur != null) {
            System.out.print(cur.getVal()+" ");
            cur = cur.getNext();
        }
        System.out.println();
    }
}