파이썬) 큐(Queues)

큐란 자료를 보관할 수 있는 선형구조이며, 단 데이터를 넣을때에는 한 쪽 끝에서 밀어 넣어야하고 꺼낼 때에는 반대쪽에서 꺼내야 하는 제약이 있다. 이러한 특성을 선입선출(first-in first-out)이라 한다.  그림을 통해 설명하면

 

위와 같이 아래쪽 방향으로 A를 집어넣으면 앞으로 데이터는 같은 방향으로만 넣을 수 있다.

 

다음 B를 넣으면 위와 같이 A위에 위치하게 된다. 이러한 큐의 삽입 연산을 enqueue()라고 한다.

 

데이터를 삭제하면 먼저 삽입된 A가 먼저 삭제되고 기존 A의 위치에는 B가 자리잡게 된다. 즉 큐에서 데이터가 삭제되면 맨 앞 데이터가 삭제되고 나머지 데이터는 한 칸씩 앞으로 가게된다. 이러한 큐의 삭제 연산을 dequeue()라고 한다.

 

큐의 핵심연산은 5가지가 있다.

 

• size() : 큐에 들어 있는 원소 개수 추출
• isEmpty() : 큐가 비어있는지에 대해 판단
• enqueue() : 원소 x를 큐에 삽입
• dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 참조

 

큐의 추상적 자료구조를 배열로 표현한 코드는 다음과 같다.

class ArrayQueue:  # 빈 큐 초기화
  def __init__(self):
    self.data=[]
    
class ArrayQueue:  # 큐의 크기를 리턴
  def size(self):
    return len(self.data)

  def isEmpty(self):  # 큐가 비어 있는지 판단
    return self.size()==0
    
class ArrayQueue:   # 데이터 원소 추가
  def enqueue(self,item):
    self.data.append(item)

  def dequeue(self): # 데이터 원소 삭제
    return self.data.pop(0)
    
class ArrayQueue: # 큐의 맨 앞 원소 반환
  def peek(self):
    return self.data[0]

배열로 표현한 큐의 연산의 시간 복잡도는 다음과 같다.

연산	복잡도
size()	O(1)
isEmpty()	O(1)
enqueue()	O(1)
dequeue()	O(n)
peek()	O(1)

삭제 연산이 O(n)인 이유는 맨 앞 원소를 삭제 후 뒤에 있는 원소들을 한 칸 씩 밀기 때문이다. 결국 선형 배열을 이용한 연결 리스트에서는 삭제연산 때문에 시간 복잡도가 높아진다. 그래서 연산의 시간 복잡도 측면에서는 이중 연결 리스트로 큐를 구현하는 것이 유리하다.

 

 

이중 연결 리스트로 큐를 구현한 코드는 다음과 같다.

 

(이전의 연결 리스트와 연산들이 쓰이므로 참고하시면 됩니다.)

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount

class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()

    def isEmpty(self):
        return self.data.getLength()==0

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.data.nodeCount+1 ,node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.getAt(1).data

 

이중 연결 리스트로 구현한 큐의 연산 시간 복잡도는 모두 O(1)이다. 이는 getAt()의 복잡도는 어느 쪽이라도 O(1)이기 때문에 삭제 연산도 O(1)이 되기 때문이다.