[データ構造キュー(Queue)

Qとは何ですか。

入力と出力を一端(前後)に制限する

初発売(FIFO):最初に発売された

キューの最初の要素は前で、終了要素は後で、

キューは、インバウンド時に後方から入るが、アウトバウンド時にフロントエンドから退出する特性を有する

メソッドでは、最初の要素と最後の要素

しか使用できません.

使用例

バッファ;乱入力処理不可;BFS

n.関数

データの挿入:enQueue()
データの抵当:DeQueue()
空かどうか:isEmpty()
満タンであることを確認:isFull()
データの挿入と削除時に、値の位置(スタック内のスタックポインタと同じ)を覚えておく必要があります.
この位置を覚えているのは前と後ろです
front:deQueueの位置を覚える
huft:enQueueの位置を覚える

インプリメンテーション

//기본값
private int size = 0; 
private int rear = -1; 
private int front = -1;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

//enQueue
public void enQueue(Object o) {
    if(isFull()) {
        return;
    }    
    queue[++rear] = o;
}
enQueue 시, 가득 찼다면 꽉 차 있는 상태에서 enQueue를 했기 때문에 
overflow 아니면 rear에 값 넣고 1 증가

//deQueue
public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    Object o = queue[front];
    queue[front++] = null;
    return o;
}
deQueue를 할 때 공백이면 underflow front에 위치한 값을 object에 꺼낸 후, 
꺼낸 위치는 null로 채워줌

//isEmpty
public boolean isEmpty() {
    return front == rear;
}
front와 rear가 같아지면 비어진 것

//isFull
public boolean isFull() {
    return (rear == queueSize-1);
}
rear가 사이즈-1과 같아지면 가득찬 것

一般的なキューの問題

キューに空きメモリがある場合でも、

がフル(末尾)と判断できます.

次元タイルキューを実装すると、削除されたスペースは

で使用できなくなります.
改善されたのは「円形キュー」です
論理的には、配列の先頭と末尾が関連付けられていると見なされます.
初期空白の場合、円形キューのフロントエンドとバックエンドは0です.
空白と飽和状態を区別するために、常に1つの位置を空けます.
(index+1)は%sizeにループします.

しかし、このようにして作られた円形のキューにも問題が発生します.

ループキューの問題

後者が前であれば問題が発生します.(つまり、後端と先端の位置が同じであれば)
満の状態と空の状態を区別できないからです.

円形キューのトラブルシューティング

空の状態と満の状態を分けるといいです.
空の状態:初期化された状態で、後方と前方の位置が同じである場合
満状態:後位の次の位置が前の位置になった場合
(すなわちhut=front+1)
空の状態を初期化状態として定義し、FとRを初期化状態で同じ配列インデックスを持つように設定します.
初期化状態(FとRが同じ空間を指す)をEmpty状態として定義する

この状態ではインデックスに情報を入れることができません

メモリが失われました.

しかし、アレイの長さは通常長いため、1つの格子のメモリ損失は小さく、コードのメリットはずっと大きいので、意味があります!
Rの次のビットがFである場合、全状態

と定義する.

リングキューの欠点

メモリ容量の使用率は高いが、アレイが採用されているため、キューのサイズは限られている.

接続リストキュー

接続リストキューにはサイズ制限がなく、挿入と削除が容易です.

# Node
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Singly linked list
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
 
    # Add new node at the end of the linked list
    def enqueue(self, node):
        if self.head == None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next
 
    def dequeue(self):
        if self.head == None:
            return -1
 
        v = self.head.data
        self.head = self.head.next
 
        if self.head == None:
            self.tail = None
        return v
 
    # 출력
    def print(self):
        curn = self.head
        string = ""
        while curn:
            string += str(curn.data)
            if curn.next:
                string += "->"
            curn = curn.next
        print(string)
 
 
if __name__ == "__main__":
    s = SinglyLinkedList()
    # 원소 추가
    s.enqueue(Node(1))
    s.enqueue(Node(2))
    s.enqueue(Node(3))
    s.enqueue(Node(4))
    s.print() # 1->2->3->4
 
    # 원소 삭제
    print(s.dequeue()) # 1
    print(s.dequeue()) # 2
    s.print()  # 3->4
    print(s.dequeue()) # 3
    print(s.dequeue()) # 4