2005年2月15日

JDK1.4でキュー(Queue)を実装してみる。

JDK1.5からデータ構造のキュー(Queue)が標準APIとして定義されている。JDK1.4まではスタック(Stack)などが標準APIとして存在するがキューは実装されていないのでJDK1.5のキューを元に実装してみる。

org.oklab.util.Queueクラスの実装。

/*
 * 2005 Copyright satoshiokita All Right Reserved.
 */
package org.oklab.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.NoSuchElementException;

/**
 * Queue Data Structure under Java 1.4.
 *
 * The Queue interface exist Java Collections Framework in Java 1.5.
 * I implemented this reference Java 1.5.
 *
 * @author satoshiokita
 */
public class Queue extends ArrayList {

	private ArrayList queue = null;

	public Queue () {
		queue = new ArrayList();
	}

	/**
	 * create empty list of initial capacity size by argument specify.
	 * @param initialCapacity
	 */
	public Queue(int initialCapacity) {
		queue = new ArrayList(initialCapacity);
	}

	/**
	 * create list of elements Collection by argument specify.
	 * @param collection.
	 */
	public Queue(Collection c) {
		super(c);
	}

	/**
	* get header object in queue, but delete objects in queue.
	* if quere is empty, throw NoSuchElementException so differ poll
	* method.
	*
	* @throws NoSuchElementException
	* @return header object in quere.
	*/
	public Object element() throws NoSuchElementException {
		if ( queue.isEmpty() ) {
			throw new NoSuchElementException();
		}
	
		return (Object) queue.get(0);
	}

	/**
	* this methods insert target element to this quere possibility.
	*
	* @param Object o target element.
	* @return true when successfully. other return false.
	*/
	public boolean offer(Object o) {
		return queue.add(o);
	}

	/**
	* get header object in queue, but delete objects in queue.
	*
	* @return header object in quere.
	*/
	public Object peek() {
		if ( queue.isEmpty() ) {
			return null;
		}
	
		return (Object) queue.get(0);
	}

	/**
	* get header object in queue, ant delete objects in queue.
	*
	* @return header object in quere. if queue is empty,, return null;
	*/
	public Object poll() {
		if ( queue.isEmpty() ) {
		return null;
		}
	
		Object tmp = (Object) queue.get(0);
		queue.remove(0);
		return tmp;
	}

	/**
	* get header object in queue, ant delete objects in queue.
	* if quere is empty, throw NoSuchElementException so differ poll
	* method.
	*
	* @throws NoSuchElementException
	* @return header object in quere.
	*/
	public Object remove() throws NoSuchElementException {
		if ( queue.isEmpty() ) {
		throw new NoSuchElementException();
		}
	
		Object tmp = (Object) queue.get(0);
		queue.remove(0);
		return tmp;
	}
	
	public int size() {
		return queue.size();
	}
}

テストソースコードorg.oklab.util.TestQueueクラスの実装

/*
 * 2005 Copyright satoshiokita All Right Reserved.
 */
package org.oklab.util;

import java.util.Date;

/**
 * Queue Data Structure test under Java 1.4.
 *
 * @author satoshiokita
 */
public class TestQueue {

	public static void main(String[] args) {
		Queue queue = new Queue();
		String hello = "Hello";
		String world = "World";
		Date   date  = new Date();
		
		queue.offer(hello);
		queue.offer(date);
		queue.offer(world);
		
		System.out.println(queue.size());
		int size = queue.size();
		for ( int i = 0; i < size; i++ ) {
			System.out.println(queue.poll());
		}
	}
}

テスト結果

3
Hello
Tue Feb 15 21:58:30 JST 2005
World