[Data Structure] Queue
1486 ワード
キューは、要素に対してenqueue、dequeue操作を有し、秩序化された集合を提供する抽象データ型です.
Enqueueは、集合の最後尾(後方)に要素を追加する動作です.
dequeueは、集合の一番前(front)で要素を削除する操作です.
まず入力された値を削除するので、第1入力(FIFO)と呼ばれます.
他にもPeekアクションがあります.
Peekはdequenceを行わずに集合の一番前の値を返す動作である.
Method
enqueue
dequeue
peek
isEmpty
Example
銀行業務
コールセンター顧客待ち時間
BFS
import
タイプはQueueとして宣言できます.
インスタンスリンクリストを使用して作成
サイズを超えた場合、OfferはIllegalStateExceptionを実行しません.
Addがサイズを超えている場合は、IllegalStateExceptionを放出します.
(Capacity Restriction)
Priority Queue
通常のスタックやキューなどの抽象データ型
要素には通常「優先度」があります.
優先度が高い場合は、優先度が低い要素より優先されます.
優先度が同じ場合は、通常のキューと同じです.
import
2つのstack資料構造を利用する.
挿入時にstack資料構造の1つに追加し続けます.
削除時にスタック構造の要素をポップアップし、他のスタックに挿入
最後の1つが残っている場合は、要素を別のスタックに入れずに戻ります.
Deque
Double Ended Queueの略
解釈すると、両端から挿入および削除できる抽象データ型
2つのポインタを使用
いつ使いますか.
始点と終点を頻繁に使う場合には、これは良い選択です.
List対端点はO(n),DequeはO(1)
Method
first
last
addFirst
addLast
removeFirst
removeLast
remove (== queue)
add ( == queue)
size
contains
Import
Enqueueは、集合の最後尾(後方)に要素を追加する動作です.
dequeueは、集合の一番前(front)で要素を削除する操作です.
まず入力された値を削除するので、第1入力(FIFO)と呼ばれます.
他にもPeekアクションがあります.
Peekはdequenceを行わずに集合の一番前の値を返す動作である.
Method
enqueue
dequeue
peek
isEmpty
Example
銀行業務
コールセンター顧客待ち時間
BFS
import
タイプはQueueとして宣言できます.
インスタンスリンクリストを使用して作成
import java.util.Queue
import java.util.LinkedList
Offer vs Addサイズを超えた場合、OfferはIllegalStateExceptionを実行しません.
Addがサイズを超えている場合は、IllegalStateExceptionを放出します.
(Capacity Restriction)
Priority Queue
通常のスタックやキューなどの抽象データ型
要素には通常「優先度」があります.
優先度が高い場合は、優先度が低い要素より優先されます.
優先度が同じ場合は、通常のキューと同じです.
import
import java.util.PriorityQueue
Stackを使用したQueueの作成2つのstack資料構造を利用する.
挿入時にstack資料構造の1つに追加し続けます.
削除時にスタック構造の要素をポップアップし、他のスタックに挿入
最後の1つが残っている場合は、要素を別のスタックに入れずに戻ります.
Deque
Double Ended Queueの略
解釈すると、両端から挿入および削除できる抽象データ型
2つのポインタを使用
いつ使いますか.
始点と終点を頻繁に使う場合には、これは良い選択です.
List対端点はO(n),DequeはO(1)
Method
first
last
addFirst
addLast
removeFirst
removeLast
remove (== queue)
add ( == queue)
size
contains
Import
import java.util.ArrayDeque
Reference
この問題について([Data Structure] Queue), 我々は、より多くの情報をここで見つけました https://velog.io/@greenddoovie/Data-Structure-Queueテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol