queue.java

6个经典数据结构JAVA解法

/**
 * 循环队列
 * 为避免队列不满却不能插入新数据项的问题，让队头队尾指针绕回到数组开始的位置。
 * 队列中插入数据项和移除数据项的时间复杂度均为O(1)。
*/
class Queue {    
    private int maxSize; //size of queue array
    private long[] queArray;
    private int front;//the front pointer 
    private int rear;//the back pointer
    private int nItems;// number of contains
    /**
     * 构建器（初始化队列的参数）
     * @param int s
     */
    public Queue(int s) { // constructor
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
    /**
     * 进入队列
     * @param long j
     */
    public void insert(long j) { // put item at rear of queue
        if (rear == maxSize-1) { // deal with wraparound
            rear = -1;
        }
        queArray[++rear] = j; // increment rear and insert
        nItems++; // one more item
    }
    /**
     * 离开队列
     */
    public long remove() { // take item from front of queue
        long temp = queArray[front++]; // get value and incr front
        if (front == maxSize) {
            front = 0;
        }
        nItems--; // one less item
        return temp;
    }
    /**
     * 前端数据
     */
    public long peekFront() { // peek at front of queue
        return queArray[front];
    }
    /**
     * 是否为空
     */
    public boolean isEmpty() { // true if queue is empty
        return (nItems == 0);
    }
    /**
     * 是否满
     */
    public boolean ifFull() { // true if queue is full
        return (nItems == maxSize);
    }
    /**
     * 当前容量
     */
    public int size() { // number of items in queue
        return nItems;
    }
    /**
     * 主函数，测试。
     * @param String[] args
     */
    
    public static void main(String[] args) {
        Queue theQueue = new Queue(5); // queue holds 5 items
        theQueue.insert(10); // insert 4 items
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);
        theQueue.remove(); // remove 3 items
        theQueue.remove();
        theQueue.remove();
        theQueue.insert(50); // insert 4 more items
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);
        while (!theQueue.isEmpty()) { // remove and display all items
            long n = theQueue.remove();
            System.out.print(n);
            System.out.print(" ");
        }
        System.out.println("");
    } // end main()
} // end class Queue