큐(Queue)

큐(queue)는 데이터 원소를 한 줄로 늘어세우는 자료 구조

📒큐 또한 선형구조라는 점에서 스택과 유사하지만 반대의 성질을 가지고 있습니다. 어느 시점에서 큐에 들어 있는 데이터 원소를 꺼내면 큐에 들어 있는 원소들 중 가장 먼저 넣었던 것이 꺼내집니다. 따라서 큐를 선입선출 (FIFO; first-in first-out) 이라고도 부릅니다.

큐의 동작

---

큐의 동작도 스택과 유사합니다. 비어있는 큐를 생성, 스택에 데이터를 추가, 큐 안의 데이터를 추출.

큐의 연산

---

• size(): 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty(): 현재 큐가 비어 있는지를 판단 (size() == 0?)
• enqueue(): 데이터 원소를 큐에 추가
• dequeue(): 큐에 가장 처음 저장된 데이터 원소를 제거(반환)
• peek(): 큐에 가장 처음에 저장된 데이터 원소를 참조 (반환), 그러나 제거하지는 않음

큐 구현하기

---

큐는 선형 배열을 이용한 연결 리스트에서 디큐 연산이 큐의 길이에 비례하는 만큼의 시간을 소요합니다. 배열에 저장된 데이터 원소들을 하나하나 앞 칸으로 당겨서 위치를 조정해야 하기 때문입니다. 그래서 연산의 시간 복잡도 측면에서는 연결 리스트로 큐를 구현하는 것이 유리합니다.

다음은 연결리스트로 구현한 큐의 코드 입니다.

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.insertAt(self.data.nodeCount+1, node)


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

    def peek(self):
        return self.data.getAt(1).data

def solution(x):
    return 0

환형 큐(Circular Queue)

---

📒환형 큐는 정해진 개수의 저장공간을 빙 돌려가며 이용합니다. 큐가 가득차면 사용 불가능하고, 큐 길이를 기억하고 있어야됩니다.

환형 큐의 연산은 지난번 큐와 동일한 연산 + isFull()이 추가되었습니다. isFull() 연산은 큐에 데이터 원소가 꽉 차 있는지를 판단하는 연산입니다.

다음은 배열로 구현한 환형 큐 코드입니다.

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
        # 빙 돌아야 하므로 maxCount 나눈 나머지가 index
        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]

우선순위 큐(Priority Queues)

---

우선순위 큐(Priority Queues)는 큐에 원소를 추가하는 연산은 다른 점이 없되, 큐에서 원소를 꺼내는 원칙은 원소들 사이의 우선순위에 따르는 자료구조이다.

우선순위 큐를 구현하는 데에는 두 가지의 서로 다른 접근 방법을 생각할 수 있습니다

• 큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법
• 큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법

여기서는 양방향 연결 리스트를 선택하여 우선순위 큐를 구현하기로 하고, 원소를 추가할 때 우선순위에 따른 알맞은 자리를 찾아서 정렬된 형태로 유지해 두고 꺼낼 때 한 쪽 끝에서 꺼낼 수 있도록 코드를 만들어보았습니다.

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 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

! 우선순위 큐는 나중에 조금 다른 자료 구조를 이용하여 더욱 효율적으로 구현할 수 있습니다.

---

💡환형 큐를 구현함에 있어서 선형배열로 구현하였지만, 양방향 연결리스트를 사용하여 구현한다면 큐의 크기가 제한되지 않고 필요한 메모리만 사용할 수 있다는 장점이 있을 것 같다.