[자료구조] 큐(Queue)란?

목표

순차적 자료구조인 큐의 개념에 대해서 알아보겠습니다.

 

개요

저번 포스팅에서는 순차적 자료구조인 스택에 대해서 알아보았습니다.

큐(Queue)는 스택과 비슷한 부분들이 많기 때문에 비교하면서 큐에 대해서 이해하는 시간을 갖도록 하겠습니다.

 

큐(Queue)란?

큐(Queue)는 스택과 비슷한 형태를 가집니다.

다만, 스택은 LIFO(Last In First Out) 구조로 마지막에 들어온 데이터가 제일 먼저 나가는 형태입니다.

큐는 FIFO(First In First Out) 구조로 맨 처음 들어온 데이터가 먼저 나가는 형태입니다. 예를 들어, 마트에서 줄 서는 것을 생각할 수 있겠네요.

 

스택에서는 Push, Pop, Len, Top 4가지 연산을 지원했습니다.

큐는 Enqueue, Dequeue, isEmpty, front, len 총 5가지 연산을 지원합니다.

Enqueue

매개변수를 큐의 가장 오른쪽(rear)에 추가합니다. 스택의 Push와 동일한 연산입니다.

Dequeue

가장 왼쪽의 값(제일 먼저 입력된 값)을 삭제 후 리턴합니다.

스택의 Pop 연산과 비슷하지만, 가장 왼쪽의 값을 삭제한다는 점에서 다릅니다.

isEmpty

큐가 비어있는지 확인합니다.

front

가장 왼쪽에 저장된 값을 리턴합니다. (삭제하지 않습니다.)

len

큐의 길이를 리턴합니다.

 

스택에서는 값을 실제로 제거하면서 리스트를 관리했습니다.

큐에서는 실제로 값을 제거하는 것이 아닌, 인덱스를 통해서 큐를 관리합니다. 인덱스를 옮겨서 값이 제거된 것을 나타냅니다.

 

디큐(Dequeue)

스택, 큐를 보다보면 왼쪽, 오른쪽 어디서든 값을 추가하고 제거할 수 있는 자료구조는 없을까? 하는 의문이 생깁니다. 이걸 가능하게 하는 것이 디큐(Dequeue)입니다. 값을 제거하는 Dequeue 연산과 이름이 같지만 여기서 말하는 디큐는 자료구조의 이름입니다.

파이썬에서는 collections라는 모듈에서 deque 클래스로 해당 자료구조를 지원하고 있습니다.

"덱(deck)"로 발음하며, 오른쪽에서 Push, Pop하는 것은 append, pop으로 동일하고, 왼쪽에서 Push, Pop하는 경우 appendleft, popleft로 left를 붙여주면 됩니다.

말로 설명하는 것 보다는 코드를 보는게 이해가 빠르니까 코드로 확인해보겠습니다.

 

▲ Deque (덱) 예시

▲ 결과

보시는 것처럼 편하게 사용할 수 있습니다.

 

코드

▲ 큐(Queue) 클래스

위와 같이 큐를 구현했습니다. 

스택과는 달리 front_index를 통해서 큐를 관리하는 모습을 확인할 수 있습니다.

각 코드의 시간 복잡도는 O(1) 입니다.(탐색 제외)

 

수정 : isEmpty 함수의 주석에 길이를 출력한다고 적어놨는데, 출력이 아니라 리턴입니다!

 

정리

기본적인 개념은 스택과 비슷하기 때문에 크게 다룰 내용은 없었습니다.

관련된 예제로 josephus problem(요세푸스 문제)를 풀어볼 예정입니다. 해당 문제를 백준에서 찾았기 때문에 알고리즘 게시판에 작성하도록 하겠습니다.

 

*한국외대 신찬수 교수님의 Data Structures with Python 강의를 참고하여 포스팅하였습니다.