[코딩테스트] No.5 큐-7장

7-1. 큐의 개념

 

큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 

일상생활에서 줄 서는 것이 큐 구조이다. 먼저 선 사람이 먼저 들어간다. 

이런 큐의 특징을 선입선출, FIFO(First in First out) 이라고 한다. 

큐도 스택처럼 꺼내는 연산을 팝, 삽입하는 연산을 푸시라고 한다. 

 

*큐의 특성을 활용하는 분야 

 

큐의 동작 방식은 프로그래밍 언어에서 많이 활용된다. 대표적으로 여러 이벤트가 발생했을때 발생한 순서대로 처리가 필요할 때 큐가 활용된다. 작업 대기열이나 이벤트 처리의 경우 큐 구조로 처리된다. 

 

큐의 ADT(abstract data type, 추상자료형)

 

*연산

정의	설명
boolean isFull()	큐에 들어 있는 데이터의 개수가 maxsize인지 확인해서 boolean 값을 반환한다.   (꽉 찼으면 True, 아니면 False)
boolean isEmpty()	큐에 들어있는 데이터가 하나도 없는지 확인해서 boolean 값을 반환한다.  (비었으면 True, 아니면 False)
void push(ItemType item)	큐에 데이터를 푸시한다.
ItemType pop()	큐에서 마지막에 푸시한 데이터를 꺼내어 반환한다.

 

*상태

정의	설명
int front	큐에서 가장 마지막에 팝한 위치를 기록한다.  (꽉 찼으면 True, 아니면 False)
int rear	큐에서 최근에 푸시한 데이터의 위치를 기록한다.
ItemType data[maxsize]	큐의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

 

 

front는 큐의 앞, rear는 큐의 뒤를 의미한다. 

큐는 앞에서 데이터를 꺼내고(팝), 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞 뒤의 최종 데이터의 위치를 기억해야한다. 

초기에는 front와 rear모두 초깃값을 -1로 설정한다. 

 

*큐의 세부동작 이해하기 

 

푸시 연산 

1. isFull() 연산을 통해 현재 큐가 가득 찼는지 확인한다. 

2. 큐가 가득 차지 않았다면, rear을 +1 하고 다음 rear가 가리키는 위치에 값을 푸시한다. 

 

팝 연산

1. isEmpty() 연산을 통해 큐가 비었는지 확인한다. 해당 연산을 통해 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 팝하는 동작을 방지한다. 

2. 만약 큐가 비어있지 않다면 front을 +1 한다. 이렇게 하면 front, rear가 0으로 같아지고, 

3. isEmpty() 연산 시 큐가 빈것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다. 

 

front의 다음 부터 rear까지만 큐가 관리하는 데이터라고 생각해야 한다. 

이런식으로 큐를 관리하다보면, 실제 data 공간에 비해 큐가 관리하는 데이터가 줄어들게 되면 메모리 공간을 낭비한 상황을 만날 수 있다. 이렇게 된 이유는 큐를 한 방향으로 관리하기 때문이다. 이렇게하면, fornt 이전의 부분을 활용할 수 없게된다. 

 

이를 개선하기 위해 원형 큐를 사용한다. 

 

코딩테스트에서 파이썬을 사용하면 그냥 리스트만 사용해도 충분하게 이런 형태들의 큐를 사용할 수 있다. 

 

* 큐 구현하기 

 

큐를 간단하게 구현하는 방식은 크게 2가지가 있다. 

1. 리스트를 활용하는 방식

 

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거, 스택과의 차이는 pop()에 인수로 0을 넣어 맨 앞 데이터를 제거했다는 점이다
first_item = queue.pop(0)
print(first_item) # 출력: 1

 

2. 덱을 활용하는 방식

 

from collections import deque

queue = deque()

# 큐에 데이터 추가 
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item) # 출력: 1

 

 

실제로 큐를 구현할 때 덱을 사용하는 이유는 속도 때문이다. 

pop(0)을 10 만번하면 0.79초가 소요되고,

popleft()를 10 만번하면 0.007초로 매우 크게 차이가 난다. 

 

 

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)