日撸 Java 三百行： DAY18 循环队列

0.主题

今天实现循环队列。

1.循环队列

队列除了有链式实习，还有顺序实现，但对于普通的顺序实现的队列可能会发生假溢出。这是因为head与tail只增不减，致使被删除元素的空间永远无法重新利用所致。循环队列通过做模运算将顺序队列转成了逻辑上的环形空间解决了这个问题。
循环队列对队空，队满的判断如下：

1. 队空： head == tail
2. 队满： ( tail + 1 ) % TOTAL_SPACE == head

其中head指向队头结点的位置，tail指向队尾结点后一个位置。由于要区分队空、队满这两种状态，因此需要牺牲一个结点的容量。

2.程序

1.实例域
循环队列由一个数组，以及指示队头队尾的变量head与tail构成。

	/**
	 * The total space. One space can never be used.
	 */
	public static final int TOTAL_SPACE = 10;
	
	/**
	 * The data.
	 */
	int[ ] data;
	
	/**
	 * The index for calculating the head. The actual head is head % TOTAL_SPACE.
	 */
	int head;
	
	/**
	 * The index for calculating the tail.
	 */
	int tail;

2.构造器
构造器用于生成一个空的队列。

	/**
	 ********************
	 * The constructor
	 ********************
	 */
	public CircleIntQueue( ) {
		data = new int[ TOTAL_SPACE ];
		head = 0;
		tail = 0;
	} // Of the first constructor

3.enqueue
enqueue入队一个结点，入队前需要先判断是否队满。

	/**
	 ********************
	 * Enqueue.
	 * 
	 * @param paraValue The value of the new node.
	 ********************
	 */
	public void enqueue( int paraValue ) {
		if( ( tail + 1 ) % TOTAL_SPACE == head ) {
			System.out.println("Queue full.");
			return;
		} // Of if
		
		data[ tail % TOTAL_SPACE ] = paraValue;
		tail++;
	} // Of enqueue

时间复杂度： O ( 1 ) O(1) O(1)

4.dequeue
dequeue出队一个结点，出队前需要先判断是否队空。

	/**
	 ********************
	 * Dequeue.
	 * 
	 * @return The value at the head.
	 ********************
	 */
	public int dequeue( ) {
		if( head == tail ) {
			System.out.println("No element in the queue");
			return -1;
		} // Of if
		
		int resultValue = data[ head % TOTAL_SPACE ];
		
		head++;
		
		return resultValue;
	} // Of dequeue

时间复杂度： O ( 1 ) O(1) O(1)

5.toString

	/**
	 ********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 ********************
	 */
	public String toString( ) {
		String resultString = "";
		
		if( head == tail ) {
			return "empty";
		} // Of if
		
		for( int i = head; i < tail - 1; i++ ) {
			resultString += data[ i % TOTAL_SPACE ] + ", ";
		} // Of for i
		
		resultString += data[ ( tail - 1 ) % TOTAL_SPACE ];
		return resultString;
	} // Of toString

时间复杂度： O ( n ) O(n) O(n)

6.测试
测试代码如下：

	/**
	 ********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 ********************
	 */
	public static void main( String args[ ] ) {
		CircleIntQueue tempQueue = new CircleIntQueue( );
		System.out.println("Initialized, the list is: " + tempQueue.toString());
		
		for( int i = 0; i < 5; i++ ) {
			tempQueue.enqueue( i + 1 );
		} // Of for i
		System.out.println("Enqueue, the queue is: " + tempQueue.toString());
		
		int tempValue = tempQueue.dequeue( );
		System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());
		
		for( int i = 0; i < 6; i++ ) {
			tempQueue.enqueue( i + 10 );
			System.out.println("Enqueue, the queue is: " + tempQueue.toString());
		} // Of for i
		
		for( int i = 0; i < 3; i++ ) {
			tempValue = tempQueue.dequeue( );
			System.out.println("Dequeue " + tempValue + ", the queue is: " + tempQueue.toString());
		} // Of for i
		
		for( int i = 0; i < 6; i++ ) {
			tempQueue.enqueue( i + 100 );
			System.out.println("Enqueue, the queue is: " + tempQueue.toString());
		} // Of for i
	} // Of main

执行结果如下：

3.体会

1. 入队前判断是否队满，出队前判断是否队空。
2. 判断位置时，需要做取模运算，这样才能起到回绕的效果。