【DS】2.キュー

キュー:先出(FIFO)
キューのストレージ表現には、配列ベースのストレージ表現とチェーンテーブルベースのストレージ表現の2つがあります.配列ベースの格納表現はシーケンスキューとも呼ばれ,ダミーオーバーフローを避けるためにループ配列(リングのテーブル)を用いて格納する必要がある.
1.シーケンスキュー
キューは最初rear=front=0で、2つのポインタが初期位置にあります.このとき要素が入ってきて、rearポインタが指す位置を入れて、その後1つ前に移動して、順番に行います.
キューヘッダポインタ進1:front=(front+1)%maxSize
キュー末尾ポインタ進1:rear=(rear+1)%maxSize
キューが満たされているかどうかを判断します:(rear+1)%maxSize==front(つまり、rearポインタをfrontの前の位置に指し示すとキューが満たされているとみなされます)
以上の判断条件の下には、実際には1つの位置が空いています.この場所を残さない場合は、rear%maxSizeを使用してキューがいっぱいかどうかを判断する必要があります.これは、キューが空であるかどうかを判断する条件rear=fontと混同されるため、空にする必要があります.これにより、ループキューにはmaxSize-1要素しか配置できません.
 
2.チェーンキュー
単一チェーンテーブルで表されるチェーンキューは、特にデータ要素が大きい場合に適しており、キューがいっぱいでオーバーフローが発生することはありません.また、プログラムで複数のキューを使用する必要がある場合、複数のスタック(スタックも順次スタックとチェーンスタックに分けられる)の場合と同様に、チェーンキューを使用することが望ましい.これにより、ストレージ割り当てが不合理な問題がなく、ストレージの移動も必要ない.
 
キューのヘッダポインタは、単一チェーンテーブルの最初のノードを指し、キューの最後のポインタは単一チェーンテーブルの最後のノードを指します.削除ノードはキューから開始され、挿入ノードはキューの最後に行われます.
 
キーコード:
1)ノード定義:

public class QueueNode {
	private int data;
	private QueueNode next;
	
	public QueueNode(int data){
		this.data = data;
	}
	
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public QueueNode getNext() {
		return next;
	}
	public void setNext(QueueNode next) {
		this.next = next;
	}
}

2)キュー定義

/**
 *  
 * */
public class Queue<T> {
	QueueNode firstNode;
	QueueNode rearNode;
	int count;
	
	public Queue(){
		firstNode = new QueueNode(1);// ？
		rearNode = firstNode;
	}
	
	// 
	public void EnQueue(int data){
		QueueNode node = new QueueNode(data);
		rearNode.setNext(node);// 
		rearNode = rearNode.getNext();
		count++;
	}
	
	// 
	public int DeQueue(){
		if(!isEmpty()){// 
			QueueNode deNode = firstNode.getNext();
			firstNode.setNext(deNode.getNext());
			count--;
			
			if(isEmpty()){
				rearNode = firstNode;
			}
			return deNode.getData();
		}else{
			return -1;
		}
	}
	
	public boolean isEmpty(){
		return count == 0;
	}
	
	// 
	public void makeEmpty(){
		firstNode.setNext(null);
		rearNode = firstNode;
		count = 0;
	}
}

解決可能な問題:楊輝三角問題、コース符号化問題(圧縮技術)
 
 
ゆうせんキュー
キューから取り出すたびに、最も優先度の高い要素である必要があります.優先キューとも呼ばれます
優先度キューは、0つ以上の要素の集合であり、各要素には優先度または値があります.優先順位キューでは、主に1)検索が実行されます.2)挿入;3)削除します.
≪最小優先度キュー|Min Priority Queue|emdw≫:検索操作は、優先度の最小要素を検索するために使用され、削除操作は要素を削除するために使用されます.
≪最大優先度キュー|Maximum Priority Queue|emdw≫:検索操作は、優先度が最も大きい要素を検索するために使用され、削除操作は要素を削除するために使用されます.
挿入操作は、単純に新しい要素をキューに追加するだけです.(実際には、挿入後に要素を優先順位で並べるように一度調整することもできます)
 
両端に挿入を削除できるデュアル・エンド・キューもあります.