큐(Queue)란,
영어 단어 'queue'는 마트에서 계산을 위해 줄을 서거나 번호표를 뽑고 줄서서 기다릴 때와 같이 이러한 '줄'을 의미하는 단어다. 자료구조에 이 큐를 접목시키면, 스택과 정반대로 가장 먼저 들어온 것이 가장 먼저 나가는, FIFO(Fisrt-in, First-Out), 선입선출의 특징을 지닌다.
큐의 개념과 원리
큐의 맨 앞에 있는 원소를 front라고 하고, 맨 뒤에 있는 원소를 tail이라고 한다. 큐에서 삽입할 때는 삽입할 원소를 지정해 주어야 하지만, 삭제할 경우에는 스택과 마찬가지로 삭제할 원소를 명시할 필요 없이 맨 앞에 있는, 가장 먼저 삽입된 원소를 삭제하면 된다.
큐에서 주로 나오는 핵심 작업들은 다음과 같다.
맨 끝에 원소를 추가 enqueue()
맨 앞의 원소를 삭제하여 알려줌 dequeue
맨 앞의 원소를 알려줌 front()
큐가 비어 있는지 확인 isEmpty()
큐를 깨끗이 비움 dequeueAll()
배열을 이용한 큐의 작업
큐의 최대 크기를 예상할 수 있는 경우에는 배열이 가장 적합하지만, 크기를 예상할 수 없는 경우에는 더 큰 배열을 할당받아 옮기는 작업을 해주어야 한다.
큐를 생성하기 위해서는 먼저 큐를 초기화 해주어야 한다. 큐의 총 원소 수를 지정해줄 변수를 하나 지정해주고, front와 tail 변수를 지정해주어 원소가 삽입될 때 마다 tail이 1씩 증가하고, 삭제될 때마다 front가 1씩 증가하게 한다. tail이 지정된 배열의 끝에 오게 되면 큐가 꽉찬 상태로 여겨지게 되는데, 여기서 공간 사용이 비효율이 발생한다.
이 문제를 해결하기 위해서는 배열을 '원형'으로 해석하면 된다.
원형 큐(Circular Queue)란,
이런 식으로 원형 큐란 배열을 원 모양으로 둥글게 말은 형태를 상상하면 이해하기 쉽다. 이는 앞서 말한 배열을 이용한 큐의 공간 사용의 비효율성 문제를 해결할 수 있는 자료구조 형태이다. rear(tail)이 배열의 마지막에 도달했다고 해도 배열의 맨 앞(front)의 원소가 빠져서 빈 공간이 생기면 rear은 다시 처음으로 돌아와 0의 자리에 원소를 저장할 수 있다.
공간이 허락하는 한 원형 큐는, 데이터를 빠르게 처리할 수 있다.
데이터를 삽입할 때는 front의 값은 변함이 없고, tail의 값만 증가하게 되고, 삭제 시에는 front의 값이 증가한다.
연결 리스트를 이용한 큐
연결 리스트에는 단방향, 양방향, 원형, 데미 헤드 등 다양한 형태의 연결 리스트가 존재하는데, 그 중 단방향 원형 연결 리스트의 경우에는 맨 뒤의 노드에 대한 레퍼런스만 있으면 관리할 수 있다. 레퍼런스 tail이 리스트의 마지막 노드를 가리키고 원형이므로 리스트의 첫번째 노드 또한 접근 가능하다.
- 원소 삽입
큐에 원소를 삽입할 때는 큐의 자료구조 원칙에 따라 맨 뒤에 넣는다. tail뒤에 원소를 삽입하고, 레퍼런스 tail이 새 노드를 가리키도록 바꾸어준다. 그리고 삽입된 새 노드는 리스트의 첫 번째 노드로 연결시킨다.
연결 리스트는 크기가 고정되 있는 배열과 달리 노드를 새로 할당받을 수 있기 때문에 항상 새 원소를 삽입할 수 있다는 장점이 있다.
- 원소 삭제
원소 삭제할 때는 큐의 자료구조 원칙에 따라 맨 앞의 원소를 삭제한다. front노드를 삭제 후, tail 노드가 가리키던 front노드의 링크를 front노드의 다음 노드를 가리키도록 바꾼다. 원형으로 연결되어 있으므로 tail 노드의 다음 노드가 front 노드가 된다.
삭제 작업의 기본 전제는 큐가 비어있는지, 큐의 원소가 하나밖에 없는지를 확인해야 한다는 것이다. 원소가 하나뿐이면 위의 작업을 실행하기 위해 작성한 코드는 작동하지 않을 수 있기 때문에 필수적으로 큐가 비어있는지 확인해야 한다.
큐와 스택을 이용한 좌우동형 문자열 체크
좌우동형 문자열이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다. 굳이 큐를 쓰지 않고도 좌우동형 문자열인지 체크할 수 있는 방법은 있지만, 큐와 스택을 활용해서도 이를 수행할 수 있다.
임의의 문자열을 받고, 해당 문자들을 앞에서부터 읽으면서 스택과 큐에 동시에 저장한다. 끝까지 저장한 다음 스택과 큐에서 동시에 하나씩 읽어들이면서 읽어들인 문자가 동일한지를 확인한다. 이게 동일하다면 계속 읽어들이고, 중간에 큐가 비면 중단하는데, 큐가 비어서 중단했다면 좌우동형이라고 판단을 내리면 된다.
