キュー

Q(QUE)
スタックと同様に、一時的にデータをスタックするデータ構造キューは、最初にデータを格納するFIFO(First in First Out)フォーマットに従う.
Queueという言葉は実際には英会話でもよく使われていて、レストランで客が立っている列もqueueと呼ばれています.最初に待っている人が最初にレストランに入るように、キュー資料構造では、最初に入力したデータが最初に出力されます.
キューにデータを入れる操作をenqueue、データを取り出す操作をdequeueと呼びます.
データの取り出し部分を前の部分とし、データの入れ部分を後の部分として表す.
キューを効率的に実装するには、Ring Bufferを理解する必要があります.
Ring Bufferは配列の先頭と末尾が接続された構造で、最初の要素のindexはfrontであり、最後の要素+1 indexはhutである.
次に,JAVAコードを用いてRing Buffer構造を記憶しQueueを実装する.

public class IntQueue {
    private int max;        // 큐의 용량
    private int front;      // 첫 번째 요소 커서
    private int rear;       // 마지막 요소 커서
    private int num;        // 현재 데이터 수
    private int[] queue;    // 큐 본체

    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){}
    }
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){}
    }

    public IntQueue(int max) {
        num = 0;
        front = 0;
        rear = 0; 
        this.max = max;
        try{
            queue = new int[max];
        } catch (OutOfMemoryError e){
            e.printStackTrace();
        }
    }

    public int enqueue(int value) throws OverflowIntQueueException{
        if(num >= max) // 현재 데이터의 개수 (num) 가 용량치 이상일 경우 데이터추가시 오버플로우
            throw new OverflowIntQueueException();

        queue[rear++] = value;    // queue 의 rear 에 value 추가 후 rear 1 증가
        num++;                    // 현재 데이터 개수(num) 1 증가

        if(rear == max)           // 자료구조의 입구가 rear, 출구가 front 다. 순환해야함으로 입구가 배열의 끝까지가면 입구는 배열의 처음으로 이동
            rear = 0;

        return value;
    }

    public int deque() throws EmptyIntQueueException{
        if (num <= 0 )
            throw new EmptyIntQueueException();

        int frontVal = queue[front++];      // queue 에서 dequeue 할 값을 임시 저장 후 front 1 증가
        num--;                              // 현재 데이터 개수(num) 1 감소

        if(front == max)                    // front (데이터가 나가는 구멍)
            front = 0;

        return frontVal;
    }

    public int peek() throws EmptyIntQueueException{
        if(num <= 0)
            throw new EmptyIntQueueException();

        return queue[front];
    }

    public int indexOf(int x){
        for(int i = 0; i < num; i++){
            int idx = (i + front) % max;
            if(queue[idx] == x)
                return idx;
        }
        return -1;
    }

    public void clear(){
        num = front = rear = 0;
    }

    public int capacity(){
        return max;
    }

    public int size(){
        return num;
    }

    public boolean isEmpty(){
        return num <= 0 ;
    }

    public boolean isFull(){
        return num >= max;
    }

    public void dump(){
        if(num <= 0)
            System.out.println("큐가 비어있습니다");
        else {
            for(int i = 0 ; i < num; i++){
                System.out.print(queue[(i + front) % max]+ " ");
            }
            System.out.println();
        }
    }

}

/を参照
バッファ(buffer)はメモリ領域であり、ある位置から別の位置にデータを転送すると、バッファは一時的にデータを保持する.
ソース-https://ko.wikipedia.org/wiki/%EB%B2%84%ED%8D%BC_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99
/