循环队列

Posted on

基本概念

队列(Queue)两端同意操作的类型不一样：
能够进行删除的一端称为队头，这样的操作也叫出队dequeue；
能够进行插入的一端称为队尾，这样的操作也叫入队enqueue。
1、添加一个属性size用来记录眼下的元素个数。
目的是当head=rear的时候。通过size=0还是size=数组长度。来区分队列为空，或者队列已满。
2、数组中仅仅存储数组大小-1个元素，保证rear转一圈之后不会和head相等。也就是队列满的时候。rear+1=head，中间刚好空一个元素。
当rear=head的时候。一定是队列空了。
解决这种问题的常见做法是这种：
使用一标记，用以区分这样的易混淆的情形。
牺牲一个元素空间。当front和rear相等时，为空。当rear的下一个位置是front时，为满。
avatar

代码实现

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
package com.hyh.datastructure;
 
 
public class CQueue {
    private int front;//指向队首
    private int rear;//指向队尾
    private int[] elem;
    private int maxSize;//最大容量
 
    public CQueue(int maxSize) {
        this.front = 0;
        this.rear = 0;
        this.elem = new int[maxSize];
        this.maxSize = maxSize;
    }
    public boolean isEmpty(){
        return rear==front;
    }
    public boolean isFull(){
        return  (rear+1)%maxSize==front;
    }
    public void offer(int val){
        if(isFull())return;
        elem[rear++]=val;
        rear=rear%maxSize;
    }
    public void poll(){
        if(isEmpty())return;
        front=++front%maxSize;
    }
    public int peek(){
        if(isEmpty())return -1;
        return elem[front];
    }
 
    @Override
    public String toString() {
        String str="";
        for (int i:elem
             ) {
            str=str+i;
        }
        return str;
    }
 
 
    public static void main(String[] args) {
        CQueue c= new CQueue(5);
        System.out.println(c.isEmpty());//true
        for (int i = 0; i < 5; i++) {
            c.offer(i);
        }
        System.out.println(c.isFull());//true
        System.out.println(c.toString());//01230   因为实际容量是maxSize-1 所以只存了前4次的值
        c.poll();
        c.offer(4);
        System.out.println(c.toString());//01234
        c.poll();
        c.offer(5);
        System.out.println(c.toString());//51234
    }
}

参考文章

https://www.jb51.net/article/130855.htm