1큐와 스택

 

이번에 살펴볼 큐와 스택은 컴퓨터 과학에서 다루는 여러 가지 자료 구조 중에서도 가장 기본적인 것입니다. 두 자료 구조는 ‘자료를 넣는 동작’과 ‘자료를 빼는 동작’을 할 수 있으며, 들어간 자료가 일렬로 보관된다는 공통점이 있습니다. 하지만 자료를 넣고 뺄 때 동작하는 방식이 서로 다릅니다.

구체적인 예를 들어 설명해 보겠습니다.

 

◼︎ 큐

큐(queue)는 ‘줄 서기’에 비유할 수 있습니다. 택시를 타기 위해서 줄을 서는 과정을 떠올려 봅시다. 새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고, 택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시를 탑니다. 가장 먼저 줄을 선 사람이 가장 먼저 택시를 타게 됩니다(First In First Out).

 

그림 13-1 큐: 택시 정류장에서 줄 서서 택시 타기

 

큐에 자료를 한 개 집어넣는 동작을 ‘인큐(enqueue)’, 큐 안에 있는 자료를 한 개 꺼내는 동작을 ‘디큐(dequeue)’라고 표현합니다.