큐(queue)

'길게 늘어선 줄' 큐(queue)의 사전적 의미입니다.

밑에서 부터 자료(data)들을 쌓는 스택(stack)과는 달리 일렬로 저장하는 것이죠. 

이제부터 큐(queue)의 동작 원리 및 특징에 대해서 알아보겠습니다.

동작 원리

'가장 먼저 저장된 자료가 가장 먼저 뽑힌다.' 이것이 큐의 동작 원리입니다.

우리는 이것은 '선입선출'이라고 합니다. 영어로는 'FIFO(First In First Out)'라고 하죠. 

저장했던 순서 반대로 자료를 뽑을 수 있었던 스택과는 달리 큐에서는 저장했던 순서대로 자료를 뽑아서 활용할 수 있습니다.

				5
			4	4
		3	3	3
	2	2	2	2
1	1	1	1	1

1에서 부터 5까지 순서대로 큐에 저장하는 모습입니다. 빨간색으로 표현된 자료는 각 단계에서 가장 먼저 뽑을 수 있는 자료입니다. 스택과는 다르게 가장 밑에 있는 자료가 표시되었네요.

 

특징

큐에서도 스택에서와 마찬가지로 크게 두 가지 동작이 있습니다. pop과 push 입니다.

스택에서는 top 하나가 pop과 push를 담당했었는데 큐에서는 pop과 push가 발생하는 위치가 서로 다르기 때문에 두 개의 top이 필요합니다. 

하나는 pop을 위한 top으로 front, 다른 하나는 push를 위한 top으로 rear라고 합니다.

push원리는 stack과 동일합니다. 가장 끝에서 이루어지기 때문에 que에서는 rear(꼬리)라고 흔히 표시합니다.

pop은 가장 앞에서 이루어지기 때문에 흔히 front(앞)이라고 표시합니다.

큐 또한 배열과 연결 리스트를 활용해 구현할 수 있는 데요.

배열에서는 front, rear는 두 개의 index일 것이고, 연결 리스트에서는 두 개의 포인터가 되겠습니다.

 

배열

배열로 구현하는 큐 또한 정말 간편합니다.

front와 rear를 -1 또는 0으로 초기화 하느냐에 따라 살짝 차이가 있지만 저번 스택을 소개하는 글에서 다루었기 때문에 이번에는 0으로 초기했을 때만 다루겠습니다.

pop을 했을 때, 가장 먼저 저장되었던 '1'이 뽑힌 것을 확인할 수 있습니다. push는 스택과 큰 차이점이 없죠?

간단하게 코드만 확인하고 넘어가겠습니다.

push(data element){
	if(큐 범위 넘어가면)
    	return;
    
    queue[rear++] = element;
}
pop(){
	if(front >= rear) // rear가 front와 같거나 작으면 큐가 비어있는 것
    	return;
    
    return queue[front++];
}

 

연결 리스트

처음 rear와 front 포인터는 head 더미 노드를 가리키면서 시작합니다. 여기 까지는 스택과 같습니다.

스택에서는 head 노드 쪽으로 향했던 방향이었던 것과는 달리 큐에서는 반대 방향으로 진행합니다. push와 pop이 일어나는 노드가 rear와 front로 나뉘어졌기 때문이죠.

push할 때는 새로운 노드를 생성해서 rear가 가리키는 노드의 next를 새로운 노드를 가리키게 한 후, rear를 새로운 노드를 가리키게 합니다.

 

pop에서는 사실 front의 역할을 하기 때문에 head의 next가 가리키는 node의 next가 가리키는 node로 head를 연결하면 됩니다.

하지만 필요없는 메모리를 삭제하기 위해 front를 옮겨가면서 pop을 진행합니다.

 

push(data element){
	node* new_node;
    new_node = new node;
    
    new_node->elemnet = elemnet;
    
    rear->next = new_node;
    rear = new_node;
}

pop(){
	front = front->next;
    
    head->next = front->next;
    
    delete front;
	
    front = head;
}

 

지금까지 큐에 대해서 알아봤습니다.

사실 큐는 스택보다 자주 사용되는데요. 특히 bfs 알고리즘을 활용할 때, 자주 사용됩니다.

나중에 bfs 알고리즘을 다룰 때, 더 자세하게 설명하겠습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!