개요
큐란 대표적인 선입선출(First In First Out, FIFO)형 자료구조이다. 선입선출이란 먼저 들어온 것이 먼저 나간다는 것을 뜻한다.
데이터를 반드시 입력한 순서대로 처리해야 할 때 큐를 사용한다. 보통은 데이터를... 순서대로 처리하므로... 큐는 정말 다양한 상황에서 쓸 수 있다.
주요 메소드
기본적으로 다음과 같은 기능을 가진다.
Enqueue()
큐에 데이터를 추가하는 것을 의미한다. 데이터는 항상 큐의 마지막 위치에 추가된다.
항상 마지막 위치에 추가되므로, 복잡한 연산이 필요없다. 따라서 항상 O(1)의 시간복잡도를 가진다.
Dequeue()
큐에서 데이터를 꺼내는 것을 의미한다. 데이터는 항상 큐의 첫번째 위치에서 꺼낸다. (스택처럼 마지막 위치에서 꺼내지 않는다!)
Enqueue와 마찬가지로 항상 처음 위치의 데이터를 꺼내기 때문에 복잡한 연산이 필요없다. 그렇기에 O(1)의 시간복잡도를 가진다.
Front()
큐의 가장 첫 위치에 존재하는 데이터를 조회한다. Dequeue처럼 데이터를 꺼내지는 않는다.
A, B, C, D의 데이터가 들어있는 큐에서, Enqueue과 Dequeue를 차례대로 연산하면 다음과 같은 그림이 나온다.
가장 먼저 들어갔었던 A가 꺼내지게 되고, 이후 E는 배열의 맨 마지막에 들어간다. 이후 Dequeue를 계속하면 B, C, D, E의 순서대로 꺼내게 된다.
어떤 때에 쓰이나
순서대로 일을 처리해야하는 모든 기능에 큐를 사용할 수 있다. 순서대로 처리한다는 것은 결국 줄을 세운다는 것이나 마찬가지다.
네트워크 상에서 데이터를 주고 받을때 큐를 사용한다. 이렇게 주고 받는 데이터를 패킷이라고 하는데, 다수의 접속자에게서 무분별하게 오는 패킷을 서버에서는 순서대로 받고, 그 순서에 맞춰 상응하는 패킷을 보낼 필요가 있다. 티켓팅을 하는데 늦게 접속한 사람이 먼저 자리를 잡아버리는... 그런 불공정한 일을 막기 위해 쓰인다고 생각하면 좋다.
