[자료구조] 큐 (Queue)

큐: 선입선출(FIFO)의 자료구조

후단(rear)에서 삽입하고 전단(front)에서 삭제한다.

큐를 단순히 front와 queue가 있는 리스트로 구현하면 front의 인덱스는 항상 0, rear의 인덱스는 항상 -1이 되는 문제점이 발생하는데, 이렇게 될 경우 삭제나 삽입 연산 중 하나는 적어도 O(n)의 시간복잡도를 가져서 비효율적임.
그래서 원형 큐를 구현하는 것이 더 효율적이다!
rear과 front 변수를 삽입과 삭제 시에 바꿔줌으로써 항상 O(1)의 시간을 가질 수 있도록 만들어준다!

• 컴퓨터와 프린터 사이에 인쇄 작업
• 실시간 비디오 스트리밍의 버퍼링
• 은행의 대기표

큐의 기능

• isEmpty(): 큐가 비어있으면 True를, 아니면 False를 반환한다.
• enqueue(e): 항목 e를 큐의 맨 뒤(rear)에 추가한다.
• dequeue(): 큐의 맨 앞(front)에 있는 항목을 삭제하고 반환한다.
• peek(): 큐의 맨 앞(front)에 있는 항목을 반환한다.
• size(): 큐의 요소들의 개수를 반환한다.
• clear(): 큐를 초기화한다.

---

선형 큐의 구현

class LinearQueue: # 선형 큐
    def __init__(self):
        items = [] # front와 rear 변수를 선언할 필요가 X
    def isEmpty(self):
        return len(self.items) == 0
    def enqueue(self, item):
        items.append(item)
    def dequeue(self):
        if not self.isEmpty():
            items.pop(0) # 맨 앞(front)의 값을 pop한다.
    def peek(self):
        return items[0] # 삭제할 값 얼핏 보는 거니까 인덱스가 -1이 아니라 0임.

 

선형 큐의 시간복잡도
삽입 연산 enqueue()의 시간 복잡도는 O(1)이지만, 삭제 연산 dequeue()의 시간 복잡도는 O(n).

---

원형 큐의 구현

MAX_QSIZE = 10
class CircularQueue: # 원형 큐
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.items = [None] * MAX_QSIZE

    def isEmpty(self):
        return self.front == self.rear

    def isFull(self):
        return self.front % MAX_QSIZE == (self.rear+1) % MAX_QSIZE

    def clear(self):
        self.front = self.rear

    def enqueue(self, item):
        if not self.isFull():
            self.rear = (self.rear+1) % MAX_QSIZE
            self.items[self.rear] = item

    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1) % MAX_QSIZE
            return self.items[self.front]
            # pop할 필요가 없는 게 어차피 front 자리 회전시켜서 그냥 덮어씌우면 돼서 삭제 불필요

    def peek(self):
        if not self.isEmpty():
            return self.items[(self.front+1) % MAX_QSIZE]

    def size(self):
        return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
    
    def display(self):
        out = []
        if self.rear > self.front:
            out = self.items[self.front+1:self.rear+1] # rear이 front보다 크면 그냥 전부 출력해준다.
        else:
            out = self.items[self.front+1:MAX_QSIZE] + self.items[0:self.rear + 1]
            # MAX_QSIZE가 8이면 인덱스는 0~7이라 MAX_QSIZE+1으로 안 해줘도 된다.
        print(f"[front={self.front}, rear={self.rear}] -> {out}")

 

원형 큐의 시간복잡도
삽입 연산 enqueue()와 삭제 연산 dequeue() 모두 O(1).

---

큐의 응용) 우선 순위 큐

front에서 삭제하는 게 아니라, 우선순위 순서대로 삭제하는 큐.
기본적으로 더 큰 수가 우선순위가 높다고 판단한다.

class PriorityQueue:    
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0
    def size(self):
        return len(self.items)
    def clear(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)
        # enqueue까지는 큐와 동일.

    def findMaxIndex(self):
        if not self.isEmpty():
            maxN = 0;
            for i in range (0, self.size()):
                if self.items[i] > self.items[maxN]:
                    maxN = i
            return maxN

    def dequeue(self):
        if not self.isEmpty():
            maxN = self.findMaxIndex()
            return self.items.pop(maxN)

    def peek(self):
        if not self.isEmpty():
            maxN = self.findMaxIndex()
            return self.items[maxN]

 

작성일자: 2023-03-05