[코딩테스트 합격자 되기 07] 큐

https://product.kyobobook.co.kr/detail/S000210881884

코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고

 

큐

- 선입선출

- 스택과 마찬가지로 삽입하는 연산을 푸시, 꺼내는 연산을 팝

 

 

큐의 특성을 활용하는 분야 

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용된다. 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용된다. 그 밖의 큐의 특성을 활용한 분야는 다음과 같다. 

• 작업 대기열 : 네트워크 통신시 다수의 클라이어트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때.

 

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환
	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환 (front , rear의 값이 같은지 확인하여 큐에 원소가 없는데 팝 하는 동작을 방지)
	void push(itemType item)	큐에 데이터 푸시
	itemType pop()	큐에서 마지막에 푸시한 데이터를 팝하고, 그 데이터를 반환
정의	int front()	큐에서 가장 마지막에 팝한 위치를 기록
	int rear	큐에서 최근에 푸시한 데이터의 위치를 기록
	itemType data[maxsize]	큐의 데이터를 관리하는 배열, 최대 maxsize개의 데이터 관리

 

큐의 ADT

 

앞서 스택에서 제시했던 그림이므로 쉽게 이해할 수 있다. 하지만 달라진 점은 스택의 top이 front 와 rear로 바뀐 것이다. front 는 큐의 앞, rear는 큐의 뒤를 의미한다. 큐는 앞에서 데이터를 빼고(팝) 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞과 뒤 데이터의 최종 위치를 기억할 변수가 필요하다. 지금의 경우 아무런 데이터도 넣지 않은 상태가 아니므로 front 와 rear모두 -1이다.(배열의 인덱스는 0부터 시작하므로 아무것도 넣지 않은 상태를 표현하기 위해 초깃값을 -1로 설정)

 

1. Push : isFull 연산으로 큐가 가득 찼는지 확인하고, 가득 차지 않았다면 rear을 +1 한 다음 rear 가 가리키는 위치에 3을 푸시

 

 

2. Pop

isEmpty 연산을 통해 큐가 비었는지 확인하고, 만약 비어있지 않다면 front를 +1한다. 이렇게 하면 front, rear가 0으로 같아지므로 isEmpty() 연산시 큐가 빈 것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다.

 

 

 

3. 다시 Push

isFull 연산을 수행해 큐가 가득 찼는지 검사하고, 가득 차지 않았다면 푸시한다. 만약 두 개의 데이터를 연달아 push 한다면 front 는 0, rear는 3이 된다. 

 

 

 

4. 큐가 가득 찼을 때 push 하는 경우

rear가 3(maximize -1)이므로 isFull연산은 True가 되어 push 하지 못한다.

큐가 가득 찬 연산에서는 생각해볼 것이 있다. 마지막 푸시에서 실제 data에 저장한 데이터는 3,5,6,8 로 4개이지만, 큐는 5,6,8로 3개이다. 다시말해 큐는 front 의 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 한다. 하지만 실제 data의 공간은 4개인데, 큐가 관리하는 데이터는 3개이므로 실질적으로는 메모리 공간을 낭비한 셈이다. 이렇게 된 이유는 큐를 한방향으로 관리하고 있기 때문이다. 이렇게 하면 front 이전의 공간을 활용하지 못한다. 다시 말해 front 이전을 기준으로 큐의 사용할 수 있는 부분과, 사용할 수 없는 부분이 나뉘었다. 

 

큐를 원형으로 계산하기
이를 개선하려면 책에서 설명한 형태의 큐가 아니라 다른 형태의 큐가 필요하다. 낭비하는 공간을 없애기 위해 원형으로 front 와 rear가 돌아간다. 원형 큐는 조금 복잡하지만 메모리 공간을 절약할 수 있다는 장점이 있다. 그러나 파이썬에서는 리스트의 길이를 자동으로 관리하기 때문에, 메모리를 효율적으로 쓰기 위해 원형 큐를 사용하거나 할 필요는 없다. 

 

 

 

리스트를 큐처럼 활용하기

푸시는 append(), 팝은 pop()연산을 활용한다. 스택과의 차이점이 있다면 pop() 메서드에 인수로 0을 넣었다는 점이다. pop()메서드에 인수를 넣지 않으면, 맨 뒤의 원소가 삭제된다. 

queue = [ ]

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

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

#큐에 데이터 추가 
queue.append(4)
queue.append(5)

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

 

* pop(0)의 cost가 실제로는 O(n)이 걸릴 수 있다. 게시글 하단 참고 

 

덱을 큐처럼 활용하기 

덱은 Double Ended Queue 를 줄인 말로, 말 그대로 양 끝에서 삽입이나 삭제를 할 수 있는 큐를 구현한 것이다. 양 끝에서 삽입과 삭제를 구현할 때는 덱을 사용하는 것이 좋다. 

from collections import deque

queue = deque()

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

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

#큐에 데이터 추가
queue.append(4)
queue.append(5)

#큐의 맨 앞 데이터 제거
fisrt_item = queue.popleft()
print(first_item) #2

 

 

* 참고 : pop vs popleft

list.pop (0) 과 deque.popleft() 의 차이는 시간이다. 

 

• pop : 리스트의 마지막 원소 삭제의 시간복잡도는 O(n)이지만, 특정 인덱스의 원소를 삭제하기 위해서는 그 원소 뒤의 모든 원소들을 한 칸씩 옮겨야 하기 때문에 시간복잡도는 O(n)이다.
• popleft : front += 1의 연산만을 수행하기 때문에 o(1)의 빠른 복잡도로 원소 삭제가 가능하다. 

from collections import deque
import time

lst = list(range(100000))
dq = deque(range(100000))

start_time = time.time()
for i in range(100000):
    lst.pop(0)
print("pop(0)소요시간 : ", time.time() - start_time)

start_time = time.time()
for i in range(100000):
    dq.popleft()
print("deque의 popleft소요시간 : ", time.time() - start_time)


# pop(0)소요시간 :  0.770686149597168 
# deque의 popleft소요시간 :  0.009191751480102539

 

위 예시에서 pop(0)을 10만번 한 결과는 0.97초, popleft()를 10만번 수행한 결과는 0.007초로 매우 크게 차이가 난다. 

하지만 deque 는 list 처럼 인덱스를 통한 접근이 불가능 하기 때문에 중간에 있는 값에 접근하려면 list를 사용하는 것이 훨씬 효율적이다.

 

ref : https://velog.io/@yoouung/Python-pop0-vs.-popleft