큐(Queue)

큐의 개념

 

• 큐는 '줄을 서다'라는 뜻을 가지고 있다.
• 큐는 먼저 들어간 데이터가 먼저 나오는 자료 구조이다. = 선입선출 = FIFO
• 큐 삽입 연산: Enqueue(Add), 꺼내는 연산을 Dequeue(Poll)이라고 한다.
• 2, 5를 스택에 넣었을 경우엔 5가 먼저 나올 것이고
• 2, 5를 큐에 넣었을 경우엔 2가 먼저 나올 것이다. 헷갈리지 말기!

 

큐의 특성을 활용하는 분야

• 먼저 들어온 것을 먼저 처리하는 큐의 동작 방식은 프로그래밍 언어에서 많이 활용 중
• 대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용 됨 (식당에서 먼저 줄 선 사람이 먼저 들어가는 것과 같은 경우)
• ex) 작업 대기열: 네트워크 통신 시, 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다. 이때 큐를 활용할 수 있다.
• ex) 이벤트 처리: 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용한다.

 

큐의 ADT

• boolean isFull(): 큐에 들어있는 데이터 개수가 max인지 확인하여 boolean값을 반환한다.
• boolean isEmpty(): 큐에 들어 있는 데이터가 한 개도 없는지 확인
• void add(Item Type item): 큐에 데이터 add
• Item Type poll(): 큐에 처음 add한 데이터를 poll하고, 그 데이터를 반환함
• int front: 큐에서 가장 마지막에 poll한 위치를 기록
• int rear: 큐에서 최근에 add한 데이터의 위치를 기록한다.
• Item Type data[maxsize]: 큐의 데이터를 관리하는 배열. 최대 max개의 데이터를 관리

큐가 실질적으로 관리하는 데이터는 front의 다음부터 rear까지이다. 즉, 데이터의 공간은 4개인데, 큐가 관리하는 데이터는 3개이므로, 실질적으로는 메모리 공간을 낭비한 상황이다. 이렇게 된 이유는 큐가 한 방향으로 관리하고 있기 때문이다. 이렇게 되면 front 이전 공간을 활용하지 못한다. 다시 말해 front 이전을 기준으로 큐의 사용할 수 있는 부분과 , 사용할 수 없는 부분으로 나뉘게 된다.

>> 그래서 나온 것이 원형 큐이다. 이는 메모리 공간을 절약할 수 있다는 장점이 있으나, 코딩테스트에서는 자바 컬렉션에서 제공하는 Queue 인터페이스를 사용해도 충분하다.

 

큐 구현하기

• 큐를 간단하게 구현하는 방식
  • Queue 인터페이스 활용
  • ArrayDeque 클래스 활용

Queue 인터페이스 활용

• 구현체로 자주 사용하는 클래스는 ArrayDeque와 LinkedList가 있음.
• 단순 코테에서는 둘다 사용해도 괜찮으나, ArrayDeque를 더 많이 사용함.

 

덱을 큐처럼 활용하기

• 덱은 양 끝에서 삽입이나 삭제를 할 수 있는 큐를 구현한 것이다.
• 따라서 덱은 큐로도 나타낼 수 있고, 스택으로도 나타낼 수 있다.
• ArrayDeque로 덱을 사용할 때, Queue와 동일한 역할을 하는 add(), poll()이 있으나 양 끝에서 모두 삽입/삭제가 가능하다는 특징 때문에 왼쪽 오른쪽을 구분해주어야 한다.
• first: 왼쪽 / last: 오른쪽
• pollFirst(): 왼쪽으로 꺼내기/ addLast(): 오른쪽으로 넣기
• pollLast(): 오른쪽으로 꺼내기/ addFirst(): 왼쪽으로 넣기
• addFirst(): 왼쪽으로 넣기 / pollFirst(): 왼쪽으로 꺼내기 >> 스택으로 구현되는 형태