算法时空第23、24讲 数据结构复习

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
73
74
75
76
77
public class Test {
    public static void  main(String[] args) {
        MyQueue myQueue = new MyQueue(5);

        myQueue.isEmpty();     //为空
        myQueue.add(5); 
        myQueue.add(7); 
        myQueue.add(5);    
        myQueue.add(4);
        myQueue.add(3);

        myQueue.isFull();   //已满

        myQueue.each(); //[4, 3, 0, 5, 7, 5]
    }
}
class MyQueue{
    int [] queue;
    int head;
    int foot;
    public MyQueue(int lenght) {
        queue = new int[lenght+1];  //通过牺牲一个空间来换取循环的可能，所以若new 一个 n 个长度的队列，那么我们应该使用 n+1 长度，因为有一个是被牺牲的
        head = 3;
        foot = 3;
    }

    //添加元素
    public void add(int num){
        //先判断是否满
        if (isFull()){
            System.out.println("满了，不能在加了");
            return;
        }
        //超过队列长度，返回队头
        if( foot == queue.length)
            foot = 0;
        queue[foot++] = num;
    }

    //弹出元素
    public void pop(){
        if (isEmpty())
            return;
        foot--;

        if (foot == 0)
            foot = queue.length-1;
    }

    //判断是否已满
    //当head 不是0时，判断head是否在foot前面即可
    //当head为0时，需要考虑到 foot 在序列尾的情况，应加一在比较
    public boolean isFull(){
        //if ((foot + 1) % queue.length == head)    另外一种判断方法    鸽笼定理
        if( head == (foot+1 == queue.length ? 0 : foot+1 ) ){
            System.out.println("已满");
            return true;
        }else{
            System.out.println("还未满");
            return false;
        }
    }

    //是否为空
    public boolean isEmpty(){
        if (head == foot){
            System.out.println("为空");
            return true;
        }
        return false;
    }

    //输出所有元素
    public void each(){
        System.out.println(Arrays.toString(queue));
    }
}