[Python] 큐(Queue) 구현

큐(Queue)

FIFO(선입선출) 형식의 자료구조
: 먼저 들어온 데이터가 순서대로 먼저 나가는 구조입니다.

스택과 다르게 한쪽에서 데이터가 추가되고, 다른 한쪽에서 데이터가 삭제되는 구조입니다.

1. 리스트를 활용한 Queue 구현

클래스를 생성합니다.

class Queue(object):
    def __init__(self):
        self.items = []        # 값을 담아줄 큐 배열 선언

다음의 기능을 추가합니다.

• enqueue : 큐의 맨 뒤쪽에 항목 삽입
• dequeue : 큐 맨 앞쪽의 항목을 반환하고 제거
• peek/front : 큐의 맨 앞쪽 항목을 조회
• empty : 큐가 비었는지 확인
• size : 큐의 크기를 확인

    def isEmpty(self):            # 큐가 비었는지 확인하는 함수(Empty : True / Not Empty : false)
        return not bool(self.items)

    def dequeue(self):
        # 큐가 비어있다면
        if self.isEmpty():
            print("Queue is Empty!")

        # 그렇지 않으면
        else:
            value = self.item.pop(0)    # 큐 배열의 0번째 값을 반환, 삭제
            return value

    def enqueue(self, item):
        self.items.append(item)            # 큐 맨 뒤에 값을 삽입

    def size(self):
        return len(self.items)           # 큐 배열의 크기를 반환

    def peek(self):
        if self.isEmpty():
            print("Queue is Empty!")

        else:
            return self.items[0]

    def __repr__(self):                    # 큐 객체를 print하기 위한 메서드
        return repr(self.items)

list를 사용해서 뒤에서 데이터를 추가하고 앞에서 데이터를 제거할 수 있는 큐를 구현했습니다.
반대 방향으로 큐를 사용하고 싶다면 dequeue에 pop(), enqueue에 insert()를 사용할 수도 있습니다.

반대방향으로 사용

    def dequeue(self):
        # 큐가 비어있다면
        if self.isEmpty():
            print("Queue is Empty!")

        # 그렇지 않으면
        else:
            value = self.items.pop()    # 큐 배열의 맨 뒤의 값을 반환
            return value

    def enqueue(self, item):            # insert(a,b) : a번째에 b값을 추가
        self.items.insert(0, item)        # 큐 배열의 0번째에 값을 추가

결과 확인

if __name__ == "__main__":
    queue = Queue()
    print("큐가 비었습니까? {}".format(queue.isEmpty()))
    print("큐에 값을 추가합니다.")
    for i in range(10):
        queue.enqueue(i)
    print("Queue : {}".format(queue))    
    print("큐의 크기 : {}".format(queue.size()))
    print("peek : {}".format(queue.peek()))
    print("dequeue : {}".format(queue.dequeue()))
    print("peek : {}".format(queue.peek()))
    print("Queue : {}".format(queue))


# 큐가 비었습니까? True
# 큐에 값을 추가합니다.
# Queue : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 큐의 크기 : 10
# peek : 0
# dequeue : 0
# peek : 1
# Queue : [1, 2, 3, 4, 5, 6, 7, 8, 9]

2. 노드를 이용한 큐 구현

노드를 이용해 Singly Linked List로 구현합니다.

# 노드 생성
class Node(object):
    def __init__(self, value = None, pointer = None):
        self.value = value
        self.pointer = pointer

# 큐 생성        
class LinkedQueue(object):
    def __init__(self):
        self.head = None    # 큐의 맨 앞
        self.tail = None    # 큐의 맨 뒤
        self.count = 0

    def isEmpty(self):
        return not bool(self.head)

    def dequeue(self):
        if self.isEmpty():
            print("Queue is Empty!")

        else:
            node = self.head                    # head를 임시 node에 대입
            self.head = self.head.pointer    # head를 다음 노드로 지정
            self.count -= 1

            if self.head is None:          # 데이터를 삭제하면서 큐가 비게 될 경우
                                        # head와 tail은 같은 노드를 바라보고 있었으므로
                self.tail = None          # tail도 비워주기

            return node.value

    def enqueue(self, value):
        node = Node(value)
        if not self.head:             # head가 비어있다면
            self.head = node
            self.tail = node
        else:
            self.tail.pointer = node       # 현재 tail의 다음 노드를 node와 연결
            self.tail = node               # 연결된 node를 tail로 지정
        self.count += 1

    def size(self):
        return self.count

    def peek(self):
        if self.head:
            return self.head.value
        else:
            print("Queue is Empty!")

    def printQueue(self):
        node = self.head
        while node:
            print(node.value, end = " ")
            node = node.pointer
        print()

LinkedQueue의 head는 큐의 맨 앞, tail은 맨 뒤를 의미합니다.

Enqueue(데이터 추가)할 때는 데이터 값을 노드 형식(value, pointer)으로 변수 node에 대입한 후
head가 비어있다면 > 큐에서 유일한 값이 되므로 head와 tail이 모두 추가된 node를 가리키게 됩니다.

head가 비어있지 않을땐 > 들어오는 값을 큐에 우선 연결해준 후, tail의 위치를 마지막으로 변경해주면 됩니다.
tail의 다음값으로 지정하기 위해 우선 기존의 tail.pointer에 변수 node를 넣어주고, 추가된 노드를 tail로 지정해줍니다.

Dequeue(데이터 삭제)할 때는 큐의 맨 앞, head를 반환해주기 위해 임시 node변수에 대입합니다.
그 후, head에 head.pointer(즉, 기존 head에서 가리키는 다음 노드)를 넣어줍니다.

마지막으로 임시 node에 저장된 기존 head값을 return해주기 전에!
큐의 유일한 노드가 삭제 될 경우는 head와 tail이 그 노드를 동시에 바라보고 있었기 때문에 tail도 None으로 초기화 해주어야 합니다.

결과 확인

if __name__ == "__main__":
    queue = LinkedQueue()
    print("스택이 비었습니까? {0}".format(queue.isEmpty()))
    print("스택에 값을 추가합니다.")

    for i in range(10):
        queue.enqueue(i)

    print("큐의 크기는? {0}".format(queue.size()))
    print("peek : {}".format(queue.peek()))
    print("pop : {}".format(queue.dequeue()))
    print("peek : {}".format(queue.peek()))
    queue.printQueue()


# 스택이 비었습니까? True
# 스택에 값을 추가합니다.
# 0 1 2 3 4 5 6 7 8 9 
# 큐의 크기는? 10
# peek : 0
# pop : 0
# peek : 1
# 1 2 3 4 5 6 7 8 9 

3. 덱(Deque)

덱(Double Ended Queue)은 큐와 다르게 양쪽 끝에서 항목을 조회, 삽입, 삭제가 가능합니다.
위에서 구현했던 큐 리스트를 그대로 상속해서 덱을 구현해보겠습니다.

큐 리스트를 이용한 덱 구현

# 리스트를 활용한 덱 구현
class Deque(Queue):               # 큐 리스트를 그대로 상속
    # enqueue 반대로 하기
    def enqueue_front(self, item):
        self.items.insert(0, item)    # 리스트 0번째에 값 추가

    # dequeue 반대로 하기
    def dequeue_back(self):
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            value = self.items.pop()   # 리스트 가장 뒤에 있는 값을 삭제, 반환
            return value
if __name__ == "__main__":
    deque = Deque()
    print("덱이 비었습니까? {}".format(deque.isEmpty()))
    print("덱에 값을 추가합니다.")
    for i in range(1,20,2):
        deque.enqueue(i)
    print("덱 : {}".format(deque))
    print("peek : {0}".format(deque.peek()))
    print("dequeue : {0}".format(deque.dequeue()))
    print("덱 : {0}".format(deque))
    deque.enqueue_front(50)
    print("덱 : {0}".format(deque))
    print("dequeue_back : {}".format(deque.dequeue_back()))
    print("덱 : {0}".format(deque))


# 덱이 비었습니까? True
# 덱에 값을 추가합니다.
# 덱 : [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# peek : 1
# dequeue : 1
# 덱 : [3, 5, 7, 9, 11, 13, 15, 17, 19]
# 덱 : [50, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# dequeue_back : 19
# 덱 : [50, 3, 5, 7, 9, 11, 13, 15, 17]

4. Collections 모듈 사용하기

Python의 Collections 모듈 안에 Deque라는 클래스가 이미 구현되어 있습니다.

Deque 클래스는 이중 연결 리스트(Double Linked List)로 구성되어서 여러 기능을 효율적으로 사용이 가능합니다.

모듈을 사용해서 덱 구현

from collections import deque        # 모듈 import

q = deque(["Apple", "Banana", "Peach"])        # deque() : 덱 생성
print(q)

# 출력
# deque(['Apple', 'Banana', 'Peach'])



# 오른쪽에 값을 추가
q.append("Strawberry")
print(q)

# 출력
# deque(['Apple', 'Banana', 'Peach', 'Strawberry'])



# 왼쪽에 값을 추가
q.appendleft("Mango")
print(q)

# 출력
# deque(['Mango', 'Apple', 'Banana', 'Peach', 'Strawberry'])



# 왼쪽의 값을 반환
q.popleft()
print(q)

# 출력
# deque(['Apple', 'Banana', 'Peach', 'Strawberry'])



# 오른쪽의 값을 반환
q.pop()
print(q)

# 출력
# deque(['Apple', 'Banana', 'Peach'])

추가로 rotate 명령어는 끝에 있는 값을 pop해서 반대쪽에 append하는 기능을 제공합니다.
리스트안의 요소들이 한 방향으로 순환하는 식입니다.

# rotate(n) : n의 길이만큼 양수면 오른쪽, 음수면 왼쪽으로 값들이 이동
q = deque(['Mango', 'Apple', 'Banana', 'Peach', 'Strawberry'])
q.rotate(2)
print(q)

# 출력
# deque(['Peach', 'Strawberry', 'Mango', 'Apple', 'Banana'])


q.rotate(-1)
print(q)

# 출력
# deque(['Strawberry', 'Mango', 'Apple', 'Banana', 'Peach'])

이상으로 파이썬에서 큐 구현에 대한 설명을 마치겠습니다.