栈和队列

栈：

栈是一个比较简单的数据结构，栈和普通数组和链表的区别就是，栈有特定的出入方式，普通数组和链表可以在任意位置进行增删改，而栈这个数据结构在增加元素的时候需要从栈顶进，也要从栈顶出，而且要符合先进后出（LIFO）的规则。假如我把A B C同时压入栈中，你只能拿出C才能拿出B最后才能拿出A，不可以一开始就把B和A出栈，所以栈就是在普通数组和链表的结构上对出入规则做出了一定的约束。一般我们用数组来实现栈，我们只需要对数组的最后一个元素进行操作，出栈的时候我们只需要进行逻辑删除，时间复杂度就是O(1)，入栈也是进行尾部插入，时间复杂度也是O(1)，比较高效。

public class MyStack {
    private T[] elem;
    private int top;//下标->栈顶指针

    public MyStack() {
        this.elem = (T[]) new Object[10];
    }

    //入栈操作
    public void push(T item) {
        if(isFull()){
            this.elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[top++]=item;
    }

    public boolean isFull() {
        return this.elem.length == this.top;
    }

    //出栈
    public T pop() {
        if(empty()){
            throw new UnsupportedOperationException();
        }
        T ret=this.elem[top-1];
        this.top--;
        return ret;
    }

    //得到栈顶元素不删除
    public T peek() {
        if(empty()){
            throw new UnsupportedOperationException();
        }
        T ret=this.elem[top-1];
        return ret;
    }
    //判断栈是否为空
    public boolean empty() {
       if(top==0){
           return true;
       }
        return false;
    }

队列：

队列和栈一样，只是在普通的数组和链表中做出了一定的约束，队列规定了先进先出（FIFO）的规则，这时候我们一般通过链表来实现一个队列，因为我们出队的时候只需要出第一个元素，让下一个节点为头节点，就完成了出队，它的时间复杂度就是O(1)，而如果使用数组来实现链表，我们出队需要让后面的所有数据往前移一个单位，时间复杂度就是O(n)，相比链表来说，就比较低效。

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 void offer(int val) {
        Node node=new Node(val);
        if(isEmpty()){
            this.first=node;
            this.last=node;
        }
        this.last.setNext(node);
        this.last=node;
    }

    public boolean isNull() {
        if (this.first == null) {
            return true;
        }
        return false;
    }

    //出队
    public int poll() {
        if(isEmpty()){
            throw  new UnsupportedOperationException();
        }
        int ret= this.first.getVal();
        this.first=this.first.getNext();
        return  ret;
    }

    //得到队头元素
    public int peek() {
        if(isEmpty()){
            throw  new UnsupportedOperationException();
        }
        int ret= this.first.getVal();
        return  ret;
    }

    public boolean isEmpty() {
        if (this.first == null) {
            return true;
        }
        return false;
    }