队列的两种实现方法

小雨的分享社区

发布于 2022-10-26 14:51:14

2230

发布于 2022-10-26 14:51:14

文章被收录于专栏：小雨的CSDN

概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

当head==tail时

情况1：队列为空

情况2：队列为满

用链表的方式形成队列

public class MyQueueByLinkedList {
    //Node 这个类叫做内部类
    static class Node{
        public int val;
        Node next = null;

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

    //创建一个链表就得有头节点  此处的head不是傀儡节点
    private Node head = null;
    private Node tail = null;

    //入队列
    //此处尾部入队列，头部出队列的方式实现
    public void offer(int val){
        Node newNode = new Node(val);
        if (head == null){
            head = newNode;
            tail = newNode;
            return;
        }
        //如果当前不是空链表
        tail.next = newNode;
        tail = tail.next;
    }

    //出队列
    public Integer poll(){
        if (head == null){
            return null;
        }
        int ret = head.val;
        head = head.next;
        if (head == null){
            tail = null;
        }
        return ret;
    }

    //取队首元素
    public Integer peek(){
        if (head == null){
            return null;
        }
        return head.val;
    }
}

用数组的方式形成队列

public class MyQueueByArray {
    private int[] array = new int[100];
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public void offer(int val){
        if (size == array.length){
            return;
        }
        array[tail] = val;
        tail++;
        //如果超出了有效范围，就从头开始
        if (tail > array.length){
            tail = 0;
        }
        size++;
    }

    public Integer poll(){
        if (size == 0){
            return null;
        }
        Integer ret = array[head];
        head++;
        if (head >= array.length){
            head = 0;
        }
        size--;
        return ret;
    }

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