queuelink.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 84 行

/*
 * 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.
 */
//30 Nov 2007
package cn.edu.whu.iss.algorithm.unit10;

import cn.edu.whu.iss.algorithm.unit10.datastruct.QueueLinkElement;

public class QueueLink<T> {
	private QueueLinkElement<T> head,tail;
	private int tot;
	
	public QueueLink(){
		head = null;
		tail = head;
		tot = 0;
	}
	
	public synchronized boolean isEmpty(){
		return (tot==0);
	}
	
	public synchronized T enqueue(T x) {
		tot++;
		QueueLinkElement<T> e = new QueueLinkElement<T>(x,null,head);
		if(head!=null){
			head.setPrev(e);
		}
		head = e;
		if(tail==null){
			tail = head;
		}
		return x;
	}
	
	public synchronized T dequeue(){
		T e = null;
		if(!isEmpty()){
			e = tail.getObject();
			tail = tail.getPrev();
			if(tail!=null){
				tail.setNext(null);
			}
		}
		tot--;
		if(isEmpty()){
			head=null;
			tail = head;
		}
		return e;
	}
	
	/**
	 * Print every object in the queue [head ...... tail ]
	 */
	public String toString(){
		 String s ="[";
		 QueueLinkElement<T> e = head;
		 while((e!=null)&&(e.getNext()!=null)){
			 s+=e.getObject()+",";
			 e = e.getNext();
		 }
		 if(e!=null){
			 s+=e.getObject();
		 }
		 s+="]";
		 return s;
	}
}