队列【Java】

什么是队列

队列是一种数据结构，具有先进先出的特点；
队列只允许在队头处出队列，在队尾处进队列；

模拟实现一个队列

模拟实现队列可以使用链表或者顺序表来实现，使用链表又可以使用单链表和双向链表来实现，这里我们使用单链表来实现：

public class test {
    //设置结点
   class Node {
       private int val;
       private Node next;
       private  Node(int val){
           this.val=val;
       }
   }

   //设置链表的头结点和尾结点
   private Node head;
   private Node last;
   //链表的长度
   int UsedSize;

    //入队
   public boolean offer(int val){

       Node node=new Node(val);

       //当前链表为空时
       if(head==null){
           head=node;
           last=node;
           return true;
       }else{
           last.next=node;      //从队尾入，让链表的为结点指向新的结点
           last=last.next;      //更新尾结点
           UsedSize++;          //长度加一
           return true;
       }

   }

   //出队
    public int poll(){

       if(empty()){
           System.out.println("队列为空");
           return -1;
       }else{
           int val=head.val;        //从队头出，记录当前的头结点的值
           head=head.next;          //更新头结点
           UsedSize--;              //长度减一
           return val;
       }


    }

    public int peek(){

        if(empty()){
            System.out.println("队列为空");
            return -1;
        }else{
            int val=head.val;
            return val;
        }

    }

    public boolean empty(){
       return UsedSize==0;
    }

    public int getUsedSize(){
       return UsedSize;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

队列的使用

java为队列的使用提供了一些方法：

一般比较常用的是上面标红的三个：

  public static void main(String[] args) {


        Queue<Integer> queue=new LinkedList<>();

        //入队
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        //出队

        queue.poll();   // 1

        //查看队头元素
        queue.peek();   // 2
        
        //队列长度，队列元素个数
        queue.size();   // 4
        
        //队列是否为空
        queue.isEmpty();    //false
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

  public static void main(String[] args) {
        
        Queue<Integer> queue=new LinkedList<>();

        //入队
        queue.add(5);
        queue.add(4);
        queue.add(3);
        queue.add(2);
        queue.add(1);

        //出队

        Integer t=queue.remove();
        System.out.println(t);        // 5
        //查看队头元素
        Integer m=queue.element();
        System.out.println(m);          // 4

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这样2组方法实际实现的效果大同小异，但还是有一些细微的差别：

• add()与offer():当在一个有容量限制的队列插入元素时，如果队列已满，使用add()就会直接抛出异常；
• remove()与poll():当队列为空时，使用第一种方法会抛出异常；而poll()方法是返回一个null;
• element()与peek():当队列为空时，使用第一种方法会抛出异常；而poll()方法是返回一个null;

循环队列

什么是循环队列

队列的首尾相接的顺序存储结构称为循环队列；

类似就是这样一个结构，front代表队头，rear代表队尾；

由于循环队列首尾相接的特殊性，我们必须考虑到这种队列空和满的情况，不难发现，当front=rear时表示队列为空，但是当队列满时，似乎也是满足这样的条件，因此我们使用一些方法重新来判断队列是空还是满：

• 借助队列的长度，当rear移动的步数与队列的长度相等时，自然就表示队列已满；
• 设置一个标志位flag:当frontrear并且flagtrue时表示队列为空；当frontrear并且flagfalse时表示队列为满；
• 在队列中设置一个空闲位置：当队列空时，front==rear；当队列只剩一个空闲时，队列满；

模拟实现循环队列

public class CircularQueue {
    int [] elem;
    private int front;  //队头元素的下标
    private int rear;   //队尾元素的下标

    //key 数组大小
    public CircularQueue(int key){
       this.elem=new int[key];
    }

    //入队
    public boolean enQueue(int val){
        //判断队列是否满
        if(isFull()){
            return false;
        }
        //将元素放到rear下标处
        this.elem[rear]=val;
        rear=(rear+1)%elem.length;
        return true;
    }

    //出队
    public boolean deQueue(){
        if (empty()){
            return false;
        }else{
            front=(front+1)%elem.length;
            return  true;
        }
    }

    //查看队头元素
    public int Front(){
        if (empty()){
            return -1;
        }else{

            return  elem[front];
        }
    }
    
    //是否队满
    public boolean isFull(){
        if((rear+1)%elem.length==front){
            return true;
        }
        return false;
    }


    //是否队空
    public boolean empty(){
        if (front==rear){
            return true;
        }
        return false;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

over !