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

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

/**
 * The stack of link.And it supports push,pop,contain methods.
 * With the link, we don't have to care the flow.
 * @author wpc
 * @version 0.0.1
 * @param <T> the type of the object will be pushed
 */
public class StackLink<T> {
	private StackLinkElement<T> top;
	private boolean allowNull = true;

	public StackLink() {
		top = null;
	}

	public synchronized  boolean isEmpty() {
		return top == null;
	}

	public synchronized  T pop() {
		if (!isEmpty()) {
			T t = top.getObject();
			top = top.getPrev();
			return t;
		} else {
			//System.err.println("The stack is empty!");
			return null;
		}
	}

	public  synchronized T getTop() {
		if(!isEmpty()){
			return top.getObject();
		}else{
			//System.err.println("The stack is empty!");
			return null;
		}
	}

	public  synchronized boolean push(T o) {
		if(!allowNull){
			if(o==null){
				return false;
			}
		}
		try {
			StackLinkElement<T> e = new StackLinkElement<T>(o, top);
			top = e;
			return true;
		} catch (Exception e) {
			//System.out.println("Push data to stack error!");
			return false;
		}
	}

	public synchronized boolean contains(T o){
		boolean f  = false;
		StackLinkElement<T> e = top;
		while(e!=null){
			if(e.getObject().equals(o)){
				f = true;
				break;
			}
			e = e.getPrev();
		}
		return f;
	}
	
	/**
	 * Print every object in the stack [under-stack ...... top-stack]
	 */
	public String toString(){
		String s = "]";
		StackLinkElement<T> e = top;
		while( (e!=null)&&(e.getPrev()!=null)){
			s=","+e.getObject()+s;
			e = e.getPrev();
		}
		if(e!=null){
			s=e.getObject()+s;
		}
		s="["+s;
		return s;
	}
	
	public boolean clear(){
		top = null;
		return true;
	}

	public boolean isAllowNull() {
		return allowNull;
	}

	public void setAllowNull(boolean allowNull) {
		this.allowNull = allowNull;
	}
}