선입선출로 데이터를 관리하는 자료구조.
BFS와 같이 먼저 삽입된 노드부터 처리하는 알고리즘에서 사용한다.

선형 Queue

선형 Queue는 정해진 크기로 배열을 생성하고 rear와 front의 계산으로 삽입과 삭제가 일어난다.

정해진 사이즈를 정해놓고 증가만 하는 형태기 때문에 충분한 사이즈를 고려해야하고 overflow가 일어날 수 있다.
-> 원형 Queue로 해결.

삽입

public static void enqueue(int data){
	if(size >= queue.length){
    	System.out.println("OVERFLOW");
        return;
    }
    size++;
	rear++;
    queue[rear] = data;
}

삽입을 할 때 rear를 증가시키고 그 위치에 새로운 데이터를 저장한다. 즉 queue[rear]가 가장 최근에 삽입한 데이터가 된다.
그리고 size도 증가시켜서 queue의 길이를 넘게 되면 경고 메시지를 띄운다.

• 0 0 0 0 0 : init (rear=-1, front=-1)
• 1 0 0 0 0 : enqueue 1 (rear=0, front=-1)
• 1 2 0 0 0 : enqueue 2 (rear=1, front=-1)
  ...
• 1 2 3 4 5 : enqueue 5 (rear=4, front=-1)
• Overflow! : enqueue 6 (rear=5, front=-1)

삭제

public static int dequeue(){
	if(size == 0){
            System.out.println("EMPTY");
            return 0;
    }
    size--; 
	front++;
    if(front == rear) System.out.println("Now Empty");
    return queue[front];
}

삭제를 할 때 front를 증가시킨 뒤 해당하는 위치의 데이터를 리턴한다.
때문에 rear와 front가 같다는 것은 현재 데이터가 없다는 뜻이다.

• 1 2 3 4 5 : dequeue (rear=4, front=0) | return 1
• 1 2 3 4 5 : dequeue (rear=4, front=1) | return 2

삭제된 위치(1, 2)는 다시는 사용하지 못하므로 메모리를 효율적으로 사용하지 못한다.

원형 Queue

때문에 원형 큐를 사용한다. 선형 큐와 다른 점은 삽입, 삭제가 이루어질 때 rear와 front의 계산 방식에 있다.

삽입

public static void enqueue(int data){
	if(size >= queue.length){
    	System.out.println("OVERFLOW");
        return;
    }
    size++; rear++;
    rear = rear % queue.length;
    queue[rear] = data;
}

rear = rear % queue.length; : 나머지 연산을 통해 rear가 queue의 길이를 넘어설 때 처음으로 돌아가게끔 한다.

• 1 2 3 4 5 : enqueue 5 (rear=4, front=1)
• 6 2 3 4 5 : enqueue 6 (rear=0, front=1)

삭제한 공간도 사용할 수 있다.
하지만 queue의 길이보다 데이터를 넣으려고 하면 다음과 같이 덮어쓰기가 되어서 dequeue 연산을 할 때 엉뚱한 값을 가져올 수 있다.(size를 넘겼을 때 분기를 안했을 때)

• 1 2 3 4 5 : enqueue 5 (rear=4, front=-1)
• 6 2 3 4 5 : enqueue 6 (rear=0, front=-1)
• 6 2 3 4 5 : dequeue (rear=0, front=0) return 6

원래는 1을 리턴해야하지만 6을 리턴하게 되었다.

삭제

public static int dequeue(){
    if(size == 0){
        System.out.println("EMPTY");
        return 0;
    }
   	else{
        size--; front++;
        front = front % queue.length;
        if(front == rear) System.out.println("Now Empty");
        return queue[front];
    }
}

front도 rear와 같이 나머지 연산을 한다.