edgequeue.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 64 行

package twf.weightedgraph.common;

import twf.weightedgraph.Edge;

public class EdgeQueue {
	private int capacity;
	private Edge[] e;
	private int tail, head;
	public EdgeQueue(int c) {
		if (c < 10) {
			c = 10;
		}
		capacity = c;
		e = new Edge[c];
		tail = head = 0;
	}
	public Edge get() {
		if (head == tail) {
			throw new RuntimeException(new EmptyEdgeQueueException());
		}
		Edge edge = e[head];
		head = (++head)%capacity;
		return edge;
	}
	public void put(Edge edge) {
		if ((tail + 1)%capacity == head) {
			capacity *= 2;
			Edge[] ee = new Edge[capacity];
			if (head < tail) {
				for (int i = head; i < tail; i ++) {
					ee[i - head] = e[i];
				}
			} else {
				for (int i = head; i < tail + capacity/2; i++) {
					ee[i - head] = e[i % (capacity/2)];
				}
			}
 			e = ee;
			e[tail++] = edge;
		} else {
			e[tail] = edge;
			tail = (tail + 1)%capacity;
		}
	}
	public boolean empty() {
		return head == tail;
	}
	public int size() {
		if (tail >= head) {
			return tail - head;
		} else {
			return tail + capacity - head;
		}
	}
	private class EmptyEdgeQueueException extends Exception {

		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;
		
	}
}