1 package queue; 2 3 /** 4 * 队列接口 5 * @author jzj 6 * 7 * @param8 */ 9 public interface Queue {10 //入队11 public void enqueue(E e);12 13 //出队14 public E dequeue();15 16 //取队列第一个17 public E front();18 19 //队列是否为空20 public boolean isEmpty();21 22 //队列大小23 public int size();24 }
1 package queue; 2 3 /** 4 * 循环队列，使用数组实现 5 * @author jzj 6 */ 7 public class ArrayQueueimplements Queue { 8 9 private Object lock = new Object(); 10 11 // 队列大小 12 private int size = 1000; 13 14 // 队列 15 private E[] arrStr = (E[]) new Object[size]; 16 17 // 队列指针 18 private int head = 0; 19 20 // 队列尾指针 21 private int tail = 0; 22 23 /** 24 * 入队 25 * @param o 26 */ 27 public void enqueue(E o) { 28 synchronized (lock) { 29 30 // 如果队列已满 31 while ((tail + 1) % size == head) { 32 try { 33 System.out.println("队列已满，" + Thread.currentThread().getName() 34 + " 线程阻塞..."); 35 // 队列满时线程阻塞 36 lock.wait();//注，这里一定要放在while条件里，因为获取锁后，条件不一定还成立 37 } catch (InterruptedException e) { 38 e.printStackTrace(); 39 } 40 } 41 // 如果队列未满 42 arrStr[tail] = o; 43 // 指针下移 44 tail = (tail + 1) % size; 45 // 入队后通知消费线程 46 lock.notifyAll(); 47 } 48 } 49 50 /** 51 * 出队 52 * @return 53 */ 54 public E dequeue() { 55 synchronized (lock) { 56 // 如果队列为空 57 while (head == tail) { 58 try { 59 System.out.println("队列为空，" + Thread.currentThread().getName() 60 + " 线程阻塞..."); 61 // 队列空时线程阻塞 62 lock.wait();//注，这里一定要放在while条件里，因为获取锁后，条件不一定还成立 63 } catch (InterruptedException e) { 64 e.printStackTrace(); 65 } 66 } 67 // 队列非空 68 E tempStr = arrStr[head]; 69 70 arrStr[head] = null;//注，这里出队后释放对象，加快回收，不然大的对象可能造内存泄露 71 head = (head + 1) % size; 72 73 // 出队后通知生产者 74 lock.notifyAll(); 75 return tempStr; 76 77 } 78 } 79 80 //取队列第一个 81 public E front() { 82 synchronized (lock) { 83 // 如果队列为空 84 while (head == tail) { 85 try { 86 System.out.println("队列为空，" + Thread.currentThread().getName() 87 + " 线程阻塞..."); 88 // 队列空时线程阻塞 89 lock.wait();//注，这里一定要放在while条件里，因为获取锁后，条件不一定还成立 90 } catch (InterruptedException e) { 91 e.printStackTrace(); 92 } 93 } 94 // 队列非空 95 return arrStr[head]; 96 } 97 } 98 99 //队列是否为空100 public boolean isEmpty() {101 return head == tail;102 }103 104 //队列大小105 public int size() {106 107 return Math.abs(tail - head);108 }109 }
Jdk1.5已有java.util.Queue接口
使用1.5中并发新特性实现循环队列：来源于 API java.util.concurrent.locks.Condition
1 //循环缓冲队列，从队首放，从队尾出。牺牲数组的最后一个元素，用来判断队列是否满 2 class BoundedBuffer { 3 final Lock lock = new ReentrantLock();//可重入锁 4 final Condition notFull = lock.newCondition();//缓冲空条件对象 5 final Condition notEmpty = lock.newCondition();//缓冲非空条件对象 6 7 final Object[] items = new Object[100];//缓冲区 8 int putptr/*队首*/, takeptr/*队尾*/, count/*可用个数*/; 9 10 //将元素放入缓冲，供生产线程调用11 public void put(Object x) throws InterruptedException {12 lock.lock();//获取锁13 try {14 //注，要将await置于循环中，这也wait道理一样15 while (count == items.length)16 notFull.await();//缓冲满时等待，且释放锁17 items[putptr] = x;18 //如果队首指针指向数组最后索引时，重新指向数组第一个元素位置19 if (++putptr == items.length)20 putptr = 0;21 ++count;//循环队列中存入的元素个数22 notEmpty.signal();//放入元素后通知其它消费线程可以消费了23 } finally {24 lock.unlock();//释放锁25 }26 }27 28 //从缓冲取出元素，供消费线程调用29 public Object take() throws InterruptedException {30 lock.lock();31 try {32 while (count == 0)33 notEmpty.await();//如果缓冲空则等待34 Object x = items[takeptr];35 //如果队尾指针指向数组最后索引时，重新指向数组第一个元素位置36 if (++takeptr == items.length)37 takeptr = 0;38 --count;39 notFull.signal();//取出后会有空间，通知生产线程40 return x;41 } finally {42 lock.unlock();43 }44 }45 } 1 package queue; 2 3 import java.util.LinkedList; 4 5 /** 6 * 使用 LinkedList 实现队列 7 * @author jzj 8 * 9 * @param10 */11 public class LinkedListQueue implements Queue {12 private LinkedList linkedList = new LinkedList ();13 14 //入队15 public void enqueue(E e) {16 linkedList.addLast(e);17 }18 19 //出队20 public E dequeue() {21 return linkedList.removeFirst();22 }23 24 //取队列第一个25 public E front() {26 return linkedList.getFirst();27 }28 29 //队列是否为空30 public boolean isEmpty() {31 return linkedList.isEmpty();32 }33 34 //队列大小35 public int size() {36 return linkedList.size();37 }38 }
1 package queue; 2 3 import java.util.NoSuchElementException; 4 5 /** 6 * 使用 循环双向链 实现队列 7 * 8 * @author jzj 9 *10 * @param11 */12 public class LinkedQueue implements Queue {13 private class Entry {14 E element;//数据域15 Entry next;//后驱节点16 Entry previous;//前驱节点17 18 /**19 * @param element 数据域20 * @param next 后驱节点21 * @param previous 前驱节点22 */23 Entry(E element, Entry next, Entry previous) {24 this.element = element;25 this.next = next;26 this.previous = previous;27 }28 }29 30 /*31 * 头节点，永远代表头。链中无结节时节点中的前后驱指针域指向自己，当有元素时32 * 头节点的前驱指针域previous指向链中最后一个节点，而next指针域指向链中的33 * 第一个节点34 */35 private Entry header = new Entry(null, null, null);36 37 private int size = 0;//链表中节点个数，但不包括头节点header38 39 public LinkedQueue() {40 //初始化时头的前后驱指针都指向自己41 header.next = header.previous = header;42 }43 44 //入队，在链表中的最后位置加入元素，相当于 LinkedList 的add、addBefore、addLast方法实现45 public void enqueue(E e) {46 //在双向链后面加入元素47 Entry newEntry = new Entry(e, header, header.previous);48 //让新元素的前驱节点（新增前链的最后点）的前驱指向新加元素49 newEntry.previous.next = newEntry;50 //让新元素的后驱节点（header头节点）的前驱指向新加元素51 newEntry.next.previous = newEntry;52 size++;53 }54 55 //出队，从链表中的第一个元素开始出队，相当于 LinkedList 的removeFirst方法实现56 public E dequeue() {57 //要出队（删除）的节点的数据域58 E first = header.next.element;59 Entry e = header.next;60 //要删除的节点为头节点时不能删除61 if (e == header) {62 throw new NoSuchElementException();63 }64 65 //将删除节点的前驱节点的next域指针指向删除节点的后驱节点66 e.previous.next = e.next;67 //将删除节点的后驱节点的previous域指针指向删除节点的前驱节点68 e.next.previous = e.previous;69 size--;70 return first;71 }72 73 //取队列的第一个元素，相当于 LinkedList 的getFirst方法实现74 public E front() {75 if (size == 0)76 throw new NoSuchElementException();77 78 return header.next.element;79 }80 81 //队列是否为空82 public boolean isEmpty() {83 return size == 0;84 }85 86 //队列大小87 public int size() {88 return size;89 }90 }