[Python] 큐 구현

스택과 마찬가지로 파이썬에서는 데큐를 이용하면 큐의 기능을 모두 사용할 수 있다. enqueue 연산은 append로, deque 연산은 popleft를 사용하면 된다.

여기서는 이중 연결리스트를 이용해 큐를 구현해보려 한다.

 

구현하려는 큐의 추상 데이터 타입은 다음과 같다.

• empty(): 비었다면 True를, 아닐 경우 False를 반환
• enqueue(item): 큐에 rear에 item을 삽입
• deque(): 큐에 front에 있는 item을 출력
• __len__(): 큐의 크기를 반환

---

1. 큐

이전에 구현한 이중 연결리스트를 이용해 큐를 구현하려 한다

 

from LinkedList import DoubleLinkedList


class Queue(object):
    def __init__(self):
        self.queue = DoubleLinkedList()

    def empty(self):
        return self.queue.empty()

    def enqueue(self, item):
        self.queue.append(item)

    def deque(self):
        return self.queue.popleft()

    def __str__(self):
        return self.queue.__str__()

    def __len__(self):
        return len(self.queue)

Queue의 모든 기능이 이미 이중 연결리스트의 구현되어 있어 별도의 구현없이 그대로 리스트의 메서드를 끌어와 사용할 수 있다. 연결 리스트를 사용해 deque를 할 때 O(1)의 시간 복잡도를 가질 수 있다.

2. 예제코드

if __name__ == '__main__':
    queue = Queue()
    print(queue.empty())
    queue.enqueue(1);    print(queue)
    queue.enqueue(3);    print(queue)
    queue.enqueue(5);    print(queue)
    queue.deque();    print(queue)
    queue.enqueue(7);    print(queue)
    print('queue\'s length is', len(queue))
    print(queue.empty())

True
1
1 3
1 3 5
3 5
3 5 7
queue's length is 3
False