javaキューの実現（シーケンス行列、チェーン行列、循環行列）
10497 ワード
双方向順序行列ArayDequeと双方向チェーン列Linked Listは、JDKが含まれています。ここで省略します。ArayDequeはシーケンススタックと順序行列を含み、LinkedListはチェーンスタックとチェーン列を含む。ArayDequeとLinkdListはスレッドが不安定です。PriorityQue優先列もJDKにあります。
1.順番待ちの実現
2.チェーン行列の実現
3.循環キューの実現
1.順番待ちの実現
package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
* @ClassName: ArrayQueue
* @Description:
* @date 2014 1 20 3:46:19
* @param
*/
public class ArrayQueue implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = 7333344126529379197L;
private int DEFAULT_SIZE = 10;
private int capacity;//
private Object[] elementData;//
private int front = 0;//
private int rear = 0;//
//
public ArrayQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//
public ArrayQueue(T element) {
this();
elementData[0] = element;
rear++;
}
public ArrayQueue(int initSize) {
elementData = new Object[initSize];
}
/**
*
* @param element
* @param initSize
*/
public ArrayQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
/**
* @Title: size
* @Description:
* @return
*/
public int size() {
return rear - front;
}
/**
* @Title: offer
* @Description:
* @param element
*/
public void offer(T element) {
ensureCapacity(rear + 1);
elementData[rear++] = element;
}
private void ensureCapacity(int minCapacity) {
//
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* @Title: poll
* @Description:
* @return
*/
public T poll() {
if (isEmpty()) {
throw new IndexOutOfBoundsException(" ");
}
// front
T oldValue = (T) elementData[front];
// front
elementData[front++] = null;
return oldValue;
}
/**
* @Title: peek
* @Description: ，
* @return
*/
public T peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException(" ");
}
return (T) elementData[front];
}
/**
* @Title: isEmpty
* @Description:
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* @Title: clear
* @Description:
*/
public void clear() {
// null
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
} 2.チェーン行列の実現
package lang;
import java.io.Serializable;
/**
* @ClassName: LinkQueue
* @Description:
* @date 2014 1 21 3:24:38
* @param
*/
public class LinkQueue implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -6726728595616312615L;
// Node，Node 。
private class Node {
private T data;//
private Node next;//
//
public Node() {
}
//
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node front;//
private Node rear;//
private int size;//
/**
* Title: LinkQueue
* Description:
*/
public LinkQueue() {
// ，front rear null
front = null;
rear = null;
}
/**
* Title: LinkQueue
* Description: ，
*/
public LinkQueue(T element) {
front = new Node(element, null);
// ，front、rear
rear = front;
size++;
}
/**
* @Title: size
* @Description:
* @return
*/
public int size() {
return size;
}
/**
* @Title: offer
* @Description:
* @param element
*/
public void offer(T element) {
//
if (front == null) {
front = new Node(element, null);
rear = front;// ，front、rear
} else {
Node newNode = new Node(element, null);//
rear.next = newNode;// next
rear = newNode;//
}
size++;
}
/**
* @Title: poll
* @Description:
* @return
*/
public T poll() {
Node oldFront = front;
front = front.next;
oldFront.next = null;
size--;
return oldFront.data;
}
/**
* @Title: peek
* @Description: ，
* @return
*/
public T peek() {
return rear.data;
}
/**
* @Title: isEmpty
* @Description:
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @Title: clear
* @Description:
*/
public void clear() {
// front、rear null
front = null;
rear = null;
size = 0;
}
public String toString() {
//
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (Node current = front; current != null; current = current.next) {
sb.append(current.data.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
public static void main(String[] args) {
LinkQueue queue = new LinkQueue("aaaa");
//
queue.offer("bbbb");
queue.offer("cccc");
System.out.println(queue);
//
queue.poll();
System.out.println(" ：" + queue);
//
queue.offer("dddd");
System.out.println(" ：" + queue);
// ，
queue.poll();
//
queue.offer("eeee");
System.out.println(queue);
}
}
3.循環キューの実現
package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
* @ClassName: LoopQueue
* @Description:
* @date 2014 1 20 3:47:14
*/
public class LoopQueue implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -3670496550272478781L;
private int DEFAULT_SIZE = 10;
private int capacity;//
private Object[] elementData;//
private int front = 0;//
private int rear = 0;//
//
public LoopQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//
public LoopQueue(T element) {
this();
elementData[0] = element;
rear++;
}
/**
*
* @param element
* @param initSize
*/
public LoopQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
//
public int size() {
if (isEmpty()) {
return 0;
}
return rear > front ? rear - front : capacity - (front - rear);
}
//
public void add(T element) {
if (rear == front && elementData[front] != null) {
throw new IndexOutOfBoundsException(" ");
}
elementData[rear++] = element;
// rear ，
rear = rear == capacity ? 0 : rear;
}
//
public T remove() {
if (isEmpty()) {
throw new IndexOutOfBoundsException(" ");
}
// rear
T oldValue = (T) elementData[front];
// rear
elementData[front++] = null;
// front ，
front = front == capacity ? 0 : front;
return oldValue;
}
// ，
public T element() {
if (isEmpty()) {
throw new IndexOutOfBoundsException(" ");
}
return (T) elementData[front];
}
//
public boolean isEmpty() {
//rear==front rear null
return rear == front && elementData[rear] == null;
}
//
public void clear() {
// null
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
// front < rear， front rear
if (front < rear) {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
// front >= rear， front->capacity 、0->front
else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < capacity; i++) {
sb.append(elementData[i].toString() + ", ");
}
for (int i = 0; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
public static void main(String[] args) {
LoopQueue queue = new LoopQueue("aaaa", 3);
//
queue.add("bbbb");
queue.add("cccc");
//
System.out.println(queue);
// ，
queue.remove();
System.out.println(" ：" + queue);
// ，
queue.add("dddd");
System.out.println(queue);
System.out.println(" ：" + queue.size());
// ，
queue.remove();
// ，
queue.add("eeee");
System.out.println(queue);
}
}