[자료구조]큐

큐

정의: 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조.

동작: 먼저 들어온 데이터가 먼저 나가는 형식, 선입선출의 자료구조

동작 방법

숫자 5, 10, 2, 7을 순서대로 큐에 삽입하면 아래와 같은 그림으로 들어간다.

큐의 삽입

먼저 들어간 5가 큐의 맨 앞에 자리하고 그 뒤로 10-2-7이 이어서 저장되어 있다.

이제 큐를 비우기 위해 저장된 모든 데이터들을 삭제해보면 아래 그림과 같이 동작한다.

큐의 삭제

맨 먼저 큐에 삽입된 5가 가장 먼저 큐에서 삭제되고 삽입 순서인 10-2-7이 순서대로 큐에서 삭제된다.

 

이처럼 큐는 먼저 들어간 데이터가 먼저 삭제되는 것을 알 수 있다.

큐의 연산

큐는 스택과 달리 deque 라이브러리를 사용하는데 이는 시간 복잡도가 증가하는 것을 방지하기 위한 것이다.

from collections import deque

삽입 연산: 큐에 새로운 데이터를 삽입하는 연산이다. 스택과 마찬가지로 append()를 사용한다. append()는 오른쪽에 새로운 데이터를 추가한다.

삭제 연산: 큐에 가장 먼저 삽입된 데이터를 삭제하는 연산이다. 스택과 달리 deque 라이브러리에 존재하는 popleft()를 사용한다. popleft()는 왼쪽에서 데이터를 삭제한다.

실습

큐의 동작을 파이썬을 사용해서 실습해보자.

아래의 순서대로 코드를 진행할 때 큐에 존재하는 데이터와 삭제되는 데이터의 값을 예측해보고 비교해보자.

 

1. 숫자 20, 3, 100, 50, 7을 순서대로 큐에 삽입하자.

2. 큐의 삭제 연산을 2번 수행하자.

3. 숫자 200을 큐에 삽입하자.

4. 큐의 삭제 연산을 3번 수행하자.

 

예상)

1. 큐에 가장 먼저 들어간 20이 맨 앞에 그 뒤를 3-100-50-7이 이어서 저장되어 있을 것이다.

2. 20과 3이 삭제되어 큐의 맨 앞에는 100이 있고 그 뒤를 50-7이 이어서 저장되어 있을 것이다.

3. 200이 큐의 맨 뒤에 삽입되어 100-50-7-200 순으로 큐에 저장되어 있을 것이다.

4. 큐의 맨 앞에 존재하는 100과 50, 7이 순서대로 삭제되어 큐에 200만 존재할 것이다.

 

코드)

## 큐를 사용하기 위해 deque 라이브러리 import
from collections import deque

## 큐를 구현하기 위해 deque 라이브러리 사용
queue = deque()

큐는 dequq 라이브러리를 사용하므로 import 한 후 deque를 사용했다.

## 1. 숫자 20, 3, 100, 50, 7을 순서대로 큐에 삽입하자.
queue.append(20)
queue.append(3)
queue.append(100)
queue.append(50)
queue.append(7)

print(queue)

## 출력값
deque([20, 3, 100, 50, 7])

가장 먼저 큐에 삽입한 20이 큐의 맨 앞에 존재하고 3-100-50-7이 이어서 큐에 존재한다. 예측한 것과 일치하다.

## 2. 큐의 삭제 연산을 2번 수행하자.
queue.popleft()
queue.popleft()

print(queue)

## 출력값
deque([100, 50, 7])

큐의 앞에 존재하는 2개의 데이터가 삭제되었다. 예측한 결과와 일치하다.

## 3. 숫자 200을 큐에 삽입하자.
queue.append(200)

print(queue)

## 출력값
deque([100, 50, 7, 200])

큐의 맨 뒤에 200이 삽입되었다. 예측한 결과와 일치하다.

## 4. 큐의 삭제 연산을 3번 수행하자.
queue.popleft()
queue.popleft()
queue.popleft()

print(queue)

## 출력값
deque([200])

큐의 앞에 존재하는 3개의 데이터가 삭제되었다. 예측한 결과와 일치하다.

정리

1. 큐는 선입선출로 동작하는 자료구조이다.

2. 큐를 사용하기 위해 deque 라이브러리를 사용하면 편리하다.