Java Tutorial/Collections/Queue
Версия от 17:44, 31 мая 2010; (обсуждение)
Содержание
A Priority Queue
/**
* 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.
*/
/** A PriorityQueue maintains a partial ordering of its elements such that the
least element can always be found in constant time. Put()"s and pop()"s
require log(size) time. */
public abstract class PriorityQueue {
private Object[] heap;
private int size;
private int maxSize;
/** Determines the ordering of objects in this priority queue. Subclasses
must define this one method. */
protected abstract boolean lessThan(Object a, Object b);
/** Subclass constructors must call this. */
protected final void initialize(int maxSize) {
size = 0;
int heapSize = maxSize + 1;
heap = new Object[heapSize];
this.maxSize = maxSize;
}
/**
* Adds an Object to a PriorityQueue in log(size) time.
* If one tries to add more objects than maxSize from initialize
* a RuntimeException (ArrayIndexOutOfBound) is thrown.
*/
public final void put(Object element) {
size++;
heap[size] = element;
upHeap();
}
/**
* Adds element to the PriorityQueue in log(size) time if either
* the PriorityQueue is not full, or not lessThan(element, top()).
* @param element
* @return true if element is added, false otherwise.
*/
public boolean insert(Object element){
if (size < maxSize){
put(element);
return true;
}
else if (size > 0 && !lessThan(element, top())){
heap[1] = element;
adjustTop();
return true;
}
else
return false;
}
/** Returns the least element of the PriorityQueue in constant time. */
public final Object top() {
if (size > 0)
return heap[1];
else
return null;
}
/** Removes and returns the least element of the PriorityQueue in log(size)
time. */
public final Object pop() {
if (size > 0) {
Object result = heap[1]; // save first value
heap[1] = heap[size]; // move last to first
heap[size] = null; // permit GC of objects
size--;
downHeap(); // adjust heap
return result;
} else
return null;
}
/** Should be called when the Object at top changes values. Still log(n)
* worst case, but it"s at least twice as fast to <pre>
* { pq.top().change(); pq.adjustTop(); }
* </pre> instead of <pre>
* { o = pq.pop(); o.change(); pq.push(o); }
* </pre>
*/
public final void adjustTop() {
downHeap();
}
/** Returns the number of elements currently stored in the PriorityQueue. */
public final int size() {
return size;
}
/** Removes all entries from the PriorityQueue. */
public final void clear() {
for (int i = 0; i <= size; i++)
heap[i] = null;
size = 0;
}
private final void upHeap() {
int i = size;
Object node = heap[i]; // save bottom node
int j = i >>> 1;
while (j > 0 && lessThan(node, heap[j])) {
heap[i] = heap[j]; // shift parents down
i = j;
j = j >>> 1;
}
heap[i] = node; // install saved node
}
private final void downHeap() {
int i = 1;
Object node = heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
if (k <= size && lessThan(heap[k], heap[j])) {
j = k;
}
while (j <= size && lessThan(heap[j], node)) {
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
if (k <= size && lessThan(heap[k], heap[j])) {
j = k;
}
}
heap[i] = node; // install saved node
}
}
Binary Heap Queue
/*
* Copyright 2005 JBoss 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.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.ruparator;
import java.util.NoSuchElementException;
public class BinaryHeapQueue implements Queue, Externalizable {
/** The default capacity for a binary heap. */
private final static int DEFAULT_CAPACITY = 13;
/** The comparator used to order the elements */
private Comparator comparator;
/** The number of elements currently in this heap. */
private int size;
/** The elements in this heap. */
private Queueable[] elements;
public BinaryHeapQueue() {
}
/**
* Constructs a new <code>BinaryHeap</code> that will use the given
* comparator to order its elements.
*
* @param comparator
* the comparator used to order the elements, null means use natural
* order
*/
public BinaryHeapQueue(final Comparator comparator) {
this(comparator, BinaryHeapQueue.DEFAULT_CAPACITY);
}
/**
* Constructs a new <code>BinaryHeap</code>.
*
* @param comparator
* the comparator used to order the elements, null means use natural
* order
* @param capacity
* the initial capacity for the heap
* @throws IllegalArgumentException
* if <code>capacity</code> is <= <code>0</code>
*/
public BinaryHeapQueue(final Comparator comparator, final int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("invalid capacity");
}
// +1 as 0 is noop
this.elements = new Queueable[capacity + 1];
this.ruparator = comparator;
}
// -----------------------------------------------------------------------
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
comparator = (Comparator) in.readObject();
elements = (Queueable[]) in.readObject();
size = in.readInt();
}
public void writeExternal(ObjectOutput out) throws IOException {
out.writeObject(comparator);
out.writeObject(elements);
out.writeInt(size);
}
/**
* Clears all elements from queue.
*/
public void clear() {
this.elements = new Queueable[this.elements.length]; // for gc
this.size = 0;
}
/**
* Tests if queue is empty.
*
* @return <code>true</code> if queue is empty; <code>false</code>
* otherwise.
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* Tests if queue is full.
*
* @return <code>true</code> if queue is full; <code>false</code>
* otherwise.
*/
public boolean isFull() {
// +1 as Queueable 0 is noop
return this.elements.length == this.size + 1;
}
/**
* Returns the number of elements in this heap.
*
* @return the number of elements in this heap
*/
public int size() {
return this.size;
}
/**
* Inserts an Queueable into queue.
*
* @param element
* the Queueable to be inserted
*/
public synchronized void enqueue(final Queueable element) {
if (isFull()) {
grow();
}
percolateUpMinHeap(element);
}
/**
* Returns the Queueable on top of heap and remove it.
*
* @return the Queueable at top of heap
* @throws NoSuchElementException
* if <code>isEmpty() == true</code>
*/
public synchronized Queueable dequeue() throws NoSuchElementException {
if (isEmpty()) {
return null;
}
final Queueable result = this.elements[1];
result.dequeue();
// Code bellow was removed because it is already executed
// inside result.dequeue()
//
// setElement(1, this.elements[this.size--]);
// this.elements[this.size + 1] = null;
//
// if (this.size != 0) {
// percolateDownMinHeap(1);
// }
return result;
}
/**
*
* @param index
*/
public synchronized Queueable dequeue(final int index) {
if (index < 1 || index > this.size) {
// throw new NoSuchElementException();
return null;
}
final Queueable result = this.elements[index];
setElement(index, this.elements[this.size]);
this.elements[this.size] = null;
this.size--;
if (this.size != 0 && index <= this.size) {
int compareToParent = 0;
if (index > 1) {
compareToParent = compare(this.elements[index], this.elements[index / 2]);
}
if (index > 1 && compareToParent < 0) {
percolateUpMinHeap(index);
} else {
percolateDownMinHeap(index);
}
}
return result;
}
/**
* Percolates Queueable down heap from the position given by the index. <p/>
* Assumes it is a minimum heap.
*
* @param index
* the index for the Queueable
*/
private void percolateDownMinHeap(final int index) {
final Queueable element = this.elements[index];
int hole = index;
while ((hole * 2) <= this.size) {
int child = hole * 2;
// if we have a right child and that child can not be percolated
// up then move onto other child
if (child != this.size && compare(this.elements[child + 1], this.elements[child]) < 0) {
child++;
}
// if we found resting place of bubble then terminate search
if (compare(this.elements[child], element) >= 0) {
break;
}
setElement(hole, this.elements[child]);
hole = child;
}
setElement(hole, element);
}
/**
* Percolates Queueable up heap from the position given by the index. <p/>
* Assumes it is a minimum heap.
*
* @param index
* the index of the Queueable to be percolated up
*/
private void percolateUpMinHeap(final int index) {
int hole = index;
final Queueable element = this.elements[hole];
while (hole > 1 && compare(element, this.elements[hole / 2]) < 0) {
// save Queueable that is being pushed down
// as the Queueable "bubble" is percolated up
final int next = hole / 2;
setElement(hole, this.elements[next]);
hole = next;
}
setElement(hole, element);
}
/**
* Percolates a new Queueable up heap from the bottom. <p/> Assumes it is a
* minimum heap.
*
* @param element
* the Queueable
*/
private void percolateUpMinHeap(final Queueable element) {
setElement(++this.size, element);
percolateUpMinHeap(this.size);
}
/**
* Compares two objects using the comparator if specified, or the natural
* order otherwise.
*
* @param a
* the first object
* @param b
* the second object
* @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
*/
private int compare(final Queueable a, final Queueable b) {
return this.ruparator.rupare(a, b);
}
/**
* Increases the size of the heap to support additional elements
*/
private void grow() {
final Queueable[] elements = new Queueable[this.elements.length * 2];
System.arraycopy(this.elements, 0, elements, 0, this.elements.length);
this.elements = elements;
}
/**
*
* @param index
* @param element
*/
private void setElement(final int index, final Queueable element) {
this.elements[index] = element;
element.enqueued(this, index);
}
public Queueable[] getQueueable() {
return this.elements;
}
public Object[] toArray() {
final Object[] result = new Object[this.size];
System.arraycopy(this.elements, 1, result, 0, this.size);
return result;
}
public Object[] toArray(Object a[]) {
if (a.length < this.size) {
a = (Object[]) java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), this.size);
}
System.arraycopy(this.elements, 1, a, 0, this.size);
if (a.length > this.size) {
a[this.size] = null;
}
return a;
}
}
/*
* Copyright 2005 JBoss 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.
*/
interface Queue {
public void enqueue(Queueable queueable);
public Queueable dequeue();
public Queueable dequeue(int index);
public boolean isEmpty();
}
/*
* Copyright 2005 JBoss 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.
*/
interface Queueable {
public void enqueued(Queue queue, int index);
public void dequeue();
}
Checking what item is first in line without removing it: element
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.add("A");
queue.add("B");
queue.offer("C");
queue.offer("D");
System.out.println("remove: " + queue.remove());
System.out.println("element: " + queue.element());
System.out.println("poll: " + queue.poll());
System.out.println("peek: " + queue.peek());
}
}
/*
remove: A
element: B
poll: B
peek: C
*/
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();
}
};
}
}
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);
}
}
}
Synchronized Queue
/*
* Copyright (c) 2003 - 2007 OpenSubsystems s.r.o. Slovak Republic. All rights reserved.
*
* Project: OpenSubsystems
*
* $Id: SynchronizedQueue.java,v 1.4 2007/01/07 06:14:00 bastafidli Exp $
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; version 2 of the License.
*
* This program 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
import java.util.LinkedList;
import java.util.List;
/**
* Class that implement unlimited queue, that is synchronized. It means that
* the consumer of the objects from the queue waits/is blocked in the get
* method until there is an object available.
*
* @version $Id: SynchronizedQueue.java,v 1.4 2007/01/07 06:14:00 bastafidli Exp $
* @author Miro Halas
* @code.reviewer Miro Halas
* @code.reviewed Initial revision
*/
public class SynchronizedQueue
{
// Attributes ///////////////////////////////////////////////////////////////
/**
* Cache of object produced by producer and consumed by consumer.
*/
protected List m_lstObjects;
// Constructors /////////////////////////////////////////////////////////////
/**
* Constructor for Synchronized Queue Object.
*/
public SynchronizedQueue(
)
{
super();
m_lstObjects = new LinkedList();
}
// Logic ////////////////////////////////////////////////////////////////////
/**
* Destructor for Synchronized Queue. It is called when no other
* object holds reference to it.
*
* @exception Throwable - default destructor exception
*/
protected void finalize(
) throws Throwable
{
// Explicitely remove this just to help garbage collector
m_lstObjects.clear();
m_lstObjects = null;
super.finalize();
}
/**
* Get the object from the beginning of the queue
*
* @return Object - object from the queue, if the thread is blocked in this
* function and you call interrupt method, an InterruptedException
* will be thrown.
* @exception InterruptedException - if the thread is blocked in this
* function and you call interrupt method,
* an InterruptedException will be thrown.
*/
public synchronized Object get(
) throws InterruptedException
{
Object objReturn = null;
if (m_lstObjects.isEmpty())
{
// There is no object in the queue, go to sleep
try
{
wait();
}
catch (InterruptedException ieException)
{
// Somebody woke us up, that means all threads waiting on this
// object competed for the lock and this one won and the object is
// locked again
// The thread can be woken up in two conditions, producer put new
// object into the queue or somebody called interrupt - to interrupt
// the wait - in this case rethrow an exception
if (m_lstObjects.isEmpty())
{
throw ieException;
}
}
}
// Remove the first object in the queue
objReturn = m_lstObjects.remove(0);
return objReturn;
}
/**
* Put the object to the end of the queue.
*
* @param objNew - new object, can be null
*/
public synchronized void put(
Object objNew
)
{
m_lstObjects.add(objNew);
// New object in the queue, notify others
notifyAll();
}
/**
* Test if the queue is empty.
*
* @return boolean - true if the queue is empty
*/
public synchronized boolean isEmpty(
)
{
return m_lstObjects.isEmpty();
}
}
Use the Stack class in Java
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < 10; i++) {
stack.push(i);
System.out.print(i + " ");
}
System.out.println("");
int position = stack.search(3);
System.out.println("Search result position: " + position);
System.out.println("Stack top: " + stack.peek());
while (!stack.empty()) {
System.out.print(stack.pop() + " ");
}
}
}
