queue.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//24 Nov 2007
package cn.edu.whu.iss.algorithm.unit10;

/**
 * Data struct ,The static queue
 * @author wpc
 * @version 0.0.1
 * @param <T> the data type 
 */
public class Queue<T> {
	private Object[] q;
	private int head,tail;
	
	/**
	 * Construct a queue with the memory n
	 * @param n the queue's size
	 */
	public Queue(int n){
		q = new Object[n+1];
		head = 0;
		tail = 0;
	}
	
	/**
	 * Check the queue is full
	 * @return true full.
	 */
	public synchronized boolean isFull(){
		if(tail == q.length-1){
			return (0==head);
		}else{
			return (tail+1==head);
		}
	}
	
	/**
	 * Check the queue is empty
	 * @return true empty
	 */
	public synchronized boolean isEmpty(){
		return (tail==head);
	}
	
	/**
	 * Enqueue a object T to the queue
	 * @param x object
	 * @return x
	 */
	public synchronized T enqueue(T x) {
		T t = x;
		if(!isFull()){
			q[tail] = x;
			if(tail==q.length-1){
				tail = 0;
			}else{
				tail++;
			}
		}
		
		return t;
		
	}
	
	/**
	 * Dequeue a object from the queue
	 * @return a object
	 */
	public synchronized T dequeue(){
		T t = null;
		if(!isEmpty()){
			t = (T)q[head];
			if(head==q.length-1){
				head = 0;
			}else{
				head++;
			}
		}
		return t;
	}

	/**
	 * Print every object in the queue [head ...... tail ]
	 */
	public String toString(){
		if(isEmpty()){
			return "[]";
		}
		String t = "[";
		int i=head;
		int p = (tail-1>=0)?tail-1:q.length-1; 
		while(i!=p){
			t+=q[i]+",";
			if(i==q.length-1){
				i=0;
			}else{
				i++;
			}
		}
		t+=q[p]+"]";
		return t;
	}
	
}