转载

Java循环队列原理与用法详解

本文实例讲述了Java循环队列原理与用法。分享给大家供大家参考，具体如下：

在正式进行循环队列学习之前，我们先来看看在顺序队列中删除队首元素出现的问题

（1）设一个容量为capacity=8，size=5(a,b,c,d,e)的数组，左侧为队首、右侧为队尾。

（2）出队一个元素后，需整体往前移动一位

#出队

#2整体前移一位

关于该种操作方式我们很容易得出时间复杂度为O(n)。

这时我们就想可不可以在出队元素后，整体元素不往前移，而是在数组中记下队首front是谁，同时队尾tail指向在下一次元素入队时的位置，这样当再有出队时只需要维护一下front的指向即可，而不需移动元素。就这样我们就有了循环队列的情况。

2.循环队列原理

(1)初始，数组整体为空时，队首front、队尾tail指向同一个位置（数组索引为0的地方）也即front==tail 时队列为空

(2)当往数组中添加元素后，

(3)出队一个元素，front指向新的位置

(4)入队元素，tail叠加

(5)当tail不能再增加时，数组前面还有空余，此时循环队列就该出场了。

此时数组应该变为这样：

在往数组中添加一个元素：

这样数组就已经满了（tail+1==front 队列满），开始出发扩容操作。【capacity中，浪费一个空间】。

为了tail能返回到数组的前面位置，将队列满的表达式变为【（tail+1）%c==front】这样数组就可以循环移动了。

3.循环队列代码实现

新建一个类LoopQueue并实现接口Queue。

#1：接口Queue代码如下：

package Queue;

public interface Queue<E> {
  //获取队列中元素个数
  int getSize();

  //队列中元素是否为空
  boolean isEmpty();

  //入队列
  void enqueue(E e);

  //出队列
  E dequeue();

  //获取队首元素
  E getFront();
}

#2：LoopQueue相关代码：

package Queue;

//循环队列
public class LoopQueue<E> implements Queue<E> {
  private E[] data;
  private int front, tail;
  private int size;//队列中元素个数

  //构造函数，传入队列的容量capacity构造函数
  public LoopQueue(int capacity) {
    data = (E[]) new Object[capacity + 1];//浪费与一个空间
    front = 0;
    tail = 0;
    size = 0;
  }

  //无参构造函数，默认队列的容量capacity=10
  public LoopQueue() {
    this(10);
  }

  //真正容量
  public int getCapacity() {
    return data.length - 1;
  }

  //队列是否为空
  @Override
  public boolean isEmpty() {
    return front == tail;
  }

  //队列中元素个数
  @Override
  public int getSize() {
    return size;
  }

  //入队列操作
  @Override
  public void enqueue(E e) {
    if ((tail + 1) % data.length == front) {//队列已满，需要扩容
      resize(getCapacity() * 2);
    }
    data[tail] = e;
    tail = (tail + 1) % data.length;
    size++;
  }

  //出队操作

  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new IllegalArgumentException("队列为空");
    }

    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("队列为空");
    }
    return data[front];
  }

  //改变容量
  private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity + 1];
    for (int i = 0; i < size; i++) {
      newData[i] = data[(front + i) % data.length];//循环数组防止越界
    }
    data = newData;
    front = 0;
    tail = size;
  }

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

}

在关于LoopQueue类中需要注意的：

（1）第11行中的+1是capacity需要浪费一个空间，故在实例化是多加1

data = (E[]) new Object[capacity + 1];//浪费与一个空间

（2）地24行真正的容量是data.length-1，这是由于有一个空间是浪费的。

data.length - 1;

（3）关于入队中第46行tail值的说明

为了保证入队是循环操作，tail值的变化规律为

tail = (tail + 1) % data.length;

（4）关于82行的数据迁移操作，取余操作是为了防止循环数组时越界。

newData[i] = data[(front + i) % data.length];//循环数组防止越界

#3直接在LoopQueue中添加一个main函数进行测试，相关代码如下：

//测试用例
  public static void main(String[] args) {
    LoopQueue<Integer> queue = new LoopQueue<Integer>();
    for (int i = 0; i < 10; i++) {
      queue.enqueue(i);
      System.out.println(queue);

      if(i%3==2){//每添加3个元素出队列一个
        queue.dequeue();
        System.out.println(queue);
      }

    }

  }

结果为：

4.循环队列时间复杂度

到此我们就实现了一个循环队列操作，解决了在顺序队列中出队时的时间复杂度为O(n)的情况，在循环队列中出队的时间复杂度为O(1)。

源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LoopQueue.java

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

时间：2020-03-17

java数据结构与算法之双向循环队列的数组实现方法

本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

Java用数组实现循环队列的示例

复习了下数据结构,用Java的数组实现一下循环队列. 队列的类 //循环队列 class CirQueue{ private int QueueSize; private int front; private int rear; private int[] queueList ; public CirQueue(int QueueSize){ this.QueueSize = QueueSize; queueList = new int[QueueSize]; front = 0; rear =

java多线程消息队列的实现代码

本文介绍了java多线程消息队列的实现代码,分享给大家,希望对大家有帮助,顺便也自己留个笔记 1.定义一个队列缓存池: //static修饰的成员变量和成员方法独立于该类的任何对象.也就是说,它不依赖类特定的实例,被类的所有实例共享. private static List<Queue> queueCache = new LinkedList<Queue>(); 2.定义队列缓冲池最大消息数,如果达到该值,那么队列检入将等待检出低于该值时继续进行. private Integer

Java数据结构之循环队列简单定义与用法示例

本文实例讲述了Java数据结构之循环队列简单定义与用法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 与普通队列的区别在于循环队列添加数据时,如果其有效数据end == maxSize - 1(最大空间)的话,end指针又移动到-1的位置删除数据时,如果head== maxSize时 head指针移动到0的位置 2.示例图: 二.实现代码: package com.java.queue; /** * @描述对列 * @项目名称 Java_DataStruct * @包名 com.

java使用数组和链表实现队列示例

(1)用数组实现的队列: 复制代码代码如下: //先自己定义一个接口 public interface NetJavaList { public void add(Student t); //继承该接口的类必须实现的方法 public Student get(int index);//队列的加入,取出,队列的大小 public int size(); } 定义一个学生类复制代码代码如下: class Student { private String na

Java利用Redis实现消息队列的示例代码

本文介绍了Java利用Redis实现消息队列的示例代码,分享给大家,具体如下: 应用场景为什么要用redis? 二进制存储.java序列化传输.IO连接数高.连接频繁一.序列化这里编写了一个java序列化的工具,主要是将对象转化为byte数组,和根据byte数组反序列化成java对象; 主要是用到了ByteArrayOutputStream和ByteArrayInputStream; 注意:每个需要序列化的对象都要实现Serializable接口; 其代码如下: package Utils

Java 队列实现原理及简单实现代码

Java 队列实现原理 "队列"这个单词是英国人说的"排".在英国"排队"的意思就是站到一排当中去.计算机科学中,队列是一种数据结构,有点类似栈,只是在队列中第一个插入的数据项也会最先被移除,而在栈中,最后插入的数据项最先移除.队列的作用就像电影院前的人们站成的排一样:第一个进入附属的人将最先到达队头买票.最后排队的人最后才能买到票. 队列和栈一样也被用作程序员的工具.它也可以用于模拟真实世界的环境,例如模拟人们在银行里排队等待,飞机等待起飞,或

java中栈和队列的实现和API的用法(详解)

在java中要实现栈和队列,需要用到java集合的相关知识,特别是Stack.LinkedList等相关集合类型. 一.栈的实现栈的实现,有两个方法:一个是用java本身的集合类型Stack类型:另一个是借用LinkedList来间接实现Stack. 1.Stack实现直接用Stack来实现非常方便,常用的api函数如下: boolean isEmpty() // 判断当前栈是否为空 synchronized E peek() //获得当前栈顶元素 synchro

剖析Java中阻塞队列的实现原理及应用场景

我们平时使用的一些常见队列都是非阻塞队列,比如PriorityQueue.LinkedList(LinkedList是双向链表,它实现了Dequeue接口). 使用非阻塞队列的时候有一个很大问题就是:它不会对当前线程产生阻塞,那么在面对类似消费者-生产者的模型时,就必须额外地实现同步策略以及线程间唤醒策略,这个实现起来就非常麻烦.但是有了阻塞队列就不一样了,它会对当前线程产生阻塞,比如一个线程从一个空的阻塞队列中取元素,此时线程会被阻塞直到阻塞队列中有了元素.当队列中有元素后,被阻塞的线程会自动

Java实现栈和队列面试题

面试的时候,栈和队列经常会成对出现来考察.本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()的栈,要求min.push.pop.的时间复杂度都是O(1) (6)判断栈的push和pop序列是否一致 1.栈的创建: 我们接下来通过链表的形式来创建栈,方便扩充. 代码实现: public class Stack { public Node head; public Node current; //方法

java队列实现方法(顺序队列,链式队列,循环队列)

双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略.ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列.ArrayDeque和LinkedList都是线程不安全的.PriorityQueue优先队列也在JDK. 1.顺序队列的实现 package lang; import java.io.Serializable; import java.util.Arrays; /** * @ClassName: ArrayQueue *

基于Java数组实现循环队列的两种方法小结

用java实现循环队列的方法: 1.添加一个属性size用来记录眼下的元素个数. 目的是当head=rear的时候.通过size=0还是size=数组长度.来区分队列为空,或者队列已满. 2.数组中仅仅存储数组大小-1个元素,保证rear转一圈之后不会和head相等.也就是队列满的时候.rear+1=head,中间刚好空一个元素. 当rear=head的时候.一定是队列空了. 队列(Queue)两端同意操作的类型不一样: 能够进行删除的一端称为队头,这样的操作也叫出队dequeue: 能够进行插

js删除Array数组中指定元素的两种方法

本节内容: js删除Array数组中指定元素方法一, /* * 方法:Array.remove(dx) 通过遍历,重构数组 * 功能:删除数组元素. * 参数:dx删除元素的下标. */ Array.prototype.remove=function(dx) { if(isNaN(dx)||dx>this.length){return false;} for(var i=0,n=0;i<this.length;i++) { if(this[i]!=this[dx]) { this[n++]=

java发送http get请求的两种方法(总结)

长话短说,废话不说一.第一种方式,通过HttpClient方式,代码如下: public static String httpGet(String url, String charset) throws HttpException, IOException { String json = null; HttpGet httpGet = new HttpGet(); // 设置参数 try { httpGet.setURI(new URI(url)); } catch (URISyntaxExc

Spring整合Struts2的两种方法小结

spring提供了一个ContextLoaderListener,该监听类实现了ServletContextListener接口.该类可以作为Listener使用,它会在创建时自动查找WEB-INF/下的applicationContext.xml文件,因此如果只有一个配置文件且配置文件命名为applicationContext.xml,则只需在web.xml文件中增加如下配置片段:  <listene

js中将多个语句写成一个语句的两种方法小结

Javascript 中将多个语句写成一个语句的两种方法小结一.使用逗号运算符将多个语句写成一个语句 1.一次声明多个变量 var i=1,j=1,k=1 2.多个语句用逗号间隔 i=1,j=i+2,k=j+2 二.使用花括号将多个语句写成一个语句 if语句.while语句.do/while语句.for语句.for/in语句和function语句等语句后都只能跟随一个子语句,此时可以用{和}将多条语句围起来变成一个语句. 复制代码代码如下: if(username==null)

jquery的ajax提交form表单的两种方法小结(推荐)

jquery的ajax提交form表单的两种方法小结(推荐) 方法一: function AddHandlingFeeToRefund() { var AjaxURL= "../OrderManagement/AjaxModifyOrderService.aspx"; alert($('#formAddHandlingFee').serialize()); $.ajax({ type: "POST", dataType: "html", url:

js判断字符是否是汉字的两种方法小结

有时需要判断一个字符是不是汉字,比如在用户输入含有中英文的内容时,需要判断是否超过规定长度就要用到.用 Javascript 判断通常有两种方法. 1.用正则表达式判断复制代码代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xml

JavaScript重定向URL参数的两种方法小结

这篇文章主要介绍的是JavaScript重定向URL参数的两种方法,下面话不多说,直接看示例代码. 一.字符拼接形式 function setUri(para, val) { var strNewUrl = new String(); var strUrl = new String(); var url = window.location.href; strUrl = window.location.href; if (strUrl.indexOf("?") != -1) { strU

基于jquery实现导航菜单高亮显示（两种方法）

项目需求: 实现原理:当选中当前元素时,给当前元素添加样式,同级元素移除样式. 点击不同的导航菜单实现当前点击的菜单是高亮的,点击导航下面的某个分类,分类所属的导航也必须是高亮的,点击某一篇文章,文章所属的导航菜单也必须是高亮的. 效果图如下: 示例代码一: 具体示例代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/x

php获取数组中重复数据的两种方法

(1)利用php提供的函数,array_unique和array_diff_assoc来实现复制代码代码如下: <?php function FetchRepeatMemberInArray($array) { // 获取去掉重复数据的数组 $unique_arr = array_unique ( $array ); // 获取重复数据的数组 $repeat_arr = array_diff_assoc ( $array, $unique_arr );

JavaScript数组深拷贝和浅拷贝的两种方法

例如这个例子: 复制代码代码如下: var arr = ["One","Two","Three"]; var arrto = arr;arrto[1] = "test";document.writeln("数组的原始值:" + arr + "<br />");//Export:数组的原始值:One,test,Threedocument.writeln("数组的新值

原文 https://www.zhangshengrong.com/p/24NjoR93XB/

正文到此结束