Java/Collections Data Structure/Queue
Содержание
Blocking Queue
<source lang="java">
/**
* 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; /**
*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>NOTE: 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).
* IMPORTANT: 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;
}
}
</source>
Circular Queue
<source lang="java">
/* 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(); } }; }
}
</source>
Circular Queue extends AbstractList
<source lang="java">
/*
* 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); }
}
</source>
Convert a Queue to a List
<source lang="java">
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
- /
</source>
Create a queue using LinkedList class
<source lang="java">
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); } }
}
</source>
Priority queue
<source lang="java">
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(""); }
}
</source>
Queue data structure
<source lang="java">
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(""); }
}
</source>
Simple Queue (FIFO) based on LinkedList
<source lang="java">
// 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 null
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(); } /** * Returnstrue
if queue is empty, otherwisefalse
*/ public boolean isEmpty() { return list.isEmpty(); } /** * Returns queue size. */ public int size() { return list.size(); }
}
</source>
The Generic Queue Class
<source lang="java">
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); }
}
</source>