Java中常见队列举例详解(非线程安全)

目录

• 一.队列定义
•  二.常见接口
•  三.常见实现类
• 3.1 ArrayDeque
• 3.1.1 实现原理
• 3.1.2 方法图解 
• 3.1.3 demo代码
• 3.2 LinkedList
• 3.1.1 实现原理
• 3.1.2 demo代码
• 3.3 PriorityQueue
• 3.1.1 实现原理
• 3.1.2 demo代码
• 3.1.3 最小堆demo代码
• 3.4 优缺点
• 总结

一.队列定义

在 Java 中，队列（Queue） 是一种遵循 先进先出（FIFO） 原则的数据结构，可以通过 java.util.Queue 接口及其实现类来使用。

 二.常见接口

• 添加元素：

  • boolean add(E e): 添加元素，若队列满则抛出异常。

  • boolean offer(E e): 添加元素，队列满时返回 false。

• 移除元素：

  • E remove(): 移除并返回队首元素，队列空时抛出异常。

  • E poll(): 移除并返回队首元素，队列空时返回 null。

• 查看队首元素：

  • E element(): 返回队首元素但不移除，队列空时抛出异常。

  • E peek(): 返回队首元素但不移除，队列空时返回 null。

 三.常见实现类

3.1 ArrayDeque

3.1.1 实现原理

* 基于数组进行实现

* 不允许添加null元素

* 在两端插入和删除元素的性能较好，时间复杂度为O(1)

* 没有容量限制，会根据需要自动扩容。

3.1.2 方法图解 

3.1.3 demo代码

public class ArrayDequeDemo {
    public static void main(String[] args) throws Exception{
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for(int i = 7 ; i >=0 ; i--){
            deque.addFirst(i);
        }
        for (int i = 8 ; i < 15 ; i++){
            deque.addLast(i);
        }
        show(deque);
        deque.addLast(15);
        show(deque);
    }
    public static void show(ArrayDeque<Integer> deque) throws Exception{
        Field elements = ArrayDeque.class.getDeclaredField("elements");
        elements.setAccessible(true);
        System.out.println(jsONObject.toJSONString(elements.get(deque)));
        System.out.println(((Object[])( elements.get(deque))).length);
        Field head = ArrayDeque.class.getDeclaredField("head");
        head.setAccessible(true);
        System.out.println(JSONObject.toJSONString(head.get(deque)));
        Field tail = ArrayDeque.class.getDeclaredField("tail");
        tail.setAccessible(true);
        System.out.println(JSONObject.toJSONString(tail.get(deque)));
    }
}

3.2 LinkedList

3.1.1 实现原理

* 基于链表实现

* 允许添加null元素

* 在插入和删除元素时性能较好，时间复杂度为O(1)

3.1.2 demo代码

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0 ; i < 20 ; i++){
            queue.add((int)(Math.random()*1000));
            queue.addFirst(i);
            queue.addLast(i);编程客栈
        }
        while (!queue.isEmpty()){
            System.out.println(queue.poll());
        }
        System.out.println(queue.poll());
    }
}

3.3 PriorityQueue

3.1.1 实现原理

* 基于二叉堆（通常是最小编程客栈堆）实现

3.1.2 demo代码

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Integer::compareTo);
        for(int i = 0 ; i < 20 ; i++){
            queue.add((int)(Math.rand编程客栈om()*1000));
        }
        while (!queue.isEmpty()){
            System.out.println(queue.poll());
        }
        System.out.println(queue.poll());
    }

}

3.1.3 最小堆demo代码

class MinHeap{
    private final List<Integer> heap;
    public MinHeap(){
        heap = new ArrayList<>();
    }
    //左子节点
    private int leftChild(int i){
        return 2*i+1;
    }
    //右子节点
    private int rightchild(int i){
        return 2*i+2;
    }
    //父节点
    private int parent(int i){
        return (i-1)/2;
    }
    //插入节点
    public void insert(int x){
        heap.add(x);
        int index = heap.size()-1;
        //上浮节点
        while(index > 0 && heap.get(index) < heap.get(parent(index))){
            swap(index, parent(index));
            index = parent(index);
        }
    }
    //交换节点
    private void swap(int i, int j) {
        int temp python= heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
    //删除最小节点
    public int deleteMin(){
        if(heap.isEmpty()){
            throw new RuntimeException("堆为空");
        }
        if (heap.size() == 1){
            return heap.remove(0);
        }
        int min = heap.get(0);
        heap.set(0,heap.remove(heap.size()-1));
        minHeapify(0);
        return min;
    }
    //更新指定节点的最小树
    public void minHeapify(int i){
        //左子节点
        int left = leftChild(i);
        //右子节点
        int right = rightChild(i);
        //最小节点
        int smallest = i;
        //计算左节点
        if(left < heap.size() && heap.get(left) < heap.get(smallest)){
            smallest = left;
        }
        //计算右节点
        if(right < heap.size() && heap.get(right) < heap.get(smallest)){
            smallest = right;
        }
        if (smallest != i){
            swapjs(i, smallest);
            minHeapify(smallest);
        }
    }
}

3.4 优缺点

总结

到此这篇关于Java中常见队列的文章就介绍到这了,更多相关JAVA常见队列内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！