[자료구조] Queue(큐)

Queue(큐)란?

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

큐는 데이터가 쌓이고 가장 먼저 들어간 데이터가 먼저 나온다. ( Stack과 반대 )

데이터를 넣는 enqueue()와 데이터를 꺼내는 dequeue() 가 있다.

 

예시

프린터의 출력 처리

윈도 시스템의 메시지 처리기

프로세스 관리

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

 

용어설명

Enqueue : 큐 맨 뒤에 데이터를 넣는다.
Dequeue : 큐 맨 앞쪽의 데이터를 꺼내온다.
Peek : front에 위치한 데이터를 읽음 (데이터 꺼내오지 않음)

front : 큐의 맨 앞의 위치
rear : 큐의 맨 뒤의 위치

Queue 설명

선형 큐
선형 큐는 위와 같이 1차원 배열로 이루어진 Queue라고 생각하면 된다.

데이터가 증가하면 Rear의 값이 증가하고 그 위치에 데이터를 저장하게 됩니다. 삭제할 때는 Front의 값을 하나 증가하고 Front의 위치에 있는 데이터를 삭제한다.

따라서 선형큐를 사용할 경우 Front와 Rear의 값이 계속 증가 하기 때문에 언젠가는 배열의 끝에 도달하게 될 거고 그렇게 되면 배열의 앞부분이 비어 있더라도 사용하지를 못한다. 

원형큐
위에서 말씀드렸던 선형큐의 문제점을 보완하기 위한 것이 바로 원형큐이다. 

큐를 원형으로 연결되어 있는 것이라고 생각하고, 구현하는 것이다. 공백상태는 front == rear 인 상태이며 포화상태는 front == (rear+1) % MAX_QUEUE_SIZE 의 값으로 판단한다. 마지막 한 자리는 공백 상태와 포화 상태를 구분하기 위해 비어놓는다.

큐 구현하기 - 선형 큐

MAX_QUEUE_SIZE=3
class Queue:
    def __init__(self):
        self.queue = [None]*MAX_QUEUE_SIZE
        self.front=-1
        self.rear=-1

    def isEmpty(self):
        if self.front==self.rear:
            return True
        else:
            return False
            
    def isfull(self):
        if self.rear>=MAX_QUEUE_SIZE-1:
            return True
        else:
            return False
            
    def enqueue(self, data):
        if self.isfull():
            print("Queue is full")
        else:
            self.queue[self.rear]=data
            self.rear+=1
            
    def dequeue(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            value=self.queue[self.front]
            self.queue[self.front]=None
            self.front += 1
            return value

    def peek(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            peeked = self.queue[self.front]
            return peeked

큐 구현하기 - 원형 큐

MAX_QUEUE_SIZE=3
class Queue:
    def __init__(self):
        self.queue = [None]*MAX_QUEUE_SIZE
        self.front=-1
        self.rear=-1

    def isEmpty(self):
        if self.front==self.rear:
            return True
        else:
            return False
            
    def isfull(self):
        if (self.rear + 1) % MAX_QUEUE_SIZE == self.front:
            return True
        else:
            return False
            
    def enqueue(self, data):
        if self.isfull():
            print("Queue is full")
        else:
            self.queue[self.rear] = data
            self.rear = (self.rear + 1) % MAX_QUEUE_SIZE

    def dequeue(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            value=self.queue[self.front]
            self.queue[self.front]=None
            self.front = (self.front + 1) % MAX_QUEUE_SIZE
            return value

    def peek(self):
        if self.isEmpty():
            return "Queue is Empty"
        else:
            peeked = self.queue[self.front+1]
            return peeked