Java/Collections Data Structure/Queue
Версия от 18:01, 31 мая 2010; (обсуждение)
Содержание
Blocking Queue
/**
* The utillib library.
* More information is available at http://www.jinchess.ru/.
* Copyright (C) 2002 Alexander Maryanovsky.
* All rights reserved.
*
* The utillib library is free software; you can redistribute
* it and/or modify it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
*
* The utillib library is distributed in the hope that it will
* be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
* General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with utillib library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
import java.util.Enumeration;
import java.util.Vector;
/**
* <P>A blocking queue, one that always "contains" elements.
* If it is in fact empty, the pop() and peek() method will block until an
* item is pushed.
* <P><B>NOTE:</B> This class is thread safe.
*
* @author Alexander Maryanovsky.
*/
public class BlockingQueue implements Cloneable{
/**
* The underlying Vector this BlockingQueue is using.
*/
private final Vector queue;
/**
* The lock we use to synchronize pushing.
*/
private final Object pushLock = new String("BlockingQueue pushLock");
/**
* The lock we use to synchronize popping.
*/
private final Object popLock = new String("BlockingQueue popLock");
/**
* Creates a new, empty BlockingQueue.
*/
public BlockingQueue(){
queue = new Vector();
}
/**
* Pushes an element into the queue.
*/
public void push(Object object){
synchronized(pushLock){
queue.addElement(object);
synchronized(this){
notify();
}
}
}
/**
* Pops an element from the queue. If the queue is empty, this method blocks
* until another thread pushes an element into the queue.
*
* @throws InterruptedException if the invoking thread was interrupted
* while waiting for an element to be pushed into the queue.
*/
public Object pop() throws InterruptedException{
return pop(0);
}
/**
* Pops an element from the queue. Unlike the pop() method, this method does not block
* for longer than the given amount of milliseconds. When the given amount of milliseconds
* have passed, this method will throw an InterruptedException.
*/
public Object pop(long timeout) throws InterruptedException{
synchronized(popLock){
synchronized(this){
if (queue.isEmpty()){
wait(timeout);
if (queue.isEmpty())
throw new InterruptedException("Timed out");
}
}
Object val = queue.firstElement();
queue.removeElementAt(0);
return val;
}
}
/**
* Returns the element on top of the queue without popping it. If the queue
* is empty, this method blocks until another thread pushes an element into
* the queue.
*
* @throws InterruptedException if the invoking thread was interrupted while
* waiting for an element to be pushed into the queue.
*/
public Object peek() throws InterruptedException{
return peek(0);
}
/**
* Returns the element on top of the queue without popping it.
* Unlike the peek() method, this method does not block
* for longer than the given amount of milliseconds. When the given amount of milliseconds
* have passed, this method will throw an InterruptedException.
*/
public Object peek(long timeout) throws InterruptedException{
synchronized(popLock){
synchronized(this){
if (queue.isEmpty()){
wait(timeout);
if (queue.isEmpty())
throw new InterruptedException("Timed out");
}
}
return queue.firstElement();
}
}
/**
* Returns true if the queue is empty (this returns the actual state of the
* queue, meaning it may return true even though ideologically, a BlockingQueue
* is never empty).
*/
public boolean isEmpty(){
return queue.isEmpty();
}
/**
* Returns true if the given element is in the queue.
*/
public boolean contains(Object element){
return queue.contains(element);
}
/**
* Returns the size of the queue.
*/
public int size(){
return queue.size();
}
/**
* Returns an Enumeration of the elements in this queue. The order of the
* elements is the same as if they were popped from the queue one by one (the
* first element is the first element that would have been popped). <br>
* <B>IMPORTANT:</B> Modifying the queue breaks the returned Enumeration.
*/
public Enumeration getElements(){
return queue.elements();
}
/**
* Removes all elements from this queue.
*/
public void removeAllElements(){
queue.removeAllElements();
}
/**
* Removes all elements from this queue.
*/
public void clear(){
queue.removeAllElements();
}
/**
* Returns a shallow copy of this BlockingQueue.
*/
public synchronized Object clone(){
BlockingQueue copy = new BlockingQueue();
Enumeration elems = getElements();
while (elems.hasMoreElements()){
Object item = elems.nextElement();
copy.push(item);
}
return copy;
}
}
Circular Queue
/* Copyright 2004 BEA Systems, Inc.
*
* Licensed under the Apache License, 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.apache.org/licenses/LICENSE-2.0
*
* 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.
*/
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public final class CircularQueue extends AbstractCollection {
// This is the largest capacity allowed by this implementation
private static final int MAX_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 1 << 8;
private int size = 0;
private int producerIndex = 0;
private int consumerIndex = 0;
// capacity must be a power of 2 at all times
private int capacity;
private int maxCapacity;
// we mask with capacity -1. This variable caches that values
private int bitmask;
private Object[] q;
public CircularQueue() {
this(DEFAULT_CAPACITY);
}
// Construct a queue which has at least the specified capacity. If
// the value specified is a power of two then the queue will be
// exactly the specified size. Otherwise the queue will be the
// first power of two which is greater than the specified value.
public CircularQueue(int c) {
this(c, MAX_CAPACITY);
}
public CircularQueue(int c, int mc) {
if (c > mc) {
throw new IllegalArgumentException("Capacity greater than maximum");
}
if (mc > MAX_CAPACITY) {
throw new IllegalArgumentException("Maximum capacity greater than " +
"allowed");
}
for (capacity = 1; capacity < c; capacity <<= 1) ;
for (maxCapacity = 1; maxCapacity < mc; maxCapacity <<= 1) ;
bitmask = capacity - 1;
q = new Object[capacity];
}
// Constructor used by clone()
private CircularQueue(CircularQueue oldQueue) {
size = oldQueue.size;
producerIndex = oldQueue.producerIndex;
consumerIndex = oldQueue.consumerIndex;
capacity = oldQueue.capacity;
maxCapacity = oldQueue.maxCapacity;
bitmask = oldQueue.bitmask;
q = new Object[oldQueue.q.length];
System.arraycopy(oldQueue.q, 0, q, 0, q.length);
}
private boolean expandQueue() {
// double the size of the queue
// This design assumes that this is a rare case
if (capacity == maxCapacity) {
return false;
}
int old_capacity = capacity;
Object[] old_q = q;
capacity += capacity;
bitmask = capacity - 1;
q = new Object[capacity];
System.arraycopy(old_q, consumerIndex, q, 0, old_capacity - consumerIndex);
if (consumerIndex != 0) {
System.arraycopy(old_q, 0, q, old_capacity - consumerIndex,
consumerIndex);
}
consumerIndex = 0;
producerIndex = size;
return true;
}
public boolean add(Object obj) {
if (size == capacity) {
// no room
if (!expandQueue()) return false;
}
size++;
q[producerIndex] = obj;
producerIndex = (producerIndex + 1) & bitmask;
return true;
}
public Object remove() {
Object obj;
if (size == 0) return null;
size--;
obj = q[consumerIndex];
q[consumerIndex] = null; // allow gc to collect
consumerIndex = (consumerIndex + 1) & bitmask;
return obj;
}
public boolean isEmpty() { return size == 0; }
public int size() { return size; }
public int capacity() { return capacity; }
public Object peek() {
if (size == 0) return null;
return q[consumerIndex];
}
public void clear() {
Arrays.fill(q, null);
size = 0;
producerIndex = 0;
consumerIndex = 0;
}
public Object clone() {
return new CircularQueue(this);
}
public String toString() {
StringBuffer s = new StringBuffer(super.toString() + " - capacity: "" +
capacity() + "" size: "" + size() + """);
if (size > 0) {
s.append(" elements:");
for (int i = 0; i < size; ++i) {
s.append("\n");
s.append("\t");
s.append(q[consumerIndex + i & bitmask].toString());
}
}
return s.toString();
}
public Iterator iterator() {
return new Iterator() {
private final int ci = consumerIndex;
private final int pi = producerIndex;
private int s = size;
private int i = ci;
public boolean hasNext() {
checkForModification();
return s > 0;
}
public Object next() {
checkForModification();
if (s == 0) throw new NoSuchElementException();
s--;
Object r = q[i];
i = (i + 1) & bitmask;
return r;
}
public void remove() {
throw new UnsupportedOperationException();
}
private void checkForModification() {
if (ci != consumerIndex) throw new ConcurrentModificationException();
if (pi != producerIndex) throw new ConcurrentModificationException();
}
};
}
}
Circular Queue extends AbstractList
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, 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.apache.org/licenses/LICENSE-2.0
*
* 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.
*
*/
import java.io.Serializable;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
/**
* A unbounded circular queue based on array.
*
* @author The Apache MINA Project (dev@mina.apache.org)
* @version $Rev: 762170 $, $Date: 2009-04-06 00:01:18 +0200 (Mon, 06 Apr 2009) $
*/
public class CircularQueue<E> extends AbstractList<E> implements List<E>, Queue<E>, Serializable {
/** The serialVersionUID : mandatory for serializable classes */
private static final long serialVersionUID = 3993421269224511264L;
/** Minimal size fo the underlying attay */
private static final int DEFAULT_CAPACITY = 4;
/** The initial capacity of the list */
private final int initialCapacity;
// XXX: This volatile keyword here is a workaround for SUN Java Compiler bug,
// which produces buggy byte code. I don"t event know why adding a volatile
// fixes the problem. Eclipse Java Compiler seems to produce correct byte code.
private volatile Object[] items;
private int mask;
private int first = 0;
private int last = 0;
private boolean full;
private int shrinkThreshold;
/**
* Construct a new, empty queue.
*/
public CircularQueue() {
this(DEFAULT_CAPACITY);
}
public CircularQueue(int initialCapacity) {
int actualCapacity = normalizeCapacity(initialCapacity);
items = new Object[actualCapacity];
mask = actualCapacity - 1;
this.initialCapacity = actualCapacity;
this.shrinkThreshold = 0;
}
/**
* The capacity must be a power of 2.
*/
private static int normalizeCapacity(int initialCapacity) {
int actualCapacity = 1;
while (actualCapacity < initialCapacity) {
actualCapacity <<= 1;
if (actualCapacity < 0) {
actualCapacity = 1 << 30;
break;
}
}
return actualCapacity;
}
/**
* Returns the capacity of this queue.
*/
public int capacity() {
return items.length;
}
@Override
public void clear() {
if (!isEmpty()) {
Arrays.fill(items, null);
first = 0;
last = 0;
full = false;
shrinkIfNeeded();
}
}
@SuppressWarnings("unchecked")
public E poll() {
if (isEmpty()) {
return null;
}
Object ret = items[first];
items[first] = null;
decreaseSize();
if (first == last) {
first = last = 0;
}
shrinkIfNeeded();
return (E) ret;
}
public boolean offer(E item) {
if (item == null) {
throw new NullPointerException("item");
}
expandIfNeeded();
items[last] = item;
increaseSize();
return true;
}
@SuppressWarnings("unchecked")
public E peek() {
if (isEmpty()) {
return null;
}
return (E) items[first];
}
@SuppressWarnings("unchecked")
@Override
public E get(int idx) {
checkIndex(idx);
return (E) items[getRealIndex(idx)];
}
@Override
public boolean isEmpty() {
return (first == last) && !full;
}
@Override
public int size() {
if (full) {
return capacity();
}
if (last >= first) {
return last - first;
} else {
return last - first + capacity();
}
}
@Override
public String toString() {
return "first=" + first + ", last=" + last + ", size=" + size()
+ ", mask = " + mask;
}
private void checkIndex(int idx) {
if (idx < 0 || idx >= size()) {
throw new IndexOutOfBoundsException(String.valueOf(idx));
}
}
private int getRealIndex(int idx) {
return (first + idx) & mask;
}
private void increaseSize() {
last = (last + 1) & mask;
full = first == last;
}
private void decreaseSize() {
first = (first + 1) & mask;
full = false;
}
private void expandIfNeeded() {
if (full) {
// expand queue
final int oldLen = items.length;
final int newLen = oldLen << 1;
Object[] tmp = new Object[newLen];
if (first < last) {
System.arraycopy(items, first, tmp, 0, last - first);
} else {
System.arraycopy(items, first, tmp, 0, oldLen - first);
System.arraycopy(items, 0, tmp, oldLen - first, last);
}
first = 0;
last = oldLen;
items = tmp;
mask = tmp.length - 1;
if (newLen >>> 3 > initialCapacity) {
shrinkThreshold = newLen >>> 3;
}
}
}
private void shrinkIfNeeded() {
int size = size();
if (size <= shrinkThreshold) {
// shrink queue
final int oldLen = items.length;
int newLen = normalizeCapacity(size);
if (size == newLen) {
newLen <<= 1;
}
if (newLen >= oldLen) {
return;
}
if (newLen < initialCapacity) {
if (oldLen == initialCapacity) {
return;
} else {
newLen = initialCapacity;
}
}
Object[] tmp = new Object[newLen];
// Copy only when there"s something to copy.
if (size > 0) {
if (first < last) {
System.arraycopy(items, first, tmp, 0, last - first);
} else {
System.arraycopy(items, first, tmp, 0, oldLen - first);
System.arraycopy(items, 0, tmp, oldLen - first, last);
}
}
first = 0;
last = size;
items = tmp;
mask = tmp.length - 1;
shrinkThreshold = 0;
}
}
@Override
public boolean add(E o) {
return offer(o);
}
@SuppressWarnings("unchecked")
@Override
public E set(int idx, E o) {
checkIndex(idx);
int realIdx = getRealIndex(idx);
Object old = items[realIdx];
items[realIdx] = o;
return (E) old;
}
@Override
public void add(int idx, E o) {
if (idx == size()) {
offer(o);
return;
}
checkIndex(idx);
expandIfNeeded();
int realIdx = getRealIndex(idx);
// Make a room for a new element.
if (first < last) {
System
.arraycopy(items, realIdx, items, realIdx + 1, last
- realIdx);
} else {
if (realIdx >= first) {
System.arraycopy(items, 0, items, 1, last);
items[0] = items[items.length - 1];
System.arraycopy(items, realIdx, items, realIdx + 1,
items.length - realIdx - 1);
} else {
System.arraycopy(items, realIdx, items, realIdx + 1, last
- realIdx);
}
}
items[realIdx] = o;
increaseSize();
}
@SuppressWarnings("unchecked")
@Override
public E remove(int idx) {
if (idx == 0) {
return poll();
}
checkIndex(idx);
int realIdx = getRealIndex(idx);
Object removed = items[realIdx];
// Remove a room for the removed element.
if (first < last) {
System.arraycopy(items, first, items, first + 1, realIdx - first);
} else {
if (realIdx >= first) {
System.arraycopy(items, first, items, first + 1, realIdx
- first);
} else {
System.arraycopy(items, 0, items, 1, realIdx);
items[0] = items[items.length - 1];
System.arraycopy(items, first, items, first + 1, items.length
- first - 1);
}
}
items[first] = null;
decreaseSize();
shrinkIfNeeded();
return (E) removed;
}
public E remove() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return poll();
}
public E element() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return peek();
}
}
///////////////////////////////////////////////
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, 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.apache.org/licenses/LICENSE-2.0
*
* 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.
*
*/
package org.apache.mina.util;
import junit.framework.TestCase;
import java.util.Iterator;
/**
* Tests {@link org.apache.mina.util.CircularQueue}
*
* @author The Apache MINA Project (dev@mina.apache.org)
* @version $Rev: 755170 $, $Date: 2009-03-17 10:46:58 +0100 (Tue, 17 Mar 2009) $
*/
public class CircularQueueTest extends TestCase {
private volatile int pushCount;
private volatile int popCount;
public void setUp() {
pushCount = 0;
popCount = 0;
}
public void testRotation() {
CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
testRotation0(q);
}
public void testExpandingRotation() {
CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
for (int i = 0; i < 10; i++) {
testRotation0(q);
// make expansion happen
int oldCapacity = q.capacity();
for (int j = q.capacity(); j >= 0; j--) {
q.offer(new Integer(++pushCount));
}
assertTrue(q.capacity() > oldCapacity);
testRotation0(q);
}
}
private void testRotation0(CircularQueue<Integer> q) {
for (int i = 0; i < q.capacity() * 7 / 4; i++) {
q.offer(new Integer(++pushCount));
assertEquals(++popCount, q.poll().intValue());
}
}
public void testRandomAddOnQueue() {
CircularQueue<Integer> q = new CircularQueue<Integer>();
// Create a queue with 5 elements and capacity 8;
for (int i = 0; i < 5; i++) {
q.offer(new Integer(i));
}
q.add(0, new Integer(100));
q.add(3, new Integer(200));
q.add(7, new Integer(300));
Iterator<Integer> i = q.iterator();
assertEquals(8, q.size());
assertEquals(new Integer(100), i.next());
assertEquals(new Integer(0), i.next());
assertEquals(new Integer(1), i.next());
assertEquals(new Integer(200), i.next());
assertEquals(new Integer(2), i.next());
assertEquals(new Integer(3), i.next());
assertEquals(new Integer(4), i.next());
assertEquals(new Integer(300), i.next());
try {
i.next();
fail();
} catch (Exception e) {
// an exception signifies a successfull test case
assertTrue(true);
}
}
public void testRandomAddOnRotatedQueue() {
CircularQueue<Integer> q = getRotatedQueue();
q.add(0, new Integer(100)); // addFirst
q.add(2, new Integer(200));
q.add(4, new Integer(300));
q.add(10, new Integer(400));
q.add(12, new Integer(500)); // addLast
Iterator<Integer> i = q.iterator();
assertEquals(13, q.size());
assertEquals(new Integer(100), i.next());
assertEquals(new Integer(0), i.next());
assertEquals(new Integer(200), i.next());
assertEquals(new Integer(1), i.next());
assertEquals(new Integer(300), i.next());
assertEquals(new Integer(2), i.next());
assertEquals(new Integer(3), i.next());
assertEquals(new Integer(4), i.next());
assertEquals(new Integer(5), i.next());
assertEquals(new Integer(6), i.next());
assertEquals(new Integer(400), i.next());
assertEquals(new Integer(7), i.next());
assertEquals(new Integer(500), i.next());
try {
i.next();
fail();
} catch (Exception e) {
// an exception signifies a successfull test case
assertTrue(true);
}
}
public void testRandomRemoveOnQueue() {
CircularQueue<Integer> q = new CircularQueue<Integer>();
// Create a queue with 5 elements and capacity 8;
for (int i = 0; i < 5; i++) {
q.offer(new Integer(i));
}
q.remove(0);
q.remove(2);
q.remove(2);
Iterator<Integer> i = q.iterator();
assertEquals(2, q.size());
assertEquals(new Integer(1), i.next());
assertEquals(new Integer(2), i.next());
try {
i.next();
fail();
} catch (Exception e) {
// an exception signifies a successfull test case
assertTrue(true);
}
}
public void testRandomRemoveOnRotatedQueue() {
CircularQueue<Integer> q = getRotatedQueue();
q.remove(0); // removeFirst
q.remove(2); // removeLast in the first half
q.remove(2); // removeFirst in the first half
q.remove(4); // removeLast
Iterator<Integer> i = q.iterator();
assertEquals(4, q.size());
assertEquals(new Integer(1), i.next());
assertEquals(new Integer(2), i.next());
assertEquals(new Integer(5), i.next());
assertEquals(new Integer(6), i.next());
try {
i.next();
fail();
} catch (Exception e) {
// an exception signifies a successfull test case
assertTrue(true);
}
}
public void testExpandAndShrink() throws Exception {
CircularQueue<Integer> q = new CircularQueue<Integer>();
for (int i = 0; i < 1024; i ++) {
q.offer(i);
}
assertEquals(1024, q.capacity());
for (int i = 0; i < 512; i ++) {
q.offer(i);
q.poll();
}
assertEquals(2048, q.capacity());
for (int i = 0; i < 1024; i ++) {
q.poll();
}
assertEquals(4, q.capacity());
}
private CircularQueue<Integer> getRotatedQueue() {
CircularQueue<Integer> q = new CircularQueue<Integer>();
// Ensure capacity: 16
for (int i = 0; i < 16; i++) {
q.offer(new Integer(-1));
}
q.clear();
// Rotate it
for (int i = 0; i < 12; i++) {
q.offer(new Integer(-1));
q.poll();
}
// Now push items
for (int i = 0; i < 8; i++) {
q.offer(new Integer(i));
}
return q;
}
public static void main(String[] args) {
junit.textui.TestRunner.run(CircularQueueTest.class);
}
}
Convert a Queue to a List
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> myQueue = new LinkedList<String>();
myQueue.add("A");
myQueue.add("B");
myQueue.add("C");
myQueue.add("D");
List<String> myList = new ArrayList<String>(myQueue);
for (Object theFruit : myList)
System.out.println(theFruit);
}
}
/*
A
B
C
D
*/
Create a queue using LinkedList class
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");
queue.offer("Fourth");
System.out.println("Size: " + queue.size());
System.out.println("Queue head using peek : " + queue.peek());
System.out.println("Queue head using element: " + queue.element());
Object data;
while ((data = queue.poll()) != null) {
System.out.println(data);
}
}
}
Priority queue
public class PriorityQ {
// array in sorted order, from max at 0 to min at size-1
private int maxSize;
private long[] queArray;
private int nItems;
public PriorityQ(int s) {
maxSize = s;
queArray = new long[maxSize];
nItems = 0;
}
public void insert(long item) {
int i;
if (nItems == 0)
queArray[nItems++] = item; // insert at 0
else
{
for (i = nItems - 1; i >= 0; i--) // start at end,
{
if (item > queArray[i]) // if new item larger,
queArray[i + 1] = queArray[i]; // shift upward
else
// if smaller,
break; // done shifting
}
queArray[i + 1] = item; // insert it
nItems++;
} // end else (nItems > 0)
}
public long remove(){
return queArray[--nItems];
}
public long peekMin(){
return queArray[nItems - 1];
}
public boolean isEmpty(){
return (nItems == 0);
}
public boolean isFull(){
return (nItems == maxSize);
}
public static void main(String[] args) {
PriorityQ thePQ = new PriorityQ(5);
thePQ.insert(30);
thePQ.insert(50);
thePQ.insert(10);
thePQ.insert(40);
thePQ.insert(20);
while (!thePQ.isEmpty()) {
long item = thePQ.remove();
System.out.print(item + " "); // 10, 20, 30, 40, 50
}
System.out.println("");
}
}
Queue data structure
public class Queue {
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s) {
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
// put item at end of a queue
public void insert(long j) {
if (rear == maxSize - 1) // deal with wraparound
rear = -1;
queArray[++rear] = j; // increment rear and insert
nItems++;
}
// take item from front of queue
public long remove() {
long temp = queArray[front++]; // get value and incr front
if (front == maxSize) // deal with wraparound
front = 0;
nItems--; // one less item
return temp;
}
public long peekFront() {
return queArray[front];
}
public boolean isEmpty() {
return (nItems == 0);
}
public boolean isFull() {
return (nItems == maxSize);
}
public int size() {
return nItems;
}
public static void main(String[] args) {
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10);
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove();
theQueue.remove();
theQueue.remove();
theQueue.insert(50);
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while (!theQueue.isEmpty()) {
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
}
}
Simple Queue (FIFO) based on LinkedList
// Copyright (c) 2003-2009, Jodd Team (jodd.org). All Rights Reserved.
import java.util.LinkedList;
/**
* Simple Queue (FIFO) based on LinkedList.
*/
public class SimpleQueue<E> {
private LinkedList<E> list = new LinkedList<E>();
/**
* Puts object in queue.
*/
public void put(E o) {
list.addLast(o);
}
/**
* Returns an element (object) from queue.
*
* @return element from queue or <code>null</code> if queue is empty
*/
public E get() {
if (list.isEmpty()) {
return null;
}
return list.removeFirst();
}
/**
* Returns all elements from the queue and clears it.
*/
public Object[] getAll() {
Object[] res = new Object[list.size()];
for (int i = 0; i < res.length; i++) {
res[i] = list.get(i);
}
list.clear();
return res;
}
/**
* Peeks an element in the queue. Returned elements is not removed from the queue.
*/
public E peek() {
return list.getFirst();
}
/**
* Returns <code>true</code> if queue is empty, otherwise <code>false</code>
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* Returns queue size.
*/
public int size() {
return list.size();
}
}
The Generic Queue Class
import java.util.LinkedList;
class GenQueue<E> {
private LinkedList<E> list = new LinkedList<E>();
public void enqueue(E item) {
list.addLast(item);
}
public E dequeue() {
return list.poll();
}
public boolean hasItems() {
return !list.isEmpty();
}
public int size() {
return list.size();
}
public void addItems(GenQueue<? extends E> q) {
while (q.hasItems())
list.addLast(q.dequeue());
}
}
public class GenQueueTest {
public static void main(String[] args) {
GenQueue<Employee> empList;
empList = new GenQueue<Employee>();
GenQueue<HourlyEmployee> hList;
hList = new GenQueue<HourlyEmployee>();
hList.enqueue(new HourlyEmployee("T", "D"));
hList.enqueue(new HourlyEmployee("G", "B"));
hList.enqueue(new HourlyEmployee("F", "S"));
empList.addItems(hList);
while (empList.hasItems()) {
Employee emp = empList.dequeue();
System.out.println(emp.firstName + " " + emp.lastName);
}
}
}
class Employee {
public String lastName;
public String firstName;
public Employee() {
}
public Employee(String last, String first) {
this.lastName = last;
this.firstName = first;
}
public String toString() {
return firstName + " " + lastName;
}
}
class HourlyEmployee extends Employee {
public double hourlyRate;
public HourlyEmployee(String last, String first) {
super(last, first);
}
}
