【Java数据结构学习笔记之三】Java数据结构与算法之队列(Queue)实现

简介:   本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点: 队列的抽象数据类型 顺序队列的设计与实现 链式队列的设计与实现 队列应用的简单举例 优先队列的设置与实现双链表实现 队列的抽象数据类型   队列同样是一种特殊的线性表,其插入和删除的操作分别在表的两端进行,队列的特点就是先进先出(First In First Out)。

  本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点:

  • 队列的抽象数据类型
  • 顺序队列的设计与实现
  • 链式队列的设计与实现
  • 队列应用的简单举例
  • 优先队列的设置与实现双链表实现

队列的抽象数据类型

  队列同样是一种特殊的线性表,其插入和删除的操作分别在表的两端进行,队列的特点就是先进先出(First In First Out)。我们把向队列中插入元素的过程称为入队(Enqueue),删除元素的过程称为出队(Dequeue)并把允许入队的一端称为队尾,允许出的的一端称为队头,没有任何元素的队列则称为空队。其一般结构如下:

关于队列的操作,我们这里主要实现入队,出队,判断空队列和清空队列等操作,声明队列接口Queue(队列抽象数据类型)如下:

 1 /**
 2 * 队列抽象数据类型
 3 */
 4 public interface Queue<T> {
 5 
 6    /**
 7     * 返回队列长度
 8     * @return
 9     */
10    int size();
11 
12    /**
13     * 判断队列是否为空
14     * @return
15     */
16    boolean isEmpty();
17 
18    /**
19     * data 入队,添加成功返回true,否则返回false,可扩容
20     * @param data
21     * @return
22     */
23    boolean add(T data);
24 
25    /**
26     * offer 方法可插入一个元素,这与add 方法不同,
27     * 该方法只能通过抛出未经检查的异常使添加元素失败。
28     * 而不是出现异常的情况,例如在容量固定(有界)的队列中
29     * NullPointerException:data==null时抛出
30     * @param data
31     * @return
32     */
33    boolean offer(T data);
34 
35    /**
36     * 返回队头元素,不执行删除操作,若队列为空,返回null
37     * @return
38     */
39    T peek();
40 
41    /**
42     * 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
43     * @return
44     */
45    T element();
46 
47    /**
48     * 出队,执行删除操作,返回队头元素,若队列为空,返回null
49     * @return
50     */
51    T poll();
52 
53    /**
54     * 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
55     * @return
56     */
57    T remove();
58 
59    /**
60     * 清空队列
61     */
62    void clearQueue();
63 }

下面我们就来分别实现顺序队列和链式队列

顺序队列的设计与实现

  关于顺序队列(底层都是利用数组作为容器)的实现,我们将采用顺序循环队列的结构来实现,在给出实现方案前先来分析一下为什么不直接使用顺序表作为底层容器来实现。实际上采用顺序表实现队列时,入队操作直接执行顺序表尾部插入操作,其时间复杂度为O(1),出队操作直接执行顺序表头部删除操作,其时间复杂度为O(n),主要用于移动元素,效率低,既然如此,我们就把出队的时间复杂度降为O(1)即可,为此在顺序表中添加一个头指向下标front和尾指向下标,出队和入队时只要改变front、rear的下标指向取值即可,此时无需移动元素,因此出队的时间复杂度也就变为O(1)。其过程如下图所示

以上是添加front和rear下标记录的顺序表插入过程

从图的演示过程,(a)操作时,是空队列此时front和rear都为-1,同时可以发现虽然我们通过给顺序表添加front和rear变量记录下标后使用得出队操作的时间复杂度降为O(1),但是却出现了另外一个严重的问题,那就是空间浪费,从图中的(d)和(e)操作可以发现,20和30出队后,遗留下来的空间并没有被重新利用,反而是空着,所以导致执行(f)操作时,出现队列已满的假现象,这种假现象我们称之为假溢出,之所以出现这样假溢出的现象是因为顺序表队列的存储单元没有重复利用机制,而解决该问题的最合适的方式就是将顺序队列设计为循环结构,接下来我们就通过循环顺序表来实现顺序队列。
  顺序循环队列就是将顺序队列设计为在逻辑结构上收尾相接的循环结构,这样我们就可以重复利用存储单元,其过程如下所示:

 

简单分析一下:
其中采用循环结构的顺序表,可以循环利用存储单元,因此有如下计算关系(其中size为队列长度):

//其中front、rear的下标的取值范围是0~size-1,不会造成假溢出。
front=(front+1)%size;//队头下标
rear=(rear+1)%size;

front为队头元素的下标,rear则指向下一个入队元素的下标

当front=rear时,我们约定队列为空。

出队操作改变front下标指向,入队操作改变rear下标指向,size代表队列容量。

约定队列满的条件为front=(rear+1)%size,注意此时队列中仍有一个空的位置,此处留一个空位主要用于避免与队列空的条件front=rear相同。

队列内部的数组可扩容,并按照原来队列的次序复制元素数组
了解了队列的实现规则后,我们重点分析一下入队add方法和出队poll方法,其中入队add方法实现如下:

/**
  * data 入队,添加成功返回true,否则返回false,可扩容
  * @param data
  * @return
  */
 @Override
 public boolean add(T data) {
     //判断是否满队
     if (this.front==(this.rear+1)%this.elementData.length){
         ensureCapacity(elementData.length*2+1);
     }
     //添加data
     elementData[this.rear]=data;
     //更新rear指向下一个空元素的位置
     this.rear=(this.rear+1)%elementData.length;
     size++;
     return true;
 }

在add方法中我们先通过this.front==(this.rear+1)%this.elementData.length判断队列是否满,在前面我们约定过队列满的条件为front=(rear+1)%size,如果队列满,则先通过ensureCapacity(elementData.length*2+1)扩容,该方法实现如下:

 1 /**
 2   * 扩容的方法
 3   * @param capacity
 4   */
 5  public void ensureCapacity(int capacity) {
 6      //如果需要拓展的容量比现在数组的容量还小,则无需扩容
 7      if (capacity<size)
 8          return;
 9 
10      T[] old = elementData;
11      elementData= (T[]) new Object[capacity];
12      int j=0;
13      //复制元素
14      for (int i=this.front; i!=this.rear ; i=(i+1)%old.length) {
15          elementData[j++] = old[i];
16      }
17      //恢复front,rear指向
18      this.front=0;
19      this.rear=j;
20  }

这个方法比较简单,主要创建一个新容量的数组,并把旧数组中的元素复制到新的数组中,这里唯一的要注意的是,判断久数组是否复制完成的条件为i!=this.rear,同时循环的自增条件为i=(i+1)%old.length。扩容后直接通过rear添加新元素,最后更新rear指向下一个入队新元素。对于出队操作poll的实现如下:

 1 /**
 2  * 出队,执行删除操作,返回队头元素,若队列为空,返回null
 3  * @return
 4  */
 5 @Override
 6 public T poll() {
 7     T temp=this.elementData[this.front];
 8     this.front=(this.front+1)%this.elementData.length;
 9     size--;
10     return temp;
11 }

出队操作相对简单些,直接存储要删除元素的数据,并更新队头front的值,最后返回删除元素的数据。ok~,关于循环结构的顺序队列,我们就分析到此,最后给出循环顺序队列的实现源码,其他方法比较简单,注释也很清楚,就不过多分析了:

  1 import java.io.Serializable;
  2 import java.util.NoSuchElementException;
  3 
  4 /**
  5  * 顺序队列的实现
  6  */
  7 public class SeqQueue<T> implements Queue<T> ,Serializable {
  8 
  9 
 10     private static final long serialVersionUID = -1664818681270068094L;
 11     private static final int  DEFAULT_SIZE = 10;
 12 
 13     private T elementData[];
 14 
 15     private int front,rear;
 16 
 17     private int size;
 18 
 19 
 20     public SeqQueue(){
 21         elementData= (T[]) new Object[DEFAULT_SIZE];
 22         front=rear=0;
 23     }
 24 
 25     public SeqQueue(int capacity){
 26         elementData= (T[]) new Object[capacity];
 27         front=rear=0;
 28     }
 29 
 30     @Override
 31     public int size() {
 32 //        LinkedList
 33         return size;
 34     }
 35 
 36     @Override
 37     public boolean isEmpty() {
 38         return front==rear;
 39     }
 40 
 41     /**
 42      * data 入队,添加成功返回true,否则返回false,可扩容
 43      * @param data
 44      * @return
 45      */
 46     @Override
 47     public boolean add(T data) {
 48         //判断是否满队
 49         if (this.front==(this.rear+1)%this.elementData.length){
 50             ensureCapacity(elementData.length*2+1);
 51         }
 52         //添加data
 53         elementData[this.rear]=data;
 54         //更新rear指向下一个空元素的位置
 55         this.rear=(this.rear+1)%elementData.length;
 56         size++;
 57         return true;
 58     }
 59 
 60     /**
 61      * offer 方法可插入一个元素,这与add 方法不同,
 62      * 该方法只能通过抛出未经检查的异常使添加元素失败。
 63      * 而不是出现异常的情况,例如在容量固定(有界)的队列中
 64      * NullPointerException:data==null时抛出
 65      * IllegalArgumentException:队满,使用该方法可以使Queue的容量固定
 66      * @param data
 67      * @return
 68      */
 69     @Override
 70     public boolean offer(T data) {
 71         if (data==null)
 72             throw new NullPointerException("The data can\'t be null");
 73         //队满抛出异常
 74         if (this.front==(this.rear+1)%this.elementData.length){
 75             throw new IllegalArgumentException("The capacity of SeqQueue has reached its maximum");
 76         }
 77 
 78         //添加data
 79         elementData[this.rear]=data;
 80         //更新rear指向下一个空元素的位置
 81         this.rear=(this.rear+1)%elementData.length;
 82         size++;
 83 
 84         return true;
 85     }
 86 
 87     /**
 88      * 返回队头元素,不执行删除操作,若队列为空,返回null
 89      * @return
 90      */
 91     @Override
 92     public T peek() {
 93         return elementData[front];
 94     }
 95 
 96     /**
 97      * 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
 98      * @return
 99      */
100     @Override
101     public T element() {
102         if(isEmpty()){
103             throw new NoSuchElementException("The SeqQueue is empty");
104         }
105         return peek();
106     }
107 
108     /**
109      * 出队,执行删除操作,返回队头元素,若队列为空,返回null
110      * @return
111      */
112     @Override
113     public T poll() {
114         T temp=this.elementData[this.front];
115         this.front=(this.front+1)%this.elementData.length;
116         size--;
117         return temp;
118     }
119 
120     /**
121      * 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
122      * @return
123      */
124     @Override
125     public T remove() {
126         if (isEmpty()){
127             throw new NoSuchElementException("The SeqQueue is empty");
128         }
129         return poll();
130     }
131 
132     @Override
133     public void clearQueue() {
134         for (int i=this.front; i!=this.rear ; i=(i+1)%elementData.length) {
135             elementData[i] = null;
136         }
137         //复位
138         this.front=this.rear=0;
139         size=0;
140     }
141 
142     /**
143      * 扩容的方法
144      * @param capacity
145      */
146     public void ensureCapacity(int capacity) {
147         //如果需要拓展的容量比现在数组的容量还小,则无需扩容
148         if (capacity<size)
149             return;
150 
151         T[] old = elementData;
152         elementData= (T[]) new Object[capacity];
153         int j=0;
154         //复制元素
155         for (int i=this.front; i!=this.rear ; i=(i+1)%old.length) {
156             elementData[j++] = old[i];
157         }
158         //恢复front,rear指向
159         this.front=0;
160         this.rear=j;
161     }
162 }

链式队列的设计与实现

  分析完顺序队列,我们接着看看链式队列的设计与实现,对于链式队列,将使用带头指针front和尾指针rear的单链表实现,front直接指向队头的第一个元素,rear指向队尾的最后一个元素,其结构如下:

  之所以选择单链表(带头尾指针)而不采用循环双链表或者双链表主要是双链表的空间开销(空间复杂度,多前继指针)相对单链表来说大了不少,而单链表只要新增头指针和尾指针就可以轻松实现常数时间内(时间复杂度为O(1))访问头尾结点。下面我们来看看如何设计链式队列:

以上述的图为例分别设置front和rear指向队头结点和队尾结点,使用单链表的头尾访问时间复杂度为O(1)。

设置初始化空队列,使用front=rear=null,并且约定条件front==null&&rear==null成立时,队列为空。

出队操作时,若队列不为空获取队头结点元素,并删除队头结点元素,更新front指针的指向为front=front.next

入队操作时,使插入元素的结点在rear之后并更新rear指针指向新插入元素。

当第一个元素入队或者最后一个元素出队时,同时更新front指针和rear指针的指向。
这一系列过程如下图所示:

ok~,关于链式队列的设计都分析完,至于实现就比较简单了,和之前分析过的单链表区别不大,因此这里我们直接给出实现代码即可:

  1 import com.zejian.structures.LinkedList.singleLinked.Node;
  2 
  3 import java.io.Serializable;
  4 import java.util.*;
  5 
  6 /**
  7  * 链式队列的实现
  8  */
  9 public class LinkedQueue<T> implements Queue<T> ,Serializable{
 10     private static final long serialVersionUID = 1406881264853111039L;
 11     /**
 12      * 指向队头和队尾的结点
 13      * front==null&&rear==null时,队列为空
 14      */
 15     private Node<T> front,rear;
 16 
 17     private int size;
 18     /**
 19      * 用于控制最大容量,默认128,offer方法使用
 20      */
 21     private int maxSize=128;
 22 
 23     public LinkedQueue(){
 24         //初始化队列
 25         this.front=this.rear=null;
 26     }
 27 
 28     @Override
 29     public int size() {
 30         return size;
 31     }
 32 
 33     public void setMaxSize(int maxSize){
 34         this.maxSize=maxSize;
 35     }
 36 
 37     @Override
 38     public boolean isEmpty() {
 39         return front==null&&rear==null;
 40     }
 41 
 42     /**
 43      * data 入队,添加成功返回true,否则返回false,可扩容
 44      * @param data
 45      * @return
 46      */
 47     @Override
 48     public boolean add(T data) {
 49         Node<T> q=new Node<>(data,null);
 50         if (this.front==null) {//空队列插入
 51             this.front = q;
 52         } else {//非空队列,尾部插入
 53             this.rear.next=q;
 54         }
 55         this.rear=q;
 56         size++;
 57         return true;
 58     }
 59 
 60     /**
 61      * offer 方法可插入一个元素,这与add 方法不同,
 62      * 该方法只能通过抛出未经检查的异常使添加元素失败。
 63      * 而不是出现异常的情况,例如在容量固定(有界)的队列中
 64      * NullPointerException:data==null时抛出
 65      * IllegalArgumentException:队满,使用该方法可以使Queue的容量固定
 66      * @param data
 67      * @return
 68      */
 69     @Override
 70     public boolean offer(T data) {
 71         if (data==null)
 72             throw new NullPointerException("The data can\'t be null");
 73         if (size>=maxSize)
 74             throw new IllegalArgumentException("The capacity of LinkedQueue has reached its maxSize:128");
 75 
 76         Node<T> q=new Node<>(data,null);
 77         if (this.front==null) {//空队列插入
 78             this.front = q;
 79         } else {//非空队列,尾部插入
 80             this.rear.next=q;
 81         }
 82         this.rear=q;
 83         size++;
 84         return false;
 85     }
 86 
 87     /**
 88      * 返回队头元素,不执行删除操作,若队列为空,返回null
 89      * @return
 90      */
 91     @Override
 92     public T peek() {
 93         return this.isEmpty()? null:this.front.data;
 94     }
 95 
 96     /**
 97      * 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
 98      * @return
 99      */
100     @Override
101     public T element() {
102         if(isEmpty()){
103             throw new NoSuchElementException("The LinkedQueue is empty");
104         }
105         return this.front.data;
106     }
107 
108     /**
109      * 出队,执行删除操作,返回队头元素,若队列为空,返回null
110      * @return
111      */
112     @Override
113     public T poll() {
114         if (this.isEmpty())
115             return null;
116         T x=this.front.data;
117         this.front=this.front.next;
118         if (this.front==null)
119             this.rear=null;
120         size--;
121         return x;
122     }
123 
124     /**
125      * 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
126      * @return
127      */
128     @Override
129     public T remove() {
130         if (isEmpty()){
131             throw new NoSuchElementException("The LinkedQueue is empty");
132         }
133         T x=this.front.data;
134         this.front=this.front.next;
135         if (this.front==null)
136             this.rear=null;
137         size--;
138         return x;
139     }
140 
141     @Override
142     public void clearQueue() {
143         this.front= this.rear=null;
144         size=0;
145     }
146 }

队列应用的简单举例

  1. 模拟现实世界中的队列,如售票柜台的队列以及其他先到先服务的场景。
  2. 计算客户在呼叫中心等待的时间。
  3. 异步数据的传输(文件输入输出、管道、嵌套字)。
  4. 操作系统中的优先级任务执行。
  5. 短信群体发送 应用的发布订阅模式

优先队列的设置与实现(双链表实现)

  了解完循环顺序队列和链式队列的实现后,我们最后再来了解一个特殊的队列,也就是优先队列,在某些情况下,有些应用系统要求不仅需要按照“先来先服务”的原则进行,而且还需按照任务的重要或紧急程度进行排队处理,此时就需要使用到优先队列。比如在操作系统中进行进程调度管理,每个进程都具备一个优先级值以表示进程的紧急程度,优先级高的进行先执行,同等级进程按照先进先出的原则排队处理,此时操作系统使用的便是优先队列管理和调度进程。
  优先级队列也是一种特殊的数据结构,队列中的每个元素都有一个优先级,若每次出队的是具有最高优先级的元素,则称为降序优先级队列(总是先删除最大的元素)。若每次出队的是值最小的元素,则称为升序优先级队列(总是先删除最小的元素),通常情况下我们所说的优先队列,一般是指降序优先级队列。关于优先队列的实现,可以使用有序数组或者有序链表,也可以使用二叉树(二叉堆)实现,这里我们仅给出有序链表的简单实现方案。而二叉树的实现,留着后面我们分析完树时再给出。好~,这里使用之前分析过的MyLikedList作为基底,实现一个排序的SortLinkedList继承自MyLinkedList,这里需要注意的是排序链表中的T类型必须是实现了Comparable接口的类型,在SortLinkedList中主要重写添加的add方法,插入逻辑是,通过比较元素的大小加入,而非简单下标或尾部插入,其实现如下:

 1 import java.io.Serializable;
 2 import java.util.Iterator;
 3 import java.util.ListIterator;
 4 
 5 /**
 6  * 排序list的简单实现
 7  */
 8 public class SortMyLinkedList<T extends Comparable<? extends T>> extends MylinkeList<T> implements Serializable {
 9 
10     private static final long serialVersionUID = -4783131709270334156L;
11 
12     @Override
13     public boolean add(T data) {
14         if(data==null)
15             throw new NullPointerException("data can\'t be null");
16 
17         Comparable cmp =data;//这里需要转一下类型,否则idea编辑器上检验不通过.
18 
19         if(this.isEmpty() || cmp.compareTo(this.last.prev.data) > 0){
20              return super.add(data);//直接尾部添加,last不带数据的尾结点
21         }
22 
23         Node<T> p=this.first.next;
24         //查找插入点
25         while (p!=null&&cmp.compareTo(p.data)>0)
26             p=p.next;
27 
28         Node<T> q=new Node<>(p.prev,data,p);
29         p.prev.next=q;
30         p.prev=q;
31 
32         size++;
33         //记录修改
34         modCount++;
35 
36         return true;
37     }
38 
39     /**
40      * 不根据下标插入,只根据比较大小插入
41      * @param index
42      * @param data
43      */
44     @Override
45     public void add(int index, T data) {
46         this.add(data);
47     }
48 
49 
50     /**
51      * 未实现
52      * @param index
53      * @return
54      */
55     @Override
56     public ListIterator<T> listIterator(int index) {
57         return null;
58     }
59 
60     /**
61      * 未实现
62      * @return
63      */
64     @Override
65     public Iterator<T> iterator() {
66         return null;
67     }
68 
69     //测试
70     public static void main(String[] args){
71         SortMyLinkedList<Integer> list=new SortMyLinkedList<>();
72         list.add(50);
73         list.add(40);
74         list.add(80);
75         list.add(20);
76         print(list);
77     }
78 
79     public static void print(SortMyLinkedList mylinkeList){
80         for (int i=0;i<mylinkeList.size();i++) {
81             System.out.println("i->"+mylinkeList.get(i));
82         }
83     }
84 }

接着以SortMyLinkedList为基底实现优先队列PriorityQueue,实现源码如下,实现比较简单,感觉没啥好说的:

  1 import com.zejian.structures.LinkedList.MyCollection.SortMyLinkedList;
  2 
  3 import java.io.Serializable;
  4 import java.util.NoSuchElementException;
  5 
  6 /**
  7  * 优先队列的简单实现,采用排序双链表,T必须实现Comparable接口
  8  */
  9 public class PriorityQueue<T extends Comparable<? extends T>> implements Queue<T> ,Serializable {
 10 
 11     private static final long serialVersionUID = 8050142086009260625L;
 12 
 13     private SortMyLinkedList<T> list;//排序循环双链表
 14 
 15     private boolean asc;//true表示升序,false表示降序
 16 
 17     /**
 18      * 用于控制最大容量,默认128,offer方法使用
 19      */
 20     private int maxSize=128;
 21     /**
 22      * 初始化队列
 23      * @param asc
 24      */
 25     public PriorityQueue(boolean asc){
 26         this.list=new SortMyLinkedList<>();
 27         this.asc=asc;//默认升序
 28     }
 29 
 30     public int getMaxSize() {
 31         return maxSize;
 32     }
 33 
 34     public void setMaxSize(int maxSize) {
 35         this.maxSize = maxSize;
 36     }
 37 
 38     @Override
 39     public int size() {
 40         return list.size();
 41     }
 42 
 43     @Override
 44     public boolean isEmpty() {
 45         return list.isEmpty();
 46     }
 47 
 48     /**
 49      * data 入队,添加成功返回true,否则返回false
 50      * @param data
 51      * @return
 52      */
 53     @Override
 54     public boolean add(T data) {
 55         return list.add(data);
 56     }
 57 
 58     /**
 59      * offer 方法可插入一个元素,这与add 方法不同,
 60      * 该方法只能通过抛出未经检查的异常使添加元素失败。
 61      * 而不是出现异常的情况,例如在容量固定(有界)的队列中
 62      * NullPointerException:data==null时抛出
 63      * IllegalArgumentException:队满,使用该方法可以使Queue的容量固定
 64      * @param data
 65      * @return
 66      */
 67     @Override
 68     public boolean offer(T data) {
 69         if (data==null)
 70             throw new NullPointerException("The data can\'t be null");
 71         if (list.size()>=maxSize)
 72             throw new IllegalArgumentException("The capacity of PriorityQueue has reached its maxSize:128");
 73 
 74         return add(data);
 75     }
 76 
 77     /**
 78      * 返回队头元素,不执行删除操作,若队列为空,返回null
 79      * @return
 80      */
 81     @Override
 82     public T peek() {
 83         if(isEmpty()){
 84             return null;
 85         }
 86         return this.asc ? this.list.get(0):this.list.get(size()-1);
 87     }
 88 
 89     /**
 90      * 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
 91      * @return
 92      */
 93     @Override
 94     public T element() {
 95         if(isEmpty()){
 96             throw new NoSuchElementException("The PriorityQueue is empty");
 97         }
 98         return peek();
 99     }
100 
101     /**
102      * 出队,执行删除操作,返回队头元素,若队列为空,返回null
103      * @return
104      */
105     @Override
106     public T poll() {
107         if(isEmpty()){
108             return null;
109         }
110         return this.asc ? this.list.remove(0): this.list.remove(list.size()-1);
111     }
112 
113     /**
114      * 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
115      * @return
116      */
117     @Override
118     public T remove() {
119         if (isEmpty()){
120             throw new NoSuchElementException("The PriorityQueue is empty");
121         }
122         return poll();
123     }
124 
125     @Override
126     public void clearQueue() {
127         this.list.clear();
128     }
129 
130     //测试
131     public static void main(String[] args){
132         PriorityQueue<Process> priorityQueue=new PriorityQueue<>(false);
133 
134         System.out.println("初始化队列");
135         priorityQueue.add(new Process("进程1",10));
136         priorityQueue.add(new Process("进程2",1));
137         priorityQueue.add(new Process("进程3",8));
138         priorityQueue.add(new Process("进程4",3));
139         priorityQueue.add(new Process("进程5"));
140         System.out.println("队列中的进程执行优先级:");
141         while (!priorityQueue.isEmpty()){
142             System.out.println("process:"+priorityQueue.poll().toString());
143         }
144 
145     }
146 
147 }

 

目录
相关文章
|
8天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
8天前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
3天前
|
存储 安全 Java
Java 数据结构类型总结
在 Java 中,常用的数据结构包括基础数据结构(如数组和字符串)、集合框架(如 Set、List 和 Map 接口的多种实现)、特殊数据结构(如栈、队列和双端队列)、链表(单链表、双链表和循环链表)以及图和树等。这些数据结构各有特点和适用场景,选择时需考虑性能、内存和操作需求。集合框架提供了丰富的接口和类,便于处理对象集合。
|
6天前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
8天前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
2月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
41 2
|
2月前
|
安全 算法 Java
java系列之~~网络通信安全 非对称加密算法的介绍说明
这篇文章介绍了非对称加密算法,包括其定义、加密解密过程、数字签名功能,以及与对称加密算法的比较,并解释了非对称加密在网络安全中的应用,特别是在公钥基础设施和信任网络中的重要性。
|
2月前
|
存储 算法 Java
"解锁Java对象数据结构的奥秘:从基础到实战,与热点技术共舞,让你的编程之路更激情四溢!"
【8月更文挑战第21天】Java以对象为核心,它是程序的基本单元与数据处理的基础。对象源自类,拥有属性(字段)和方法。对象在内存中分为对象头(含哈希码、GC信息等)和实例数据区(存储属性值)。例如,`Student`类定义了姓名、年龄等属性及相应的方法。通过`new`关键字实例化对象并调用其方法进行数据操作,是Java编程的关键技能。
29 0
|
2月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
25 0
|
5天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
下一篇
无影云桌面