자료구조 - 큐(Queue)란?

Queue란

- 큐는 한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제연산만 이루어지는 유한 순서 리스트이다.

 

 

특성

- 구조상 먼저 삽입된 item이 먼저 삭제가 이루어진다. (FIFO)

 

 

큐의 표현

1. 순차 표현

- 1차원 배열을 이용한 순차표현이다.

- 인덱스를 값으로 가지는 front, rear 라는 두개의 변수와 큐의 사이즈를 나타내는 n이라는 변수를 사용한다.

- front, rear를 -1로 초기화 하여 큐가 empty임을 나타낸다. (front == rear일 때 큐는 공백)

- rear에서 삽입 되므로 rear가 점차 증가하여 rear==n-1인 경우 큐는 full상태이다.

 

문제점

- 큐에 삽입이 되며 점차 rear가 증가하게 되면 결국 full상태가 된다. 하지만 이때 큐에 원소가 꽉차있지 않을 수 있다. front에서 삭제가 일어났다면 그만큼 공간이 비었기 때문이다. 따라서 만원(Full) 상태가 되었을 때에는 첫번째 원소의 위치를 큐의 [0]번 인덱스부터 위치되게 한뒤 이것을 기준으로 rear이 위치도 다시 정해주어야 한다.

- 위의 문제로 순차 표현 큐는 많은 비용(큐 원소 이동에 따른 지연시간)을 발생하게 된다.

 

해결책(원형큐)

- 큐의 순차표현시 원형큐를 이용하면 원소의 이동없이 이용할 수 있다.

empty(공백)

- front, rear를 0으로 초기화한다. 이 때 큐는 비어있는 상태이므로 front == rear는 큐가 Empty임을 나타내는 조건이다.

enqueue(삽입)

- 원소 삽입시 우선 큐가 full인지 확인한 다음 full상태가 아니라면 rear를 1증가 시킨 후 그 자리에 item을 삽입한다.

full(만원)

- full의 상태를 검사하기 위해서는 rear를 증가시켰을 때 front와 같게 된다면(rear+1 == front) full로 처리하면 된다. 그렇게 된다면 항상 큐의 front가 가리키는 인덱스는 비어있는 상태로 유지되는데, 이것을 통해 full과 empty를 구분한다. 만약 front에 자리까지 원소가 삽입된다면 front==rear 조건이 큐가 empty인지 full인지를 구분하지 못하게 된다.

dequeue(삭제)

- 삭제하기전 우선 큐가 empty인지 확인한 다음 empty가 아니라면 front를 1 증가 시킨 후 그 자리의 원소를 삭제한다.

 

Source Code

​x
# -1은 빈 원소로 표현
class Queue:
    front = 0
    rear = 0
    size = 0
    queue = []
​
    def __init__(self, size):
        self.queue = [-1 for i in range(0,size)]
        self.size = size
        self.front = 0
        self.rear = 0
​
    def is_empty(self):
        if self.rear is self.front:
            return True
        return False
​
    def is_full(self):
        if (self.rear + 1)%size is self.front:
            return True
        return False
​
    def enqueue(self, item):
        if self.is_full():
            return
        self.rear = (self.rear + 1)%self.size
        self.queue[self.rear] = item
​
    def dequeue(self):
        if self.is_empty():
            return
        self.front = (self.front + 1)%self.size
        self.queue[self.front] = -1
​
# Test code
if __name__ == "__main__":
    size = int(input("큐의 크기를 입력"))
    queue = Queue(size)
    print(queue.queue)
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    print(queue.queue)
    queue.dequeue()
    print(queue.queue)

 

2. 연결 표현

- 연결 표현(Linked List)을 이용한 큐 표현은 원소의 삽입과 삭제시 원소들을 이동시킬 필요가 없다.

empty(공백)

- front, rear 가 아무런 노드를 가리키지 않는다면 empty 상태이다.

enqueue(삽입),full(만원)

- 삽입시 순차표현과 달리 full(만원)상태 인지를 확인할 필요가 없다.

dequeue(삭제)

- 삭제시 큐가 empty상태인지 확인을 해야하며, front를 이용해 마지막 노드를 제거할 때 rear역시 null 상태로 변경해주어야 한다.

 

문제점

- 다음 노드를 가리키는 링크필드에 대한 추가적인 메모리 사용을 염두해야 한다.

 

Source Code

xxxxxxxxxx
class Node:
    item = -1
    next = None
​
    def __init__(self, item):
        self.item = item
​
class Queue:
    front = None
    rear = None
​
    def __init__(self):
        self.front = None
        self.rear = None
​
    def enqueue(self, item):
        new_node = Node(item)
​
        #공백 큐
        if self.is_empty():
            self.rear = new_node
            self.front = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
​
    def dequeue(self):
        if self.is_empty():
            return
        else:
            delete_node = self.front
            self.front = self.front.next
            if self.front is None:
                self.rear = None
​
    def is_empty(self):
        if self.rear is None:
            return True
        return False
​
    def print_queue(self):
        print("==== queue ====")
        temp = self.front
        while temp is not None:
            print(temp.item)
            temp = temp.next
​
if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.print_queue()
    queue.dequeue()
    queue.dequeue()
    queue.print_queue()
    queue.dequeue()
    queue.print_queue()