큐(Queues)

1 큐(Queue)란?

• 자료 (data element)를 보관할 수 있는 (선형) 구조
• 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고, 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있다 → enqueue & dequeue → 선입선출(FIFO First-In First-Out)
  

2 큐의 동작

1. 초기 상태: 비어 있는 큐 (empty queue)
   1. Q = Queue()
2. 데이터 원소 A를 큐에 추가
   1. Q.enqueue(A)
3. 데이터 원소 B를 큐에 추가
   1. Q.enqueue(B)
4. 데이터 원소 꺼내기 → A
   1. r1 = Q.dequque()
5. 데이터 원소 꺼내기 → B
   1. r2 = Q.dequque()

3 큐의 추상적 자료구조 구현

1. 배열(array)을 이용하여 구현
   • python 리스트와 메서드들을 이용
2. 연결 리스트(linked list)를 이용하여 구현
   • 양방향 연결 리스트 이용
3. 파이썬 라이브러리로 구현
   • from pythonds.basic.queue import Queue

3.1 연산의 정의

• size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 큐가 비어 있는지를 판단
• enqueue(x): 데이터 원소 x를 큐에 추가 ↔ push과 동일
  
• dequeue(): 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 변환) ↔ pop과 동일
  
• peek(): 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거 X)

4 배열로 구현한 큐

4.1 구현 코드

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):
				return self.data.pop(0)
		
		def peek(self):
				return self.data[0]

4.2 배열로 구현한 큐의 연산 복잡도

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

배열을 활용해 구현할 경우 dequeue() 연산 시에 선형 연산 시간이 된다

→ 큐의 길이에 비례한다

리스트(파이썬의 배열)의 특성상 맨 앞 원소를 삭제하면 그 다음 원소부터 삭제된 맨 앞 원소의 자리를 채우기 위해 앞으로 한 자리씩 옮기는 과정을 갖기 때문에 큐의 길이가 길어질 수록 비효율적이게 된다

5 양방향 연결 리스트를 이용한 구현

5.1 구현 코드

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.insertAfter(self.data.tail.prev, node)

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

    def peek(self):
        return self.data.head.next.data

6 큐의 활용

1. 큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우 활용
2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
4. 자료를 생성하고 이용하는 작업이 양쪽 다 여러 고에서 일어나는 경우
5. 자료를 처리해 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

→ 큐는 컴퓨터 시스템 내에서도 자주 사용된다