13. 큐(queue ADT) 파이썬(with Python)

큐는 리스트의 일종으로 뒷부분에 데이터가 삽입되고 앞부분에서는 데이터가 삭제되는 자료구조입니다. 

 

간단히 선입 선출 (FIFO = First-in first-out)이라고 하죠. 

 

컨베이어 벨트를 떠올리시면 이해가 쉬울 겁니다. 

 

프린터 스풀러나, 운영 체제의 프로세스 처리 순서 등에서 많이 쓰이죠. 

 

 

큐의 뒤(rear, tail, back)에 요소를 삽입하는 것을 enqueue(put, insert) 큐의 앞(front, head)에서 요소를 제거하는 것을 dequeue(get, delete)라고 합니다. 

* dequeue에는 두 가지 의미가 있습니다. double ended queue 양 끝을 가지는 큐, enqueue의 반대(요소 제거)

그리고 보통 디큐로 발음합니다. 특히 인큐의 반대말로 쓰였을 때는 디큐가 맞겠죠? https://en.wiktionary.org/wiki/dequeue#English

 

또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우를 언더플로우(Underflow)라고 합니다.

 

List 기반의 Queue 클래스 구현

 

참고) 리스트를 큐로 사용하는 것은 효율적이지 않습니다. 리스트의 끝에 요소를 덧붙이거나 꺼내는 것과 달리, 리스트의 머리에 요소를 덧붙이거나 머리에서 꺼내는 것은 느립니다(다른 요소들을 모두 한 칸씩 이동시켜야 하기 때문입니다).

https://docs.python.org/ko/3/tutorial/datastructures.html#using-lists-as-queues

 

리스트로 리스트를 만드는 삽질도 했는데.... 리스트로 큐를 만드는 정도야 애교죠?

 

실제 프로젝트에서는 collections.deque 를 사용하시면 됩니다. 

 

class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, element):
        self.data.append(element)

    def dequeue(self):
        return self.data.pop(0)

    def front(self):
        return self.data[0]

    def back(self):
        return self.data[-1]  # return self.data[len(self.data)-1]
        # 마지막 요소는 [-1]로 접근하는 것이 편합니다.

    def is_empty(self):
        return len(self.data) == 0

    def show(self):
        print(self.data)

boo = Queue()
for i in range(4):
    boo.enqueue(i)
boo.show()
print('front', boo.front())
print('back', boo.back())
print(boo.is_empty())
print(boo.dequeue())
print(boo.dequeue())
print(boo.dequeue())
boo.show()
print(boo.dequeue())
print(boo.is_empty())

[0, 1, 2, 3]
front 0
back 3
False
0
1
2
[3]
3
True

 

collections.deque를 이용해서 코딩한다면.. 

from collections import deque

boo = deque()
for i in range(4):
    boo.append(i)
print(boo)
print('front', boo.index(0))
print('back', boo.index(len(boo) - 1))
print(len(boo) == 0)
print(boo.popleft())
print(boo.popleft())
print(boo.popleft())
print(boo)
print(boo.popleft())
print(len(boo) == 0)

deque([0, 1, 2, 3])
front 0
back 3
False
0
1
2
deque([3])
3
True

 

번외편 "가독성"

def is_empty(self): 
    return len(self.data) == 0

'self.data 의 길이가 0 인지를 리턴하라.' 라고 간결하게 한 문장으로 해석이 됩니다. 
가독성이 좋습니다. 

 

이 부분을 if else를 써서 코딩해보겠습니다. 

def is_empty(self): 
    if len(self.data) == 0:
        return True
    else:
        return False

쓸데없이 길고 가독성도 별로죠?

 

def is_empty(self):
    return not self.data

파이썬에서는 위의 예처럼 간결하게 코딩하는 게 추천됩니다. 
사실 저도 입문한 지 몇 달 안되어 아직 어색합니다. ㅠ,.ㅠ