文档章节

Java实现队列 && 数组存储结构

秋风醉了
 秋风醉了
发布于 2014/09/17 11:58
字数 1134
阅读 3546
收藏 49

Java实现队列 && 数组存储结构

C语言版队列的实现:http://my.oschina.net/xinxingegeya/blog/267845

队列(Queue)两端允许操作的类型不一样:

  • 可以进行删除的一端称为队头,这种操作也叫出队dequeue

  • 可以进行插入的一端称为队尾,这种操作也叫入队enqueue

总的来说,队头(front)只能出队,队尾(rear)只能入队。

队列出队和入队的示意图

 

实现队列时,要注意的是假溢出现象,如上图的最后一幅图。

如上图所示的假溢出。

解决办法在顺序存储时,我们常见的解决办法是把它首尾相接,构成循环队列 ,这可以充分利用队列的存储空间。循环队列示意图:

在上图中,front指向队列中第一个元素,rear指向队列队尾的下一个位置。

但依然存在一个问题:当front和rear指向同一个位置时,这代表的是队空还是队满呢?大家可以想象下这种情景。解决这种问题的常见做法是有以下两种:

  1. 使用一标记,用以区分这种易混淆的情形。

  2. 牺牲一个元素空间。当front和rear相等时,为空;当rear的下一个位置是front时,为满。

如下图:

 

下面我们给出循环队列,并采用第二种方式,即牺牲一个元素空间来区分队空和队满的代码。几个重点:

  1. front指向队头,rear指向队尾的下一个位置。

  2. 出队时,front=(front+1)%MAXSIZE;入队时,rear=(rear+1)%MAXSIZE。

  3. 队为空的判断:front==rear;队为满的判断:(rear+1)%MAXSIZE==front。

具体请参考Java类库中实现的双端队列ArrayDeque,在这里参考了其中的代码,比如队列内部数组大小的确定,队列扩容的算法。

package hash;

/**
 * 队列(queue),是先进先出(FIFO, First-In-First-Out)的线性表。
 * 在具体应用中通常用链表或者数组来实现。
 * 队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
 */
public class CustomArrayQueue<T> {
    private T[] elements;
    private int front;//队头
    private int rear;//队尾

    /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

    /**
     * 队列扩容的算法
     * 队列的容量扩大为原来的两倍
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    private void doubleCapacity() {
        int p = front;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new IllegalStateException("Sorry, deque too big");
        }
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (T[]) a;
        front = 0;
        rear = n;
    }


    /**
     * 默认存储空间大小为16
     */
    public CustomArrayQueue() {
        elements = (T[]) new Object[16];
    }

    /**
     * 确定队列内部数组实际的大小
     * 对于一个给定长度,先判断是否小于定义的最小长度,
     * 如果小于,则使用定义的最小长度作为数组的长度。
     * 否则,找到比给定长度大的最小的2的幂数
     *
     * @param numElements
     */
    public CustomArrayQueue(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>> 1);
            initialCapacity |= (initialCapacity >>> 2);
            initialCapacity |= (initialCapacity >>> 4);
            initialCapacity |= (initialCapacity >>> 8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (T[]) new Object[initialCapacity];
    }


    /**
     * 入队
     * 入队要求队列不能满
     *
     * @param item
     */
    public void enqueue(T item) {

        if (item == null) {
            throw new NullPointerException();
        }
        elements[rear] = item; //入队
        rear = (rear + 1) % elements.length; //移动尾指针
        if ((rear+1) % emements.length == front) {    //如果队列已满,扩容
            doubleCapacity();
        }
    }


    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        int f = front;
        @SuppressWarnings("unchecked")
        T result = (T) elements[f];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[f] = null;     // Must null out slot
        front = (f + 1) % elements.length; //元素出对后头指针向后移位
        return result;
    }


    /**
     * @return
     */
    public int size() {
        return (rear - front + elements.length) % elements.length;
    }

    /**
     * 遍历算法
     * 移动front指针,直到front指针追上rear指针
     */
    public void traverse() {
        int i = front, j = rear;
        while (i != j) {
            System.out.println(elements[i]);
            i = (i + 1) % elements.length;
        }
    }

    /**
     * 判断队列为空的条件是front == rear
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }

    public static void main(String[] args) {
        CustomArrayQueue queue = new CustomArrayQueue();
        queue.enqueue("0000");
        queue.enqueue("1111");
        queue.enqueue("2222");
        queue.enqueue("3333");
        queue.enqueue("4444");
        queue.enqueue("5555");
        queue.enqueue("6666");
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        for (int i = 0; i < 98; i++) {
            queue.enqueue("lyx" + i);
        }
        System.out.println(queue.size());
        System.out.println("===========traverse==========");
        queue.traverse();
        System.out.println("===========traverse==========");
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
    }
}

=====END=====

© 著作权归作者所有

秋风醉了
粉丝 252
博文 532
码字总数 405694
作品 0
朝阳
程序员
私信 提问
加载中

评论(3)

CheneyWong
CheneyWong
结构都是一样的,万变不离其宗。我第一次看到这个结构,还是当年在一个嵌入式系统里面。
秋风醉了
秋风醉了 博主

引用来自“古月楼”的评论

Disruptor 就是采用这种轮询方式
在上面的代码中好像也没有轮询啊。。
古月楼
古月楼
Disruptor 就是采用这种轮询方式
Java基础之数组队列及Java堆外内存学习笔记[图]

Java基础之数组队列及Java堆外内存学习笔记[图] 1.数组 1.1 数组基本概念: 数组是一个容器,可以存储同一数据类型的N个数据;数组是一个数据结构,是数据结构中访问速度最快的; 数组是直接...

原创小博客
2018/08/25
49
0
Flatten Nested Arrays(展平嵌套数组)

这个题目是在一个公司现场面谈的时候的一个题目。虽然对这种找工作上来就做题目的现象比较反感。 但是大环境如此,也只能被蹂躏了。 中文描述 题目要求比较简单:[1,2,[3],[[4]],5,6] -> [1...

honeymose
2018/12/28
10
0
Java核心(四)你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧! Java中的集合通常指的是Collection下的三个集合框架List、Set、Q...

王磊的博客
2018/11/28
108
0
java数组、集合和数据结构知识*

一、数据结构知识。数据结构分为逻辑结构和物理结构,下面是百度百科的数据结构知识。 数据的逻辑结构:指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关...

cjun1990
2015/06/27
71
0
源码阅读(9):Java中主要的Queue、Deque结构——概述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/yinwenjie/article/details/96308528 1. Queue、Deque结构概述 Queu...

说好不能打脸
08/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

教你玩转Linux—添加批量用户

添加和删除用户对每位Linux系统管理员都是轻而易举的事,比较棘手的是如果要添加几十个、上百个甚至上千个用户时,我们不太可能还使用useradd一个一个地添加,必然要找一种简便的创建大量用户...

xiangyunyan
14分钟前
3
0
返回提示信息,如:xxx创建成功!

【服务端】在输出的方法块中,加入要输出的字段(qcm_batch_id) QCMUserType.cs: public struct QCM_Custom_Create_Batch_Out_Tag { public BASCoreType.Cmn_Out_T......

_Somuns
14分钟前
3
0
Aliyun Serverless VSCode Extension v1.12.0 发布

Aliyun Serverless VSCode Extension 是阿里云 Serverless 产品 函数计算 Function Compute 的 VSCode 插件,该插件结合了函数计算 Fun 工具以及函数计算 SDK ,是一款 VSCode 图形化开发调试...

阿里云官方博客
15分钟前
4
0
程序员如何培养解决复杂问题的能力?

今天在上网时候,突然看到了这篇文章,感觉非常的适合现在的自己去思考下,可能也适用在座的读者。程序员不仅仅是敲代码,更是一个复合能力的结合体,也不仅仅停留在技术和代码阶段。你想要成...

哥本哈根的小哥
18分钟前
6
0
市场变化驱动产品思维升级

宜信科技中心财富管理产品部负责人Bob,与大家一起聊聊个性化推荐产品功能的设计和B端产品的功能策划方式。 拓展阅读:回归架构本质,重新理解微服务 智慧金融时代,大数据和AI如何为业务赋能...

宜信技术学院
19分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部