cynchanpin

隊列。queue，就是現(xiàn)實生活中的排隊。

1、簡單隊列：

public class Queqe {
    private int array[];
    private int front;
    private int end;
    private int number;
    private int max;
    
    private Queqe(int maxsize){
        array = new int[maxsize];
        max = maxsize;
        front = 0;
        end = 0;
        number = 0;
    }
    
    private void insert(int item){
        if(isFull()){
            System.out.println("is full,can not insert");
            return;
        }
        array[end++] = item;
        number++;
    }
    
    private int remove(){
        if(isEmpty()){
            System.out.println("is empty,can not remove");
            return -1;
        }
        number--;
        return array[front++];
    }
    
    private boolean isFull(){
        return number == max;
    }
    private boolean isEmpty(){
        return number == 0;
    }
    
    private int size(){
        return number;
    }
    
    private int peekFront(){
        return array[front];
    }
    
    public static void main(String[] args) {
        Queqe q = new Queqe(4);
        System.out.println("queqe is empty:"+q.isEmpty());
        
        q.insert(1);
        q.insert(2);
        q.insert(3);
        q.insert(4);
        q.insert(5);
        
        System.out.println(q.size());
        System.out.println("front is "+q.peekFront());
        
        while(!q.isEmpty())
            System.out.println(q.remove());
    }
}

result:
queqe is empty:true
is full,can not insert
4
front is 1
1
2
3
4

先進(jìn)的元素排在前面，那么移除的時候就是先移除隊頭，達(dá)到先進(jìn)先出的效果。·插入和移除并不用移動整個數(shù)組，僅僅需改變隊頭和隊列的指向，所以時間復(fù)雜度和棧一樣都是O(1)。

2、不用number之后的方法改變

前面用了number統(tǒng)計隊列中元素個數(shù)，事實上不用這個變量。單靠隊頭和隊尾也是能夠?qū)崿F(xiàn)隊列。

    private boolean isFull(){
        return end == max;
    }
    private boolean isEmpty(){
        return (front ==0&&end ==0)||front == max;
    }
    
    private int size(){
        return end -front;
    }

而推斷是不是滿了更簡單，隊尾移到數(shù)組尾部即是滿了。

空的話會復(fù)雜一些，一種是一開始front為零，可是有元素插入，此時end不為零。假設(shè)兩者為零那就是空了。還有就是不停remove之后，front移到最后，證明之前的元素所有remove掉了，此時也為空。

作者依據(jù)的是front和end的變化。然后再insert和remove中直接改變front和end的值，在isEmpty和isFull中，比如在isFull()中：

    private boolean isFull(){
        return end+2 == front||(front+max-2==end);
    }

private void insert(int item){
    if(isFull()){
        System.out.println("is full,can not insert");
        return;
    }
    if(end == 0){
        array[end++] = item;
    }else{
        int i;
        for ( i = number-1; i >=0; i--) {
            if(item > array[i]){
                array[i+1] = array[i];
            }
        }
        array[i+1]= item;
        end++;
    }
    number++;
}

result：
queqe is empty:true
size:0
is full,can not insert
queqe is empty:false
size:4
front is 4
4
3
2
1 

頂

0

踩

1