[CS] 큐(Queue)란 무엇인가?

큐(Queue)

큐는 ‘줄을 서서 기다리다.’, ‘대기행렬’이라는 의미를 가진다. 마치 영화표를 예매하기 위해 줄을 서서 기다리는 것과 비슷한 형태의 자료구조이다. 프로그래밍에서도 마치 데이터가 영화표를 예매하기 위해 큐라는 자료구조에 줄을 서서 대기한 다음, 예매를 성공한 데이터부터 빠져나가는 것이다.

또한 실생활에서 톨게이트를 지나가는 자동차와 빗대어 표현할 수도 있다.

 

따라서 큐는 스택과 반대되는 개념으로 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출(FIFO : First In First Out) 구조로 되어 있어, 프로그래밍에서의 큐 자료구조는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.

 

큐의 특징

선입선출 (FIFO : First In First Out)

먼저 들어간 데이터가 먼저 나오는 선입선출 구조를 가지고 있다. 자바 언어에서 표현하는 큐는 다음과 같다.

// 큐 선언
Queue<Integer> queueEx = new LinkedList<>();

// 큐에 데이터 삽입
queueEx.push(1);
queueEx.push(2);
queueEx.push(3);
queueEx.push(4);
queueEx.push(5);
// 1, 2, 3, 4, 5 순으로 저장된다.

// 큐에서 데이터 꺼내기
queueEx.pop();
queueEx.pop();
queueEx.pop();
queueEx.pop();
queueEx.pop();

// 1, 2, 3, 4, 5 순으로 나온다.

 

데이터는 하나씩 넣고 뺄 수 있다.

큐는 스택과 마찬가지로 데이터가 아무리 많이 있어도 데이터를 하나씩 넣고 뺄 수 있다. 한 번에 여러 데이터를 넣거나 뺄 수 없다.

 

두 개의 입출력 방향을 가지고 있다.

한 개의 입출력 방향을 가지고 있는 스택과는 다르게 큐는 데이터의 입력과 출력의 방향이 다르다. 한쪽으로 데이터가 들어오면, 반대쪽 방향에서 빠져나간다.