Java Tutorial/Collections/Queue
Содержание
A Priority Queue
<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. */
/** 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
* { pq.top().change(); pq.adjustTop(); } *instead of
* { o = pq.pop(); o.change(); pq.push(o); }*
*/ 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 }
}</source>
Binary Heap Queue
<source lang="java">
/*
* 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 newBinaryHeap
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 newBinaryHeap
. * * @param comparator * the comparator used to order the elements, null means use natural * order * @param capacity * the initial capacity for the heap * @throws IllegalArgumentException * ifcapacity
is <=0
*/ 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. * * @returntrue
if queue is empty;false
* otherwise. */ public boolean isEmpty() { return this.size == 0; } /** * Tests if queue is full. * * @returntrue
if queue is full;false
* 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 * ifisEmpty() == true
*/ 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();
}</source>
Checking what item is first in line without removing it: element
<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.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
- /</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>
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>
Synchronized Queue
<source lang="java">
/*
* 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(); }
}</source>
Use the Stack class in Java
<source lang="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() + " "); } }
}</source>