[자료구조] 큐(Queue)

큐(Queue)는 먼저 추가한 데이터를 먼저 반환/삭제하는 선입선출(FIFO - First In First Out) 형식의 선형 또는 원형 자료구조이다.
queue는 사전적으로 '대기줄'을 뜻한다.

가령 식당에 입장하기 위에 줄을 설 때, 가장 먼저 줄을 선 사람은 맨앞에 있으므로 맨앞 사람부터 차례대로 가게에 들어간다.
(줄을 섬 = 데이터 추가 = Enqueue,  가게에 입장 = 데이터 반환 = Dequeue)

---

핵심 연산

• push(item) : 큐 맨뒤에 데이터 삽입
• pop() : 큐 맨앞 데이터 삭제 및 반환
• front() : 큐 맨앞 데이터 반환
• back() : 큐 맨뒤 데이터 반환
• size() : 큐 크기 반환
• empty() : 큐가 비었는지 여부 반환
• full() : 큐가 가득 찼는지 여부 반환

참고 :
꽉 찬 큐에 push하려는 경우를 오버플로우(Overflow), 텅 빈 큐에서 pop하려는 경우를 언더플로우(Underflow)라고 한다.

---

큐의 활용

• 데크(Deque), 우선순위 큐(Priority Queue) 등으로 변형
• 캐시 구현
• 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기

---

구현 [Python]

선형 큐(Linear Queue)

1. 배열(Array)

class Queue:
    maxlen = 10

    def __init__(self):
        self.array = [None] * self.maxlen
        self.head = -1
        self.tail = -1

    def push(self, item):
        if not self.full():
            self.tail += 1
            self.array[self.tail] = item

    def pop(self):
        if not self.empty():
            self.head += 1
            return self.array[self.head]
            
    def front(self):
        if not self.empty():
            return self.array[self.head + 1]
            
    def back(self):
        if not self.empty():
            return self.array[self.tail]

    def size(self):
        return self.tail - self.head

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

    def full(self):
        return self.size() == self.maxlen

2. 연결 리스트(Linked List)

class Node:
    def __init__(self, item, link=None):
        self.item = item
        self.link = link

class Queue:
    maxlen = 10

    def __init__(self):
        self.head = None
        self.tail = self.head
        self.length = 0

    def push(self, item):
        if not self.full():
            new = Node(item)
            if self.tail:
                self.tail.link = new
                self.tail = self.tail.link
            else:
                self.head = self.tail = new
            self.length += 1

    def pop(self):
        if not self.empty():
            item = self.head.item
            self.head = self.head.link
            self.length -= 1
            if self.empty():
                self.tail = self.head
            return item
            
    def front(self):
        return self.head.item

    def back(self):
        return self.tail.item

    def size(self):
        return self.length

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

    def full(self):
        return self.size() == self.maxlen

원형 큐(Circular Queue)

위 1번 코드에서 배열로 구현된 선형 큐에는, pop 연산 횟수와 관계없이 삽입할 수 있는 아이템 개수가 maxlen를 넘을 수 없다는 비효율성이 존재한다.
이때 나머지 연산 %를 활용해 원형 큐(Circular Queue)를 구현하면 이러한 단점을 극복할 수 있다.
원형 큐는 마지막 위치가 시작 위치와 연결된다는 점에서 링 버퍼(Ring Buffer)라고도 불린다.

class Queue:
    maxlen = 10

    def __init__(self):
        self.array = [None] * self.maxlen
        self.head = -1
        self.tail = -1

    def push(self, item):
        if not self.full():
            self.tail += 1
            self.array[self.tail % self.maxlen] = item

    def pop(self):
        if not self.empty():
            self.head += 1
            return self.array[self.head % self.maxlen]
            
    def front(self):
        if not self.empty():
            return self.array[(self.head + 1) % self.maxlen]

    def back(self):
        if not self.empty():
            return self.array[self.tail % self.maxlen]

    def size(self):
        return self.tail - self.head

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

    def full(self):
        return self.size() == self.maxlen