큐

- 큐

큐의 구조는 스택과 다르게 '선입선출'의 구조를 가진다. 즉, 먼저 들어온 것이 먼저 나가는 구조이다.

큐의 예로는 은행에서 쉽게 볼 수 있는 번호표가 있다. 먼저 온 손님이 먼저 은행업무를 볼 수 있다.

큐에서는 맨 처음 위치와 맨 마지막 위치만 기억하면 쉽게 해결이 된다.

이 위치를 큐에서는 front, rear라고 한다.

위 그림에 Deletion, Insertion이라는 용어가 있다. 보통 큐에서 Dequeue, Enqueue라는 용어를 많이 쓰는데,

Enqueue = Insertion 

Dequeue = Deletion 

은행에서 보면 먼저 온 사람들은 이미 번호표를 받았기 때문에 마지막에 온 사람에게 번호표를 주기 때문에 rear부분에 Enqueue가 들어가게 된다.

(1) Enqueue(삽입)  : 큐 맨 뒤에 요소를 추가, rear부분에서 발생되며 데이터가 삽입 될 때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

(2) Dequeue(삭제) : 큐 맨 앞에 요소를 삭제, 큐에서 데이터를 제거하는 작업이며 front에서 발생한다. front가 가리키는 데이터를 꺼낸 후 front 값을 하나 증가 시키도록 구현한다. front 값이 rear값을 추월하면 더이상 제거할 데이터가 없는 빈 큐가 된다.

(3) Peek(읽기) : front에 위치한 데이터를 제거하지 않고 읽음

(4) front : 큐의 맨 앞에 위치 (인덱스)

(5) rear : 큐의 맨 뒤에 위치 (인덱스)

스택과 마찬가지로 배열과 연결리스트를 이용해 구현할 수 있다. 배열과 연결리스트 모두 장단점이 존재하기 때문에 상황에 맞게 사용하면 된다.

1. 배열을 이용한 큐

가장 먼저 삽입한 데이터이며 데이터를 추출할 때 사용할 인덱스인 front와 마지막에 삽입한 데이터를 가리키는 rear,

큐의 최대 크기인 maxSize, 실제 데이터를 저장할 배열 queueArray를 선언하고 초기화한다.

empty() 메소드는 front가 rear를 추월할 때 발생한다. 추월했을 경우 더이상 데이터가 없으므로 true를 반환한다.

full() 메소드는 데이터를 저장할 위치인 rear가 배열의 크기에 도달했을 때 true를 반환해 배열이 다 찼음을 의미한다.

insert() 메소드는 리스트에 데이터를 삽입하는 메소드로 rear값을 하나 증가시키고 rear위치에 삽입할 데이터를 지정한다.

peek() 메소드는 리스트의 데이터 중 먼저 삽입된 데이터를 가리키는 front에 위치한 데이터를 꺼내 반환하고,

remove() 메소드는 peek() 메소드를 통해 데이터를 하나 반환하고 front를 하나 증가시키면서 데이터 삭제를 수행한다.

단점 : 배열의 크기가 고정되어있고, 데이터의 삽입 삭제가 반복 될 수록 rear, front가 계속 증가되어 이미 꺼낸 데이터가

들어있던 배열의 인덱스를 다시 쓸 수 없다. 그리고 데이터가 다 차있지 않아도 rearm front가 증가하다 배열의 사이즈까지

도달해 더이상 사용할 수 없게된다.

이러한 문제점을 해결하기위해 원형 큐를 사용해 구현한다.

2. 연결 리스트를 이용한 큐의 구현

front 노드는 리스트 중 가장 먼저 삽입한 노드이며 데이터를 삭제하거나 꺼낼 노드를 의미하고

rear 노드는 가장 최근에 삽입한 노드를 의미한다.

front와 rear의 초기값은 null 이고 front가 null 값을 가질 경우 더이상 꺼낼 데이터가 없다는 의미다.

데이터를 하나 삽입 할 경우에는 노드를 먼저 생성 한 후 생성한 노드의 nextNode 값을 null로 지정하여 마지막 노드임을

표시하고 비어있는 큐였을 경우 front와 rear 값 모두 새로 생성한 노드를 지정하도록 한다.

만약 비어있지 않고 데이터가 있었을 경우에는 삽입하기 이전의 rear 노드의 nextNode값을 새로운 노드를 가리키도록

지정하고 새로운 노드가 rear 노드가 된다.

데이터를 꺼낼 때는 가장 오래된 노드인 front 노드의 data를 반환하도록 peek()메소드를 작성한다.

remove() 메소드는 front 노드를 삭제하고 반환하면 되는데 peek()를 호출하여 front 노드의 data를 반환하고

삭제될 노드의 nextNode가 새로운 front 노드가 된다.

만약 삭제한 노드가 마지막 노드였을 경우 큐에 더이상 데이터가 없으므로 rear 값도 초기화 시킨다.

Queue에 offer 메소드를 사용해서 뒤로 값을 추가 할 수 있습니다.
Queue에 element 메소드를 사용해서 맨 앞의 값을 가져 옵니다.
Queue에 poll 메소드를 사용해서 맨 앞의 값을 가져오고 Queue에서 제거합니다.
public static void main(String[] args) {
    Queue<String> queue = new LinkedList<String>();
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    queue.offer("d");
        System.out.println(queue);
    System.out.println(queue.element());
    System.out.println(queue);
    System.out.println(queue.poll());
    System.out.println(queue);
}
출력 결과는 아래와 같습니다.
[a, b, c, d]
a
[a, b, c, d]
a
[b, c, d]