浏览 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; } }
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |