큐(Queue)

큐(Queue)란?

---

큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 자료구조이다.

 

이러한 특징을 선입선출 또는 FIFO(FirstInFirstOut)이라고 한다.

 

큐에 데이터를 삽입하는 것을 Enqueue(add)라고 하고 큐로부터 데이터를 꺼내는 것을 Dequeue(poll)라고 한다.

 

큐의 ADT

메서드	설명
boolean isFull()	큐에 들어가 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환한다.
boolean isEmpty()	큐에 데이터가 없는지 확인해 boolean 값을 반환한다.
void add(ItemType item)	큐의 데이터를 삽입한다(Enqueue)
ItemType poll()	큐의 데이터를 꺼내고 그 데이터를 반환한다(Dequeue)

 

변수	설명
int front	큐에서 가장 마지막에 저장된 데이터를 가리킨다.
int rear	큐에서 가장 최근에 저장된 데이터를 가리킨다.
ItemType data[maxsize]	큐의 데이터를 관리하는 배열

 

Enqueue 세부 동작 방식

최초 큐의 front, rear는 -1이다.

1. 먼저 isFull()을 호출해 큐가 꽉차있는지 확인한다.
   • Rear = MaxSize - 1이면 큐는 꽉차있다는 의미이다.
2. 큐가 꽉차있지 않다면 add(data)를 통해 데이터를 삽입한다.
3. 데이터를 삽입한 뒤 Rear에 1을 더해준다.

 

Dequeue 세부 동작 방식

 

 

1. 먼저 isEmpty()를 호출해 큐에 데이터가 비어있는지 확인한다.
   • Rear == Front이면 비어있다는 의미이다.
2. 큐가 비어있지 않다면 poll()를 통해 가장 마지막에 저장된 데이터를 삭제한다.
3. 데이터를 삭제한 뒤 Front에 1을 더해준다.

 

Queue의 문제점

위의 상황 이후에 데이터가 4개가 추가됐다.

• 이후에 데이터를 하나 더 추가하려 했는데 Rear의 값이 MaxSize-1이 돼 isFull()이 true가 반환돼 실패했다.
• 분명 0번 인덱스에는 데이터가 없지만 큐는 꽉차있는 상태가 되어버린다. --> 메모리의 낭비 발생

 

이러한 문제를 해결하는 것이 Circular Queue이다. 

 

Circular Queue

• Circular Queue는 원형 모양의 Queue이다.
• 최초 Circular Queue의 Front, Rear는 0이다.

Enqueue

• Queue일 때와 똑같이 Rear에 1을 더한다.
• 단 Rear가 MaxSize-1일 때는 Rear에 (Rear+1) % MaxSize를 넣는다.
  • 위의 상황에선 4 --> 0

Dequeue

• Queue일 때와 똑같이 Front에 1을 더한다.
• 단 Front가 MaxSize-1일 때는 Front에 (Front+1) % MaxSize를 넣는다.
  • 위의 상황에선 4 --> 0

isEmpty()

• Queue와 똑같이 Front == Rear 일 때, 비어있다고 판단한다.

isFull()

• Queue와는 달리 (Rear + 1) % MaxSize == Front 일 때, 꽉찼다고 판단한다.
• 이를 통해 메모리 낭비 없이 데이터를 저장할 수 있다.

자바의 큐(Queue) 클래스

---

자바에서 큐를 사용하는 방법은 크게 두 가지가 있다.

첫 번째는 Queue 인터페이스를 활용하는 방식,

두 번째는 ArrayDeque 클래스를 활용하는 방식이다.

💡자바에서는 Queue 크기를 동적으로 조절하기 때문에 Circular Queue를 사용하지 않아도 된다.
     이 때문에 isFull() 메서드도 존재하지 않는다.

Queue 인터페이스

Queue<ItemType> queue = new ArrayDeque<>();

주요 메서드	설명
boolean isEmpty()	큐에 데이터가 없는지 확인해 boolean 값을 반환한다.
void add(ItemType item)	큐의 데이터를 삽입한다.(Enqueue)
void offer(ItemType item)	큐의 데이터를 삽입한다.
ItemType remove()	큐의 데이터를 꺼내고 그 데이터를 반환한다.
ItemType poll()	큐의 데이터를 꺼내고 그 데이터를 반환한다.
ItemType peek()	큐의 Head에 있는 데이터(가장 처음으로 저장된 데이터)를 반환한다.(꺼내진 않음)
ItemType element()	큐의 Head에 있는 데이터(가장 처음으로 저장된 데이터)를 반환한다.(꺼내진 않음)

• Queue 인터페이스의 구현체로 ArrayDeque를 사용했다.
  • LinkedList를 사용할 수도 있지만 코딩테스트에선 일반적으로 ArrayDeque 사용
• add()와 offer의 차이?
  • add(): 큐가 꽉차면 예외 발생
  • offer(): 큐가 꽉차면 false를 반환
• remove()와 poll()의 차이?
  • remove(): 큐가 비어있다면 예외 발생
  • poll(): 큐가 비어있다면 null을 반환
• peek()와 element의 차이?
  • peek(): 큐가 비어있다면 null을 반환
  • element(): 큐가 비어있다면 예외를 반환

ArrayDeque 클래스

ArrayDeque<ItemType> queue = new ArrayDeque<>();

주요 메서드	설명
void add(ItemType item)	Deque의 데이터를 삽입한다(Enqueue)
void addFirst(ItemType item)	Deque의 앞에 데이터를 삽입한다.
void addLast(ItemType item)	Deque의 끝에 데이터를 삽입한다.
ItemType poll()	Deque의 데이터를 꺼내고 그 데이터를 반환한다(Dequeue)
ItemType pollFirst()	Deque의 첫 데이터를 꺼내고 반환한다.
ItemType pollLast()	Deque의 첫 데이터를 꺼내고 반환한다.

• ArrayDeque는 스택처럼도, 큐처럼도 사용할 수 있는 자료구조이다.
• addLast(), pollFirst()는 각각 add(), poll()과 기능상으로는 동일하지만 메서드의 이름 덕분에 더욱 직관적으로 이해할 수 있다.

 

연습문제

---

 

[프로그래머스] 요세푸스 문제

 

해당 포스트는 『코딩 테스트 합격자 되기 - 자바편』을 참고하여 작성되었습니다.