[자료구조] 11. 큐 (Queue)

큐 (Queue)

• 큐(Queue)는 Data 원소를 보관할 수 있는 선형 구조 알고리즘이다.
• 어떻게 보면 앞서 후입선출(LIFO, Last-In First-Out)형인 스택(Stack)과 비슷한 것으로 보이지만, 큐는 데이터 원소를 인풋하는 방향과 아웃풋하는 방향이 서로 반대인 선입선출(FIFO, First-In First-Out)형 알고리즘이다.

(1) 인큐(Enqueue) 연산

• 인큐는 큐에 새로운 데이터를 추가하는 연산이다.

• 데이터는 큐의 맨 뒤에 삽입된다.

  

  

(2) 디큐(Dequeue) 연산

• 디큐는 큐에 데이터를 제거하는 연산이다.

• 큐의 맨 앞에 위치한 데이터가 제거된다.

  

  

---

큐의 추상적 자료구조 구현

(1) 연산의 정의

• size(): 현재 큐에 들어있는 데이터 원소의 수를 구한다.
• isEmpty(): 현재 큐가 비어있는지를 판단한다.
• enqueue(): 데이터 원소 x를 큐에 추가한다.
• dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거하고 반환한다.
• peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환한다. (*공개 라이브러리에는 X)

(2) 배열(Array)를 이용하여 구현

• 이전 스택을 배열을 이용하여 구현했을 때와 원소의 삭제를 제외하고는 모두 동일하다.
• 큐의 연산복잡도는 dequeue를 제외하고 모두 상수시간 알고리즘\( O(1) \)에 해당한다.
  • 참고) 사이즈 반환의 경우, 리스트의 길이 정보가 리스트 객체 내에 직접 저장되기 때문에 상수시간 알고리즘\(O(1)\)에 해당한다.
• dequeue의 경우 리스트의 맨 앞에 위치한 원소를 삭제하는 과정을 거치기 때문에, 삭제 이후 index=0부터 데이터 원소를 채우기 위해서 index이동이 발생한다. 따라서, dequeue는 큐내에 데이터 원소 수에 비례하여 처리 시간이 길어지는 선형시간 알고리즘\( O(n) \)에 해당한다.

• 코드로 구현하면 다음과 같다.

    class ArrayQueue:
      
        def __init__(self):
            self.data = [] # 빈 큐를 초기화
  
        def size(self):
            return len(self.data) # 큐의 크기를 리턴
  
        def isEmpty(self):
            return self.size()==0 # 큐가 비어 있는지 판단
  
        def enqueue(self, item):
            self.data.append(item) # 데이터 원소를 추가 
  
        def dequeue(self):
            self.data.pop(0) # 데이터 원소를 삭제 (리턴)
  
        def peek(self):
            return self.data[-1] # 큐의 맨 앞 원소 반환 
  

(3) 양방향 연결리스트 (Doubly Linked List)를 이용하여 구현

• 위에서 설명했듯이, 배열 기반의 선형 큐는 dequeue작업 수행 시 선형 시간\(O(n)\) 알고리즘에 해당하여 담고 있는 데이터 원소의 수가 증가할수록 비효율적이다. 따라서, 배열보다는 인덱싱 이동이 필요없는 양방향 연결리스트로 구현하는 것이 배열 기반으로 구현하는 것보다 시간복잡도 측면에서 효율적이다.

• 코드로 구현하면 다음과 같다.(모듈 코드 참고 링크)

    from utils_practice.node_v2 import Node
    from utils_practice.linkedlist_v2 import DoublyLinkedList
      
    class LinkedListQueue:
      
        def __init__(self):
            self.data = DoublyLinkedList()
      
        def size(self):
            return self.data.nodeCount
      
        def isEmpty(self):
            return self.size() == 0
      
        def enqueue(self, item):
            node = Node(item)
            self.data.insertAt(self.size()+1, node)
      
        def dequeue(self):
            return self.data.popAt(1)
      
        def peek(self):
            return self.data.getAt(1).data
  

(4) 파이썬 라이브러리

• 스택은 굉장히 많이 사용되는 알고리즘이기에 파이썬 라이브러리 형태로도 존재한다.

    from pythonds.basic.queue import Queue
  

---

References

• Programmers, 어서와! 자료구조와 알고리즘은 처음이지?