首页 > 其他分享 >数据结构——队列

数据结构——队列

时间：2023-02-01 18:04:40浏览次数：68  
标签：return 队列 tail 数据结构 data public size

简介

队列是是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

 

队列是一种先进先出的线性表，简称FIFO允许插入的以端称为队尾，允许删除的一端被称为队头。

入队

队列入队

出队

队列出队

队列的两种存储表示：

  • 顺序表示：与顺序栈相似，队列的顺序存储结构会用一组地址连续的存储单元依次存储对猎头到队列尾的元素，还分别有头指针和尾指针指向队列头和队列尾。

    • 顺序结构队列的初始化：①设置队列最大长度；②头尾指针为0；③插入新队尾元素，尾指针加一；④删除头元素时，头指针加一。
    • 队列假溢出：当队列的最大空间为6，而头指针为5，尾指针为6时，将不可再继续插入新的队尾元素，实际上队列的实际可用空间并未沾满，此为“假溢出”现象。
    • 假溢出的解决方案：循环队列，队空条件：头指针=尾指针；队满条件：（尾指针+1）%MAXQSIZE == 头指针。　

  • 链式表示：用链表标识的队列简称为链队。

    • 链队的初始化：①构造一个只有头结点的控队，头尾指针相等，头结点的指针域为null。
    • 入队：为新队尾元素分配结点，将新结点插入队尾，修改队尾指针的值。
    • 出队：判断对是否为空，空则出错，否则取出队列的队头元素，修改头指针。　　

队列的应用

  • 用于管理多线程中的线程。
  • 用于实施排队系统。

队列的抽象接口

public interface Queue<E> {

    /**
     * 队列的容量
     * @return
     */
    int getSize();

    /**
     * 队列是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 向队列中添加元素
     * @param e
     */
    void enqueue(E e);

    /**
     * 向队列取出元素
     * @return
     */
    E dequeue();

    /**
     * 查看队列第一个元素
     * @return
     */
    E getFront();
}

数组实现队列

public class ArrayQueue<E> implements Queue<E> {

    private E[] data;

    private int size;

    public ArrayQueue(){
        this(10);
    }

    public ArrayQueue(int capacity){
        this.data = (E[]) new Object[capacity];
        this.size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取队列的容量
     * @return
     */
    public int getCapacity(){
        return data.length;
    }

    @Override
    public void enqueue(E e) {
        addLast(e);
    }

    @Override
    public E dequeue() {
        return removeFirst();
    }

    @Override
    public E getFront() {
        return get(0);
    }

    /**
     * 获取指定索引位置的值
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. index is illegal.");
        }
        return data[index];
    }

    /**
     * 数组尾部新增元素
     * @param e
     */
    private void addLast(E e){
        add(size, e);
    }

    /**
     * 在指定位置插入元素
     * @param index
     * @param e
     */
    private void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size");
        }
        if(size == data.length){
            //扩容
            resize(2 * data.length);
        }

        for(int i = size - 1; i >= index; i --){
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }

    /**
     * 数组扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 删除数组中第一个元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除栈数组中index位置的元素, 并返回删除的元素
     * @param index
     * @return
     */
    private E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. index is illegal.");
        }
        E ret = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size --;
        data[size] = null;
        if(size == data.length / 4 && data.length / 2 != 0){
            //当数组长度缩小为原数组的4分之一的时候才进行数组的缩容，
            //缩小为原数组的2分之一，预留空间，防止有数据添加导致扩容浪费性能
            resize(data.length / 2);
        }
        return ret;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: ");
        sb.append("front [");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i != size - 1){
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

循环队列

队列首位相接的顺序存储结构。 循环队列

通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？ 队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。

tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。当队满时，(tail+1)%n=head，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会 浪费一个数组的存储空间。

基于数组实现

public class LoopQueue<E> implements Queue<E> {

    private E[] data;

    //队首
    private int front;

    //队尾
    private int tail;

    private int size;

    public LoopQueue(){
        this(10);
    }

    public LoopQueue(int capacity){
        //在该实现中front==tail表示队列为空，所以存储容量的时候要空一格
        this.data = (E[]) new Object[capacity + 1];
        this.front = 0;
        this.tail = 0;
        this.size = 0;
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0){
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("Queue is Empty.");
        }
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Queue：size=%d, capacity=%d\n",size,getCapacity()));
        sb.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if((i + 1) % data.length != tail){
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

链表队列

public class LinkedListQueue<E> implements Queue<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node(E e){
            this.e = e;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node<E> head, tail;

    private Integer size;

    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        if(tail == null){
            head = tail = new Node<>(e);
        }else {
            tail = tail.next = new Node<>(e);
        }
        size ++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        Node<E> retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null){
            tail = null;
        }
        size --;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: front ");
        Node<E> cur = head;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

对比测试

public class Test {

    //测试使用queue运行opCount个enQueue和deQueue操作所需的时间，单位：秒
    private static double testQueue(Queue<Integer> queue,int opCount){
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            queue.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            queue.dequeue();
        }
        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
        double time1 = testQueue(arrayQueue,opCount);
        System.out.println("ArrayQueue, time: "+time1+" s");

        LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue, time: "+time2+" s");

        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<Integer>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("LinkedListQueue, time: "+time3+" s");
    }
}

可见链表队列和循环队列相差不大，而数组队列时间差距是将近200多倍。

应用

阻塞队列

阻塞队列在队列基础上增加了阻塞操作。在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生 产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

 

而且不仅如此，基于阻塞队列，我可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。

并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法 上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用 更加广泛的原因。

 

参考： https://blog.csdn.net/weixin_39084521/article/details/89820114

https://www.cnblogs.com/smallzhen/p/14165352.html

标签：return,队列,tail,数据结构,data,public,size
From： https://blog.51cto.com/u_14014612/6031724

相关文章

  • 数据结构——栈
    简介限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端成为栈顶，另一端成为栈低，不含任何元素的栈成为空栈，栈又称为先进先出的线性表，简称LIFO结构。 栈的插......
  • 数据结构——链表
    链表数组要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，......
  • LeetCode.225 用队列实现栈
    1题目请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。实现MyStack类：voidpush(intx)将元素x压入栈顶。intpop()......
  • LeetCode.232 用栈实现队列
    1.题目请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现MyQueue类：voidpush(intx)将元素x推到队列的末尾intpop()......
  • 【算法训练营day35】LeetCode860. 柠檬水找零 LeetCode406. 根据身高重建队列 LeetCod
    LeetCode860.柠檬水找零题目链接：860.柠檬水找零独上高楼，望尽天涯路本来以为只想到了最笨的方法，即讨论所有情况。classSolution{public:boollemonadeChange......
  • 异步任务队列
    异步任务队列Task.WhenAll(List<Task>)等List中所有的异步任务完成后才算完成Task.WhenAny(List<Task>)List中某个完成就完成较常用的是Task.WhenAll(List<Task>)不aw......
  • [数据结构] 根据前中后序遍历中的两种构造二叉树
    前中后序遍历前中后序遍历的特点前序遍历前序遍历顺序：根节点->左子树->右子树前序遍历结果：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]假如把前序遍历结果......
  • 使用消息队列必须考虑的问题
    总结：为什么使用消息队列？异步、解耦、削峰。消息队列有什么缺点？可用性降低、系统复杂度提高、一致性问题。如何保证消息队列的可用性？镜像集群模式（RabbitMQ），主从......
  • Python-数据结构
    数据结构：数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如int/float/char等。数据元素之间不是独立的，存在特点的关系，这些关系便是结构。数据结构指数......
  • rabbitmq 延时消息队列
    //rabbitmq延时消息队列生产端demo//1.将消息发送到延时交换机对应的队列上delay-queue，指定过期时间；过期后转发的交换机和绑定的key//2.过期时间过期......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99