java实现队列

发布时间：2020-12-15 07:31:37 所属栏目：Java 来源：网络整理

导读：队列的定义队列的特点是节点的排队次序和出队次序按入队时间先后确定，即先入队者先出队，后入队者后出队。即我们常说的FIFO(first in first out)先进先出。顺序队列定义及相关操作顺序存储结构存储的队列称为顺序队列，内部使用一个一维数组存储，用一个

队列的定义

　　队列的特点是节点的排队次序和出队次序按入队时间先后确定，即先入队者先出队，后入队者后出队。即我们常说的FIFO(first in first out)先进先出。　　　　

顺序队列定义及相关操作

　　顺序存储结构存储的队列称为顺序队列，内部使用一个一维数组存储，用一个队头指针front指向队列头部节点（即使用int类型front来表示队头元素的下标），用一个队尾指针rear，指向队列尾部元素(int类型rear来表示队尾节点的下标)。

　　初始化队列时: front = rear = -1 (非必须，也可设置初始值为0，在实现方法时具体修改)

　　队列满时： ? ? rear = maxSize-1 (其中maxSize为初始化队列时，设置的队列最大元素个数)

　　队列为空时： ?front = rear

　　下面使用java实现一个基于一维数组的顺序队列，代码如下：

 1 /**
 2  * 定义一个queue
 3  */
 4 class ArrayQueue{
 5     private int[] data ; //队列中存放的数据
 6     private int maxSize ; //队列的大小
 7     private int front ;//指向队列头部的指针
 8     private int rear ; //指向队列尾部的指针
 9 
10     public ArrayQueue(int maxSize){
11         this.maxSize = maxSize;
12         data = new int[maxSize];
13         front = -1;
14         rear = -1;
15     }
16 
17     /**
18      * 判断队列是否已满
19      * @return
20      */
21     public boolean isFull(){
22         return rear == maxSize -1 ;
23     }
24 
25     /**
26      * 判断队列是否为空
27      * @return
28      */
29     public boolean isEmpty(){
30         return rear == front;
31     }
32 
33     /**
34      * 添加数据到队列
35      * @param n
36      */
37     public void add(int n){
38         if(isFull()){
39             System.out.println("队列已满，不能添加");
40             return;
41         }
42         data[++rear] = n;
43     }
44 
45     /**
46      * 显示头部数据
47      * @return
48      */
49     public void head(){
50         if(isEmpty()){          
   　　　　　　throw new RuntimeException("队列为空");
53         }
54         System.out.println(data[front+1]);
55     }
56 
57     /**
58      * 取出头部数据
59      * @return
60      */
61     public int pop(){
62         if(isEmpty()){
64             throw new RuntimeException("队列为空");
65         }
66         int a = data[++front];
67         data[front] = 0;
68         return a;
69     }
70 
71     /**
72      * 打印全部数据
73      */
74     public void print(){
75         if(isEmpty()){
76             System.out.println("队列为空");
77             return;
78         }
79         for(int i=0;i<data.length;i++){
80             System.out.printf("array["+i+"]=%dn",data[i]);
81         }
82     }
83 }

　　简单描述顺序队列的入队(add方法)：

 1 public static void main(String []args) {
 2         //1.声明一个可以存储6个元素的顺序队列，默认值为0,front 和rear指针为-1
 3         ArrayQueue queue = new ArrayQueue(6);
 4         //2.向顺序队列中添加元素
 5         queue.add(1);
 6         queue.add(2);
 7         queue.add(3);
 8         queue.add(4);
 9         queue.add(5);
10         queue.add(6);
11         //2.1打印当前队列元素
12         queue.print();
13         //3.将顺序队列中元素取出
14         queue.pop();
15         queue.pop();
16         queue.pop();
17         queue.pop();
18         queue.pop();
19         queue.pop();
20         //4.队列中元素全部取出
21 }

　　在代码中初始化了一个大小为6的顺序队列，下图展示了第一步(即代码ArrayQueue queue = new ArrayQueue(6))中队列元素及指针情况

　　其中front和rear指向的虚线框实际并不存在，仅用来表示初始化时的默认状态，因我们实现的队列元素使用int[]存储元素，所以初始值均为0(如用Object[]或范型则初始值为null)

? ? ? 执行queue.add(1)方法后队列的状态如下图：

　　可以看到向队列中添加元素后，rear指针向后移动一个位置指向第一个元素位置，后面继续添加后面5个元素后队列如下图所示

　　接下来看下队列的出队情况?

　　当第一次执行queue.pop()方法后，队列元素如上图所示，此时队列剩下5个元素

　　当第六次执行queue.pop()方法后，队列元素如下图所示

　　此时队列中元素已全部出队，按正常逻辑应该可以添加元素到队列中，但此时添加元素却会报队列已满错误（rear=maxSize-1)，当然即使前面元素未出队也会报相同错误。这就是我们常说的“假溢出”问题。为解决这个问题，就引出了我们的环形队列。

环形队列

　　环形队列，顾名思义即让普通队列首尾相连，形成一个环形。当rear指向尾元素后，当队列有元素出队时，可以继续向队列中添加元素。

　　这里我使用的是rear指针指向最后一个节点的后一个元素，即会占用一个位置用来表示队列已满。

　　初始化队列时: front = rear = 0

　　队列满时： ? ?( rear +1 ) % maxSize == front (其中maxSize为初始化队列时，设置的队列最大元素个数)

　　这里不能使用rear = maxSize-1作为判断队满的条件，因使用环形队列方式实现，当第一次队满时，rear = maxSize -1，执行出队操作后原队头位置空出，此时继续执行入队操作，则rear向后移动一个位置，则rear = 0，而此时队列也是已满状态。所以只要rear 向前移动一个位置就等于front时，就是队满的情况。

　　队列为空时： ?front == rear

　　先看下具体代码

 1 public class CycleQueue {
 2 
 3     /**
 4      *
 5      */
 6     private int maxSize ;
 7     private int data[] ;
 8     private int front ;
 9     /**
10      * 这里rear指向最后一个数据的后面一个位置，即队列中有一个为空占位
11      */
12     private int rear ;
13 
14     public CycleQueue(int maxSize){
15         this.maxSize = maxSize;
16         data = new int[maxSize];
17         front = 0;
18         rear = 0;
19     }
20 
21     /**
22      * 判断队列是否已满
23      * 因是循环队列，所以rear值可能小于front，所以不能使用rear == maxSize -1来判断
24      * @return
25      */
26     public boolean isFull(){
27         return (rear + 1) % maxSize == front;
28     }
29 
30     public boolean isEmpty(){
31         return rear == front;
32     }
33 
34     public void add(int n){
35         if(isFull()){
36             System.out.println("队列已满，不能添加");
37             return;
38         }
39         data[rear] = n;
40         rear = (rear + 1) % maxSize;
41     }
42 
43     public void head(){
44         if(isEmpty()){
45             throw new RuntimeException("队列为空");
46         }
47         System.out.println("head="+data[front]);
48     }
49 
50     public int pop(){
51         if(isEmpty()){
52             throw new RuntimeException("队列为空");
53         }
54         int value = data[front];
55         front = (front + 1) % maxSize;
56         return value;
57     }
58 
59     public void print(){
60         if(isEmpty()){
61             System.out.println("队列为空");
62             return;
63         }
64         for(int i= front; i<front+size(); i++){
65             System.out.printf("array"+(i%maxSize)+"=%d",data[i%maxSize]);
66         }
67     }
68 
69     /**
70      * 因是循环队列，所以会出现rear<front情况，这里需要+maxSize
71      * @return
72      */
73     public int size(){
74         return (rear - front + maxSize)%maxSize;
75     }
76 }

　　下面再以图解的方式讲解一下环形队列的入队出队以及队满情况。当执行初始化代码后

1 CycleQueue queue = new CycleQueue(6);　　?

　　此时front = rear = 0，队列为空。当第一次执行queue.add(1)后，环形队列元素如下图所示

　　当依次执行queue.add(2);queue.add(3);queue.add(4);queue.add(5);后，达到(rear+1)%maxSize=front （即rear=5）条件，队列已满不能添加新元素。此时环形队列元素情况如下图

　　所以这种情况会浪费一个空间来作为判满的条件。

　　下面执行出队操作，当第一次执行出队操作queue.pop()方法后，环形队列元素情况如下图所示

　　　此时 (rear+1)%maxSize = 0 ?不等于 front=1,所以可以继续向队列中添加元素，也就不会出现假溢出的情况。当执行入队(例queue.add(6))操作后，rear = (rear+1)%maxSize 即rear=0，以此来生成环形队列。此时队列元素情况如下图所示

　　另外，再说明下环形队列有效元素个数问题，如果不是环形队列，则有效元素个数size = rear - front。而使用环形实现后，会出现rear<front的情况，所以这里使用(rear-front+maxSize)%maxSize的方式计算有效元素个数。（或者在内部定义一个size属性，当元素入队时size++，当出队时size--）

　　因此在打印队列中元素时，从front位置开始至 front+size位置结束来循环打印有效元素。

总结

　　如果不实用环形队列方式实现队列，则会出现“假溢出”情况（即队列满后，将全部元素出队却不能继续添加元素的情况）。而环形队列会在队头元素出队后，将队尾指针rear重新分配为0，以达到循环使用队列空间的目的。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!