JAvaアルゴリズム:FIFOキュー

JAvaアルゴリズム:FIFOキュー
FIFOキューはADTで、2つの基本操作で構成されています.新しいアイテムを挿入(挿入)し、最初に挿入したアイテムを削除(取得)します.
例1:FIFOキューADTインタフェース
Javaコード

interfaceintQueue{

intQueue(intq);

intempty();

voidput(intq);

intget();

}

interface intQueue{
	intQueue(int q);
	int empty();
	void put(int q);
	int get();
}

配列またはチェーンテーブルを使用して、FIFOキューADTのgetおよびput動作を一定時間で実現します.
例2:FIFOキューのチェーンテーブル実装
Javaコード

publicclassintQueue{

privateclassNode{

intitem;

Nodenext;

Node(intitem){

this.item=item;

next=null;

}

}

privateNodehead,tail;

intQueue(intmax){

head=null;

tail=null;

}

booleanempty(){

return(head==null);

}

voidput(intitem){

Nodet=tail;

tail=newNode(item);

if(empty()){

head=tail;

}else{

t.next=tail;

}

}

intget(){

intv=head.item;

Nodet=head.next;

head=t;

returnv;

}

}

public class intQueue{
	private class Node{
		int item;
		Node next;
		Node(int item){
			this.item = item; 
			next = null;
		}
	}
	private Node head, tail;
	intQueue(int max){
		head = null;
		tail = null;
	}
	boolean empty(){
		return (head == null);
	}
	void put(int item){
		Node t = tail;
		tail = new Node(item);
		if(empty()){
			head = tail;	
		}else{
			t.next = tail;
		}
	}
	int get(){
		int v = head.item;
		Node t = head.next;
		head = t;
		return v;
	}
}

配列は、予想される最大アイテム数に対して最初から最後まで十分なスペースを保持する必要があります.チェーンテーブルは、使用するスペースがデータ構造の要素の個数に比例していることを示しますが、ポインタに余分なスペースを割り当てる必要があります.また、各操作にはメモリの余分な時間を割り当て、解放する必要があります.
例3:FIFOキューの配列実装
Javaコード

publicclassintQueue{

privateint[]q;

privateintN,head,tail;

intQueue(intmax){

q=newint[maxN+1];

head=N;

tail=0;

}

booleanempty(){

return(head%N==tail);

}

voidput(intitem){

q[tail++]=item;

tail=tail%N;

}

intget(){

head=head%N;

returnq[head++];

}

}

public class intQueue{

	private int[] q;
	private int N, head, tail;

	intQueue(int max){
		q = new int[maxN + 1];
		head = N;
		tail = 0;
	}
	boolean empty(){
		return (head%N == tail);
	}
	void put(int item){
		q[tail++] = item;
		tail = tail%N;
	}
	int get(){
		head = head%N;
		return q[head++];
	}
}

拡張:両端キュー、ランダム・アイテム・キューの削除(最初がFIFOキュー、最後がスタックの場合)、またはキーワード・アイテム、カスタム・アイテムなどを削除します.