Java数组模拟优先级队列数据结构的实例

优先级队列
如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样,我们就引入了优先级队列 这种数据结构。 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 。对于优先权相同的元素,可按先进先出次序处理或按任意优先权进行。

Java数组模拟队列
队列是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。这也就是我们平常经常用说到的先进先出原则(FIFO)。Java 中的 List 就可以作为队列来使用,在队列尾部添加元素则使用 list.add 方法,从队列头部删除元素则使用 list.remove 方法。

Java数组模拟优先级队列结构实例:

package datastruct; 

import java.util.Arrays;
import java.util.Comparator; 

/**
 * 用数组模拟 优先级队列 优先级高的排前、先出 线性表结构
 * 类似使用了比较器的 TreeSet、TreeMap
 */
public class SimulatePriorityQueue { 

  public static void main(String[] args) {
    SimulatePriorityQueue queue = new SimulatePriorityQueue(4);
//   SimulateQueue queue = new SimulateQueue();
//   System.out.println("取出元素:" + queue.remove());
    queue.insert(1);
    queue.insert(3);
    queue.insert(2);
    queue.insert(5);
    queue.insert(4);
    System.out.println("size:" + queue.size());
    System.out.println("peek:" + queue.peek());
    System.out.println("取出元素:" + queue.remove());
    System.out.println("取出元素:" + queue.remove());
    System.out.println("取出元素:" + queue.remove());
    System.out.println("取出元素:" + queue.remove());
//   System.out.println("取出元素:" + queue.remove());
    System.out.println("size:" + queue.size());
    System.out.println();
  } 

  private int mSize = 3;     //大小
  private int[] mArray;    //数组
  private int mNextItem;     //下一个位置,也可当作 当前的元素数 

  public SimulatePriorityQueue() {
    mArray = new int[mSize];
    mNextItem = 0;
  }
  public SimulatePriorityQueue(int size) {
    this.mSize = size;
    mArray = new int[mSize];
    mNextItem = 0;
  }
  /**
   * 插入元素
   * @param item
   */
  public void insert(int item) {
    if (!isFull()) {
      mArray[mNextItem++] = item;
      for (int i = 0; i < mNextItem; i++) {//冒泡排序
        for (int j = 0; j < mNextItem - 1; j++) {
          if (mArray[j] > mArray[j + 1]) {
            mArray[j] = mArray[j + 1] + 0 * (mArray[j + 1] = mArray[j]);
            System.out.println(Arrays.toString(mArray));
          }
        }
      }
      System.out.println(Arrays.toString(mArray));
    } else {
      System.out.println("----不能插入元素了,队列已满----");
    }
  }
  /**
   * 移出元素 先进先出
   * @return
   */
  public int remove() {
    if (!isEmpty()) {
      return mArray[--mNextItem];
    } else {
      throw new IllegalArgumentException("没有元素可以取出了");
    }
  }
  /**
   * 查看前面的元素
   * @return
   */
  public int peek() {
    return mArray[mNextItem - 1];
  }
  /**
   * 是否为空
   * @return
   */
  public boolean isEmpty() {
    return mNextItem == 0;
  }
  /**
   * 是否满
   * @return
   */
  public boolean isFull() {
    return mNextItem == mSize;
  }
  /**
   * size
   * @return
   */
  public int size() {
    return mNextItem;
  } 

}

输出结果:

[1, 0, 0, 0]
[1, 3, 0, 0]
[1, 2, 3, 0]
[1, 2, 3, 0]
[1, 2, 3, 5]
----不能插入元素了,队列已满----
size:4
peek:5
取出元素:5
取出元素:3
取出元素:2
取出元素:1
size:0
(0)

相关推荐

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

  • Java数据结构之队列的简单定义与使用方法

    本文实例讲述了Java数据结构之队列的简单定义与使用方法.分享给大家供大家参考,具体如下: 一.概述: 1.说明: 队列的原则时先进先出,就像生活中排队取票一样,谁排在前面谁先得到 2.有五个属性: 1)数组元素 2)最大空间 3)长度 4)队头 5)队尾 3.示例图: 二.代码实现 /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin * @version 1.0 * @S

  • java 数据结构中栈和队列的实例详解

    java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

  • Java数据结构之有效队列定义与用法示例

    本文实例讲述了Java数据结构之有效队列定义与用法.分享给大家供大家参考,具体如下: /** * @描述 有序对列 * 从任何位置插入数据都是有序的 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin */ public class SequeQueue { private long[] arr; private int maxSize;// 最大空间 private int len;// 有效长度

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

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

  • Java数据结构之队列(动力节点Java学院整理)

    队列的定义: 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表. (1)允许删除的一端称为队头(Front). (2)允许插入的一端称为队尾(Rear). (3)当队列中没有元素时称为空队列. (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表. 队列的修改是依先进先出的原则进行的.新来的成员总是加入队尾,每次离开的成员总是队列头上的(不允许中途离队). 队列的存储结构及实现 队列的顺序存储结构 (1) 顺序队列的定义: 队列

  • 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 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • Java数组模拟优先级队列数据结构的实例

    优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先

  • Java基础之数组模拟循环队列

    一.队列简介 队列是一个有序列表,遵循"先入先出"的原则,即先存入队列的数据要先取出,后存入的数据后取出. 队列有两种存储表示,顺序表示和链式表示.顺序表示可以用数组来实现. 二.数组模拟队列 用数组模拟队列时,设两个值front=0,rear=0.front表示队列首部第一个数据所在位置,rear表示尾部最后一个数据的下一个位置. 将数据插入数组队列时(入队),从尾部进行插入,即array[rear] = value,同时rear后移,rear++.取出数据时(出队),从头部取出数据

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

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

  • Java数组集合的深度复制代码实例

    这篇文章主要介绍了Java数组集合的深度复制代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java当我们想要对一个数组进行一些操作,同时又不希望对原来的数组数据有影响的时候,使用引用是不能满足我们的需求的, 这时候我们可以使用System.arraycopy()方法实现,对用这两种复制方式,我们习惯称前者为浅复制,后者为深复制.深复制的 实现方法如下: public static void arraycopyTest() { int[

  • 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

  • 解析Java中PriorityQueue优先级队列结构的源码及用法

    一.PriorityQueue的数据结构 JDK7中PriorityQueue(优先级队列)的数据结构是二叉堆.准确的说是一个最小堆. 二叉堆是一个特殊的堆, 它近似完全二叉树.二叉堆满足特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆. 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆. 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆. 下图是一个最大堆 priorityQueue队头就是给定顺序的最小元素. prio

  • Java数组传递及可变参数操作实例详解

    本文实例讲述了Java数组传递及可变参数操作.分享给大家供大家参考,具体如下: 方法可以操作传递和返回基本数据类型,但是方法中也可用来传递和返回数组.如果要向方法中传递一个数组,则方法的接收参数处必须是符合其类型的数组.而且数组属于引用数据类型,所以在把数组传递进方法之后,如果方法对数组本身做了任何修改,修改结果都是会保存下来的. 向方法中传递数组 在java中,所有对象都是通过引用进行操作的.而数组也是一种对象,当把数组作为参数传递给方法时,传递的实际上就是数组对象的引用.在方法中对数组的所有

  • 关于Java数组查询的相关问题及实例 原创

    在做数组查询的过程中,我们有时候会遇到一些问题,下面就跟随作者一起解答这些问题. Arrays 类的 binarySearch() 方法,可使用二分搜索法来搜寻指定数组,以获得指定对象.该方法返回要搜索元素的索引值. binarySearch()方法提供了多种重载形式,用于满足各种类型数组的查找需要. binarySearch()方法有两种参数类型. (1)binarySearch(Object[] a.Object key) 其中a 代表要所搜的数组,key 表示要搜索的值.如果key 包含在

  • Java 数组获取最大和最小值的实例实现

    以下实例演示了如何通过 Collections 类的 Collections.max() 和 Collections.min() 方法来查找数组中的最大和最小值: Main.java 文件: import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) { Integer[] numbers = { 8, 2, 7, 1, 4, 9

  • Java队列篇之实现数组模拟队列及可复用环形队列详解

    队列简介 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则.即先存入队列的数据,先取出,后存入的后取出. 示意图:(使用数组模拟队列示意图) 有两个分别指向头部和尾部的"指针". 数组模拟队列(无法复用) 1.实现思路 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量. 因为队列的输出.输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变

随机推荐