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

用java实现循环队列的方法:

1、添加一个属性size用来记录眼下的元素个数。

目的是当head=rear的时候。通过size=0还是size=数组长度。来区分队列为空,或者队列已满。

2、数组中仅仅存储数组大小-1个元素,保证rear转一圈之后不会和head相等。也就是队列满的时候。rear+1=head,中间刚好空一个元素。

当rear=head的时候。一定是队列空了。

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

能够进行删除的一端称为队头,这样的操作也叫出队dequeue;

能够进行插入的一端称为队尾,这样的操作也叫入队enqueue。

队列的示意图

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

如图所看到的的假溢出现象

解决的方法:使用链式存储,这显然能够。在顺序存储时。我们常见的解决的方法是把它首尾相接,构成循环队列。这能够充分利用队列的存储空间。

循环队列示意图:

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

但依旧存在一个问题:当front和rear指向同一个位置时,这代表的是队空还是队满呢?大家能够想象下这样的情景。

解决这种问题的常见做法是这种:

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

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

例如以下图:

以下我们给出循环队列,并採用另外一种方式,即牺牲一个元素空间来区分队空和队满的代码.

几个重点:

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

2、队为空的推断:front==rear;队为满的推断:(rear+1)%MAXSIZE==front。

import java.io.*;
  public class QueueArray {
  Object[] a; //对象数组,队列最多存储a.length-1个对象
  int front; //队首下标
  int rear;  //队尾下标
  public QueueArray(){
    this(10); //调用其他构造方法
  }
  public QueueArray(int size){
    a = new Object[size];
    front = 0;
    rear =0;
  }
  /**
   * 将一个对象追加到队列尾部
   * @param obj 对象
   * @return 队列满时返回false,否则返回true
   */
  public boolean enqueue(Object obj){
    if((rear+1)%a.length==front){
      return false;
    }
    a[rear]=obj;
    rear = (rear+1)%a.length;
    return true;
  }
  /**
   * 队列头部的第一个对象出队
   * @return 出队的对象,队列空时返回null
   */
  public Object dequeue(){
    if(rear==front){
      return null;
    }
    Object obj = a[front];
    front = (front+1)%a.length;
    return obj;
  }
  public static void main(String[] args) {
    QueueArray q = new QueueArray(4);
    System.out.println(q.enqueue("张三"));
    System.out.println(q.enqueue("李斯"));
    System.out.println(q.enqueue("赵五"));
    System.out.println(q.enqueue("王一"));//无法入队列,队列满
    for(int i=0;i<4;i++){
      System.out.println(q.dequeue());
    }
  }
} 

以上这篇基于Java数组实现循环队列的两种方法小结就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

您可能感兴趣的文章:

  • java实现队列数据结构代码详解
  • Java自定义实现链队列详解
  • java队列实现方法(顺序队列,链式队列,循环队列)
(0)

相关推荐

  • Java自定义实现链队列详解

    一.写在前面 数据结构中的队列应该是比较熟悉的了,就是先进先出,因为有序故得名队列,就如同排队嘛,在对尾插入新的节点,在对首删除节点.jdk集合框架也是提供也一个Queue的接口.这个接口代表一个队列.顺序队列:ArrayBlockingQueue,LinkedBlockingQueue.(上面两种是足色队列)还有一种是ConcurentLinkedQueue. 底层的实现由数组合链表两种的,数组的实现会有个弊端的,会造成假满的现象,开始的时候,队列为空的时候,对首引用变量个对尾的引用变量都为n

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

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

  • java实现队列数据结构代码详解

    什么是队列结构 一种线性结构,具有特殊的运算法则[只能在一端(队头)删除,在另一端(队尾)插入]. 分类: 顺序队列结构 链式队列结构 基本操作: 入队列 出队列 给出一些应用队列的场景 1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点. 2):售票口的人买票的顺序的按照先来先买的顺序售票. 3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候. 队列是先进先出的! 我们设置一个叫做LinkQueue<T>的泛型集合类,该类里面有 Node

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

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

  • java数组实现循环队列示例介绍

    从顶部进去数据,从底部出来数据,用数组实现队列,但是下面这个队列,只能进行一次存数值,取数值,不够完善. import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[]args){ //定义队列大小maxsize ArrayQueue arrayQueue=new ArrayQueue(3); Scanner scanner=new Scanner(System.in); char

  • PHP基于imagick扩展实现合成图片的两种方法【附imagick扩展下载】

    本文实例讲述了PHP基于imagick扩展实现合成图片的两种方法.分享给大家供大家参考,具体如下: 方法一:compositeimages /** * function: 合成图片 * @param string $output_url 图片保存路径 * @param string $img_type 图片保存类型 * @param integral $line_num 每行显示图片数量 * @param array $logo_info 每张待合成图片的信息(要求所有尺寸统一) * @para

  • Java编程求二叉树的镜像两种方法介绍

    给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

  • Python实现删除排序数组中重复项的两种方法示例

    本文实例讲述了Python实现删除排序数组中重复项的两种方法.分享给大家供大家参考,具体如下: 对于给定的有序数组nums,移除数组中存在的重复数字,确保每个数字只出现一次并返回新数组的长度 注意:不能为新数组申请额外的空间,只允许申请O(1)的额外空间修改输入数组 Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1

  • JAVA实现下载文件功能的两种方法

    第一种方法: public HttpServletResponse download(String path, HttpServletResponse response) { try { // path是指欲下载的文件的路径. File file = new File(path); // 取得文件名. String filename = file.getName(); // 取得文件的后缀名. String ext = filename.substring(filename.lastIndexO

  • 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

  • Java和scala实现 Spark RDD转换成DataFrame的两种方法小结

    一:准备数据源 在项目下新建一个student.txt文件,里面的内容为: 1,zhangsan,20 2,lisi,21 3,wanger,19 4,fangliu,18 二:实现 Java版: 1.首先新建一个student的Bean对象,实现序列化和toString()方法,具体代码如下: package com.cxd.sql; import java.io.Serializable; @SuppressWarnings("serial") public class Stude

  • Java动态验证码单线设计的两种方法

    1.java的动态验证码我这里将介绍两种方法: 一:根据java本身提供的一种验证码的写法,这种呢只限于大家了解就可以了,因为java自带的模式编写的在实际开发中是没有意义的,所以只供学习一下就可以了,待会讲解的第二种呢就是我们需要掌握的一种模式了: 第一种的代码如下: import java.awt.Color; import java.awt.Font; import java.awt.Graphics; import java.awt.image.BufferedImage; import

随机推荐