Queues

1. Queues

1) Array를 이용한 큐 구현

class ArrayQueue:
    def __init__(self):
        self.data = []
    
    def size(self): # O(1)
        return len(self.data)
       
    def isEmpty(self): # O(1)
        return self.size() == 0
        
    def enqueue(self, item): # O(1)
        self.data.append(item)
        
    def dequeue(self): # O(n) : worst case - 배열의 맨 앞 원소를 꺼내는 경우
        return self.data.pop(0)
        
    def peek(self): # O(1)
        return self.data[0]

2) Doubly LinkedList를 이용한 큐 구현

from doublyLinkedList import Node
from doublyLinkedList 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

>>> from DoublyLinkedListQueue import *
>>> Q = LinkedListQueue()
>>> Q.size()
0
>>> Q.isEmpty()
True
>>> Q.enqueue(10)
>>> Q.size()
1
>>> Q.isEmpty()
False
>>> Q.enqueue(20)
>>> Q.dequeue()
10
>>> Q.peek()
20
>>> Q.dequeue()
20
>>> Q.size()
0

2. Circular Queue

1) Queue를 활용하는 경우

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
  
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
  
• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
  
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 모두 여러 곳에서 일어나는 경우
• 자료를 처리해서 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우
  

2) 환형 큐 특징

• 배열의 경우 맨 앞에 위치한 원소를 삭제할 때 큐의 길이의 비례하는 복잡도가 발생하는 것을 방지
• '정해진 개수'의 저장 공간을 빙 돌려가며 이용
• 큐가 가득차면 원소를 더 넣을 수 없기 때문에 큐 길이를 기억해야 함
• 기존 큐 연산에서 isFull() 연산 추가 사용
• 데이터를 꺼내는 곳 pointer : front
• 데이터를 넣는 곳 pointer : rear

3) 배열을 이용한 환형 큐 구현

• pointer front와 rear를 적절하게 계산해서 배열을 환형으로 재활용
  

class CircularQueue:

    def __init__(self, n): # 빈 큐 초기화
        self.maxCount = n # 인자로 주어진 최대 큐 길이 설정
        self.data = [None] * n
        self.count = 0 # 현재 큐에 들어있는 데이터 원소 개수
        self.front = -1
        self.rear = -1
        
    def size(self): # 현재 큐 길이 반환
        return self.count
        
    def isEmpty(self):
        return self.count == 0
       
    def isFull(self):
        return self.count == self.maxCount # 최대 큐 길이와 비교
        
    def enqueue(self, x): # 큐에 데이터 원소 추가
        if self.isFull(): # 큐가 꽉차있는 경우 예외 발생
            raise IndexError('Queue full')
        self.rear = (self.rear + 1) % self.maxCount # pointer 조정
        self.data[self.rear] = x # 데이터 추가
        self.count += 1 # 카운트 증가
        
    def dequeue(self): # 큐에서 데이터 원소 뽑기
        if self.isEmpty(): # 큐가 비어있는 경우 예외 발생
            raise IndexError('Queue empty')
        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x
        
    def peek(self): # 큐의 맨 앞 원소 들여다보기
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]

>>> Q = CircularQueue(6)
>>> Q.enqueue(1)
>>> Q.enqueue(2)
>>> Q.enqueue(3)
>>> Q.enqueue(4)
>>> Q.enqueue(5)
>>> Q.enqueue(6)
>>> Q.enqueue(7)
IndexError: Queue full
>>> Q.dequeue()
1
>>> Q.dequeue()
2
>>> Q.peek()
3
>>> Q.enqueue(8)
>>> Q.peek()
3
>>> Q.dequeue()
3
>>> Q.peek()
4
>>> Q.enqueue(9)
>>> Q.enqueue(10)
>>> Q.enqueue(11)
IndexError: Queue full
>>> Q.dequeue()
4
>>> Q.dequeue()
5
>>> Q.dequeue()
6
>>> Q.dequeue()
8
>>> Q.dequeue()
9
>>> Q.dequeue()
10
>>> Q.dequeue()
IndexError: Queue empty
>>> Q.peek()
IndexError: Queue empty

3. Priority Queues

• 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

1) 우선 순위 큐의 구현

• 두가지 구현 방식이 존재
  (1) Enqueue를 할 때 우선 순위 순서를 유지하도록 구현
  (2) Dequeue를 할 때 우선 순위가 높은 것을 선택하도록 구현
  -> (1)이 더 유리함

• 구현 재료
  (1) 선형 배열 이용
  (2) 연결 리스트 이용
  -> 시간적으로 유리한 것은 (2), 공간적으로 유리한 것은 (1)
  -> 시간이 더 중요하기 때문에 연결 리스트를 사용해서 구현

2) 양방향 연결리스트 우선순위 enqueue 연산

• 양방향 연결 리스트의 getAt() 메서드를 이용하지 않음
  -> curr라는 pointer가 따라가면서 우선순위 확인
  -> while문에서 getAt() 메서드를 반복 호출하는 것을 방지하기 위함
• 나머지 연산은 기존 큐와 동일함
• dequeue 연산은 맨 앞에서부터 꺼내면 됨

from doublyLinkedList import Node, DoublyLinkedList

# 여기서는 값이 작을수록 우선 순위가 높음
class PriorityQueue:

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

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

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head # 처음 위치 지정
        # while 종료 조건 : 연결 리스트의 끝이거나, 
        # 다음 노드의 데이터보다 값이 크거나 같은 경우
        while curr.next.data != None and x < curr.next.data:
            curr = curr.next
        self.queue.insertAfter(curr, newNode) # 해당 위치 다음에 삽입

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data      

>>> Q = PriorityQueue()
>>> Q.isEmpty()
True
>>> Q.enqueue(1)
>>> Q.enqueue(0)
>>> Q.enqueue(3)
>>> Q.size()
3
>>> Q.dequeue()
0
>>> Q.peek()
1
>>> Q.enqueue(2)
>>> Q.dequeue()
1
>>> Q.dequeue()
2
>>> Q.dequeue()
3
>>> Q.dequeue()
IndexError
>>> Q.isEmpty()
True

출처 : 어서와! 자료구조와 알고리즘은 처음이지? - 프로그래머스