[자료구조][Python] : Queue(큐)

자료구조 with Python : Queue(큐)

---

큐는 스택과 다르게 항목이 들어온 순서대로 접근이 가능하다. 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조다. 큐도 스택처럼 랜덤 액세스가 제한된다.

큐의 구조

• front : 큐의 가장 앞을 가리키는 포인터
• rear : 큐의 가장 뒤를 가리키는 포인터
• enqueue : rear 뒤에 원소를 삽입하는 함수
• dequeue : front 위치의 원소를 제거하면서 반환하는 함수
• is_empty : 큐가 비어있는지 확인하는 함수
• size : 큐의 크기를 확인하는 함수

---

큐의 구현

---

class Queue(object):
    def __init__(self):
        self.items = []
        self.front = 0
        self.rear = -1

    def isEmpty(self):
        return self.front > self.rear

    def enqueue(self, item):
        self.items.append(item)
        self.rear += 1

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
        else:
            self.front += 1
            return self.items[self.front - 1]

    def __repr__(self):
        return repr(self.items[self.front:self.rear+1])

items 리스트에 enqueue()함수로 데이터를 넣으면 가장 뒤를 나타내는 rear가 커진다.

dequeue를 하면 front가 가리키는 데이터를 반환하고 front가 1 증가한다.

큐가 비어있는 지 여부는 front > rear로 알 수 있다.

확인코드

queue = Queue()
for i in range(1, 4):
    queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)

이 방법은 큐의 동작이 어떻게 이뤄지는지 확인하기 위함이고 이렇게 계속 사용하게 되면 dequeue()를 하더라도 데이터가 남아있기 때문에 좋은 방법은 아니라고 생각한다.

쉬운 구현은 list자료형을 이용해서 append와 pop(0)를 사용하는 방법이지만 pop(0) 의 경우 시간복잡도가 O(N)이기 때문에 이 또한 비효율적이다.