java数据结构之栈和队列

java数据结构之栈和队列一、栈二、队列三、标准库中的栈和队列

核心思想：后进先出

顺序表实现：

public class MyStack1 {
    private int[] data = new int[100];
    private int size = 0;

入栈：尾插

    public void  push(int val){
        if (size >= data.length){
            return;
        }
        data[size] = val;
        size++;
    }

出栈：尾删（返回值就是被出栈删除的元素）

    public Integer pop(){
        if (size == 0){
            return null;
        }
        //删除栈顶元素
        int ret = data[size-1];
        size--;
        return ret;
    }

取栈顶元素：根据下标获取元素

    public Integer peek(){
        if (size == 0){
            return null;
        }
        return data[size-1];
    }

链表实现

class Node{
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}
public class MyStack2 {
    //此处以不带傀儡节点的链表为例
    private Node head = null;
}

入栈：头插

    public void push(int val){
        //step1：创建新节点
        Node newNode = new Node(val);
        //2、把新节点进行头插，由于当前链表是不带傀儡的，
        // 所以需要判断当前链表是非空还是空
        if (head == null){
            head = newNode;
            return;
        }
        newNode.next = head; //让 newNode 指向原头结点
        head = newNode; //更新 head
    }

出栈：头删

    public Integer pop(){
        //进行头删，若是空链表
        if (head == null){
            return null;
        }
        //只有一个节点的链表
        if (head.next == null){
            int ret = head.val;
            head = null;
            return ret;
        }
        // 其他一般情况
        // java中节点的删除主要看该对象是否有引用指向他，
        // 若是无引用指向该对象，则表示该对象被删除(GC垃圾回收)
        int ret = head.val;
        head = head.next;
        return ret;
    }

取栈顶元素：取头结点

    public Integer pip(){
        if (head == null){
            return null;
        }
        return head.val;
    }

核心思想：先进先出

顺序表（数组）实现：

入队列：尾插

    public boolean offer(int val){
        //队列满了,也可以实现扩容逻辑
        if (size == data.length){
            return false;
        }
        //队列没满的情况下可以把新元素放到tail对应的下标上
        data[tail] = val;
        tail++;
        //一旦tail到达队列的末尾就要让其从头开始
        //方法1：
        if (tail == data.length){
            tail = 0;
        }
        //方法2：
        tail = tail % data.length;
        size++; //更新 size 的值
        return true;
    }

出队列：尾删

    public Integer poll(){
        if (size == 0){
            return null;
        }
        int ret = data[head];
        head++; //更新 head 的位置
        if (head == data.length){
            head = 0;
        }
        size--;
        return ret;
    }

取队顶元素：根据下标获取元素

    public Integer peek(){
        if (size == 0){
            return null;
        }
        return data[head];
    }

链表实现

//链表实现队列
public class MyQueue {

    //创建链表
    static class  Node{
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    //创建一个链表并记录其头结点和尾结点
    private Node head = null;
    private Node tail = null;
}

入队：尾插

返回值表示是否插入成功

    public boolean offer(int val){
        //创建新节点
        Node newNode = new Node(val);
        //若是空链表,直接让 head 和 tail 指向新节点即可
        if (head == null){
            head = newNode;
            tail = newNode;
            return true;
        }
        //一般情况的尾插
        tail.next = newNode;
        tail = tail.next;
        return true;
    }

出队：头删

    public Integer poll(){
        if (head == null){
            return null;
        }
        int ret = head.val;
        if (head.next == null){
            return ret;
        }
        head = head.next; //删除头结点
        return ret;
    }

取队首元素：获取头结点

    public Integer peek(){
        if (head == null){
            return null;
        }
        return head.val;
    }

标准库中，栈（Stack）是一个类，可以直接使用；队列（Queue）是一个接口，不能直接实例化，需要创建对应的子类。Stack 继承自 Vector。