(6)シーケンスキュー(Java)
2824 ワード
シーケンスキューは、rear側からfront側までのすべてのデータ要素を順次格納するアドレス連続メモリユニットのセットを採用し、プログラムはfrontとrearの2つの整数変数でキューfront側とrear側の要素インデックスを記録するだけである.シーケンスキューfrontは、キューから出る要素のインデックスを常に保存し、シーケンスキューrearは、次のキューに入る要素のインデックスを常に保存します.キュー要素の個数はrear-frontです.
シーケンスキューの場合、キューの下部にはキュー要素が格納され、各キュー要素の配列内の位置は固定され、rearとfrontの2つの整数変数のみが変化し、要素がキューに入るとrear+1、要素がキューから除去されるとfront変数の値+1になります.
実装コードは次のとおりです.
シーケンスキューの場合、キューの下部にはキュー要素が格納され、各キュー要素の配列内の位置は固定され、rearとfrontの2つの整数変数のみが変化し、要素がキューに入るとrear+1、要素がキューから除去されるとfront変数の値+1になります.
実装コードは次のとおりです.
package com.xuan.datastructs;
/**
* , elementData , front、rear
*/
import java.util.Arrays;
public class SequenceQueue<T> {
private int DEFAULT_SIZE=10;
//
private int capacity;
//
private Object[] elementData;
//
private int front=0;
private int rear=0;
//
public SequenceQueue() {
capacity=DEFAULT_SIZE;
elementData=new Object[capacity];
}
//
public SequenceQueue(T element){
this();
elementData[0]=element;
rear++;
}
/**
*
* @param element
* @param initSize
*/
public SequenceQueue(T element,int initSize){
this.capacity=initSize;
elementData=new Object[capacity];
elementData[0]=element;
rear++;
}
//
public int length(){
return rear-front;
}
//
public void add(T element){
if(rear>capacity-1){
throw new IndexOutOfBoundsException(" ");
}
elementData[rear++]=element;
}
//
public T remove(){
if(empty()){
throw new IndexOutOfBoundsException(" ");
}
// rear
T oldValue=(T)elementData[front];
// reat
elementData[front++]=null;
return oldValue;
}
//
public boolean empty(){
return rear==front;
}
// ,
public T element(){
if(empty()){
throw new IndexOutOfBoundsException(" ");
}
return(T)elementData[front];
}
//
public void clear(){
// null
Arrays.fill(elementData, null);
front=0;
rear=0;
}
public String toString() {
if(empty()){
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();
}
}
//
public static void main(String[] args) {
SequenceQueue<String> queue=new SequenceQueue<String>();
// 4
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.println(queue);
System.out.println(" front :"+queue.element());
System.out.println(" front :"+queue.remove());
System.out.println(" front :"+queue.remove());
System.out.println(" remove :"+queue);
}
}