论坛首页 综合技术论坛

队列Queue

浏览 4489 次
锁定老帖子 主题:队列Queue
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-11-17   最后修改:2010-06-03
package queue;

/**
 * 队列接口
 * @author jzj
 *
 * @param <E>
 */
public interface Queue<E> {
	//入队
	public void enqueue(E e);

	//出队
	public E dequeue();

	//取队列第一个
	public E front();

	//队列是否为空
	public boolean isEmpty();

	//队列大小
	public int size();
}

 

package queue;

/**
 * 循环队列,使用数组实现
 * @author jzj
 */
public class ArrayQueue<E> implements Queue<E> {

	private Object lock = new Object();

	// 队列大小
	private int size = 1000;

	// 队列
	private E[] arrStr = (E[]) new Object[size];

	// 队列指针
	private int head = 0;

	// 队列尾指针
	private int tail = 0;

	/**
	 * 入队
	 * @param o
	 */
	public void enqueue(E o) {
		synchronized (lock) {

			// 如果队列已满
			while ((tail + 1) % size == head) {
				try {
					System.out.println("队列已满," + Thread.currentThread().getName()
							+ " 线程阻塞...");
					// 队列满时线程阻塞
					lock.wait();//注,这里一定要放在while条件里,因为获取锁后,条件不一定还成立
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
			// 如果队列未满
			arrStr[tail] = o;
			// 指针下移
			tail = (tail + 1) % size;
			// 入队后通知消费线程
			lock.notifyAll();
		}
	}

	/**
	 * 出队
	 * @return
	 */
	public E dequeue() {
		synchronized (lock) {
			// 如果队列为空
			while (head == tail) {
				try {
					System.out.println("队列为空," + Thread.currentThread().getName()
							+ " 线程阻塞...");
					// 队列空时线程阻塞
					lock.wait();//注,这里一定要放在while条件里,因为获取锁后,条件不一定还成立
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
			// 队列非空
			E tempStr = arrStr[head];

			arrStr[head] = null;//注,这里出队后释放对象,加快回收,不然大的对象可能造内存泄露
			head = (head + 1) % size;

			// 出队后通知生产者
			lock.notifyAll();
			return tempStr;

		}
	}

	//取队列第一个
	public E front() {
		synchronized (lock) {
			// 如果队列为空
			while (head == tail) {
				try {
					System.out.println("队列为空," + Thread.currentThread().getName()
							+ " 线程阻塞...");
					// 队列空时线程阻塞
					lock.wait();//注,这里一定要放在while条件里,因为获取锁后,条件不一定还成立
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
			// 队列非空
			return arrStr[head];
		}
	}

	//队列是否为空
	public boolean isEmpty() {
		return head == tail;
	}

	//队列大小
	public int size() {

		return Math.abs(tail - head);
	}
}

 

使用1.5中并发新特性实现循环队列:来源于 API java.util.concurrent.locks.Condition

//循环缓冲队列,从队首放,从队尾出。牺牲数组的最后一个元素,用来判断队列是否满
class BoundedBuffer {
	final Lock lock = new ReentrantLock();//可重入锁
	final Condition notFull = lock.newCondition();//缓冲空条件对象
	final Condition notEmpty = lock.newCondition();//缓冲非空条件对象

	final Object[] items = new Object[100];//缓冲区
	int putptr/*队首*/, takeptr/*队尾*/, count/*可用个数*/;

	//将元素放入缓冲,供生产线程调用
	public void put(Object x) throws InterruptedException {
		lock.lock();//获取锁
		try {
			//注,要将await置于循环中,这也wait道理一样
			while (count == items.length)
				notFull.await();//缓冲满时等待,且释放锁
			items[putptr] = x;
			//如果队首指针指向数组最后索引时,重新指向数组第一个元素位置
			if (++putptr == items.length)
				putptr = 0;
			++count;//循环队列中存入的元素个数
			notEmpty.signal();//放入元素后通知其它消费线程可以消费了
		} finally {
			lock.unlock();//释放锁
		}
	}

	//从缓冲取出元素,供消费线程调用
	public Object take() throws InterruptedException {
		lock.lock();
		try {
			while (count == 0)
				notEmpty.await();//如果缓冲空则等待
			Object x = items[takeptr];
			//如果队尾指针指向数组最后索引时,重新指向数组第一个元素位置
			if (++takeptr == items.length)
				takeptr = 0;
			--count;
			notFull.signal();//取出后会有空间,通知生产线程
			return x;
		} finally {
			lock.unlock();
		}
	}
}

 

 

package queue;

import java.util.LinkedList;

/**
 * 使用 LinkedList 实现队列
 * @author jzj
 *
 * @param <E>
 */
public class LinkedListQueue<E> implements Queue<E> {
	private LinkedList<E> linkedList = new LinkedList<E>();

	//入队
	public void enqueue(E e) {
		linkedList.addLast(e);
	}

	//出队
	public E dequeue() {
		return linkedList.removeFirst();
	}

	//取队列第一个
	public E front() {
		return linkedList.getFirst();
	}

	//队列是否为空
	public boolean isEmpty() {
		return linkedList.isEmpty();
	}

	//队列大小
	public int size() {
		return linkedList.size();
	}
}

 

package queue;

import java.util.NoSuchElementException;

/**
 * 使用 循环双向链 实现队列
 * 
 * @author jzj
 *
 * @param <E>
 */
public class LinkedQueue<E> implements Queue<E> {
	private class Entry {
		E element;//数据域
		Entry next;//后驱节点
		Entry previous;//前驱节点

		/**
		 * @param element 数据域
		 * @param next 后驱节点
		 * @param previous 前驱节点
		 */
		Entry(E element, Entry next, Entry previous) {
			this.element = element;
			this.next = next;
			this.previous = previous;
		}
	}

	/*
	 * 头节点,永远代表头。链中无结节时节点中的前后驱指针域指向自己,当有元素时
	 * 头节点的前驱指针域previous指向链中最后一个节点,而next指针域指向链中的
	 * 第一个节点
	 */
	private Entry header = new Entry(null, null, null);

	private int size = 0;//链表中节点个数,但不包括头节点header

	public LinkedQueue() {
		//初始化时头的前后驱指针都指向自己
		header.next = header.previous = header;
	}

	//入队,在链表中的最后位置加入元素,相当于 LinkedList 的add、addBefore、addLast方法实现
	public void enqueue(E e) {
		//在双向链后面加入元素
		Entry newEntry = new Entry(e, header, header.previous);
		//让新元素的前驱节点(新增前链的最后点)的前驱指向新加元素
		newEntry.previous.next = newEntry;
		//让新元素的后驱节点(header头节点)的前驱指向新加元素
		newEntry.next.previous = newEntry;
		size++;
	}

	//出队,从链表中的第一个元素开始出队,相当于 LinkedList 的removeFirst方法实现
	public E dequeue() {
		//要出队(删除)的节点的数据域
		E first = header.next.element;
		Entry e = header.next;
		//要删除的节点为头节点时不能删除
		if (e == header) {
			throw new NoSuchElementException();
		}

		//将删除节点的前驱节点的next域指针指向删除节点的后驱节点
		e.previous.next = e.next;
		//将删除节点的后驱节点的previous域指针指向删除节点的前驱节点
		e.next.previous = e.previous;
		size--;
		return first;
	}

	//取队列的第一个元素,相当于 LinkedList 的getFirst方法实现
	public E front() {
		if (size == 0)
			throw new NoSuchElementException();

		return header.next.element;
	}

	//队列是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	//队列大小
	public int size() {
		return size;
	}
}

 

 

论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics