【数据结构】队列详解和模拟实现

标签：Head null ListNode val 队列 Tail 详解数据结构

大家好，今天我们学习队列，本篇博客主要涉及一般队列，环形队列和双端队列，每个队列应用场景均有所差异，下面我们一起来看看吧。

队列(Queue)

一，概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性
入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）

队列的概念其实很好理解，想象成排队即可，先来的元素可以先出队列

二，队列的使用

1.队列实质

在Java中，Queue是个接口，底层是通过链表实现的。

2.常用方法：

boolean offer(E e) ：                                 入队列
E poll() ：                                                   出队列
peek() ：                                                     获取队头元素
int size()：                                                  获取队列中有效元素个数
boolean isEmpty() ：                                检测队列是否为空

需要注意的是， Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

3.应用：

import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);// 从队尾入队
        System.out.println(q.size());
        System.out.println(q.peek()); // 获取队头元素
        q.poll();
        System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
        if (q.isEmpty()) {
            System.out.println("队列空");
        } else {
            System.out.println(q.size());
        }
    }
}

三：队列的模拟实现

1.事前准备

已经说过Java原生队列底层是双向链表，因此我们采用双向链表实现队列，当然，使用单链表也能达成目的，但是并没有双链表方便

首先我们创建一个自己的队列并定义好节点和头尾节点

public class MyQueue {
    class ListNode{
        int val;
        ListNode next;
        ListNode prev;
        ListNode(int val){
            this.val=val;
        }
    }
    ListNode Head= null;
    ListNode Tail= null;
    int size=0;
}

2.成员方法

a.入队

我们选择在双链表尾部进行插入即可，和我们在双链表写过的尾插方法一样

public void offer(int val){
        ListNode node=new ListNode(val);
        if(Head==null&&Tail==null){
            Head=Tail=node;
        }else {
            Tail.next=node;
            node.prev=Tail;
            Tail=node;
        }
        size++;
    }

b，出队

出队列与双向链表头删方法一致，分三种情况

1. 队列为空
2. 队列中只有一个元素----链表中只有一个节点---直接删除
3. 队列中有多个元素---链表中有多个节点----将第一个节点删除

public int poll() {
        int val = -1;
        if (Head == null) {
            return -1;
        } else if (Head == Tail) {
            val=Head.val;
            Head = null;
            Tail = null;
        } else {
            val=Head.val;
            ListNode tmp=Head.next;
            Head.next.prev = null;
            Head.next = null;
            Head=tmp;
        }
        size--;
        return val;
    }

c，获取头部元素

和删除非常像，但是不执行删除操作，返回头部val值

public int peek() {
        if (Head == null) {
            return -1;
        }
        return Head.val;
    }

d，判空

主要与size有关，或者判断头节点是否为空

public boolean isEmpty(){
return Head == null;
//return size==0；
}

我们可以测试一下我们自己的队列，是完全没问题的

public class MyQueue {
    class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        ListNode(int val) {
            this.val = val;
        }
    }
    private  ListNode Head = null;
    private ListNode Tail = null;
    private int size = 0;

    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (Head == null && Tail == null) {
            Head = Tail = node;
        } else {
            Tail.next = node;
            node.prev = Tail;
            Tail = node;
        }
        size++;
    }
    public int poll() {
        int val = -1;
        if (Head == null) {
            return -1;
        } else if (Head == Tail) {
            Head = null;
            Tail = null;
        } else {
            val = Head.val;
            ListNode tmp = Head.next;
            Head.next.prev = null;
            Head.next = null;
            Head = tmp;
        }
        size--;
        return val;
    }

    public int peek() {
        if (Head == null) {
            return -1;
        }
        return Head.val;
    }

    public boolean isEmpty() {
        return Head == null;
        //return size==0；
    }
}