数据结构与算法-队列(未完)

Posted on | Edited on | In ,

队列的作用和实际使用场景

循环队列

特点：

  • 没有数组队列在扩容时候O(n)的数据迁移工作
  • 当(tail+1)%n=head时候队列满,当head==tail的时候队列空
  • 因为是环状，所以被enqueue一个元素，tail=(tail+1)%n,每dequeue一个元素，head=(head+1)%n
  • 缺点：tail不能存数据
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
public class CircleQueuqe {
    private String[] array;
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public CircleQueuqe(int size) {
        this.size = size;
        array = new String[size];
    }

    public void enque(String s) {
        //尾指针下一个指向head队列满
        if ((tail + 1) % size == head) {
            throw new RuntimeException("CircleQueuqe has full");
        }

        array[tail] = s;
        //环状的下一个位置是 tail+1取模
        tail = (tail + 1) % size;
    }

    public String deques() {
        if(head==tail){
            throw new RuntimeException("CircleQueuqe has empty");
        }

        String ret=array[head];
        head=(head+1)%size;

        return ret;
    }

    public String[] getArray() {
        return array;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "CircleQueuqe{" +
                "array=" + Arrays.toString(array) +
                ", head=" + head +
                ", tail=" + tail +
                ", size=" + size +
                '}';
    }
}