큐(Queue)란?

큐(Queue)란?

 

큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

실제 큐의 사용 사례로는 프린터의 출력 처리, 은행 창구 번호표 대기 등이 있다.

 

큐을 구현할 때 만들 메서드는 아래와 같다.

• enqueue(): 큐의 뒤쪽(rear)에 데이터 x를 넣는 작업
• dequeue(): : 큐의 앞쪽(front)에서 데이터를 꺼내는 작업
• peek(): 큐의 앞쪽(front)에 있는 데이터를 제거하지 않고 확인하는 작업
• is_empty(): 빈 큐 인지 확인하는 작업

큐의 구현 순서

 

노드 구현

 

연결리스트와 마찬가지로, 데이터를 담을 노드를 구현한다. 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.

• 가장 먼저 들어온 값을 front라고 지칭한다. 값을 꺼낼 때, front의 값이 가장 먼저 꺼내진다.

class Queue:
    def init(self):
        self.front = None

 

enqueue()

 

큐의 뒤쪽(rear)에 데이터 x를 넣는 작업

• 가장 먼저 front에 값이 있는지 확인을 한다. front에 값이 없다면 새로운 노드를 front로 지정한다.
• front의 값이 이미 있다면, front의 값으로 가서 다음 노드의 값이 없을 때 까지 이동한다.
• 다음 노드의 값이 없다면 새로운 노드를 다음 노드의 값으로 넣는다.

    def enqueue(self, value):
        if not self.front:
            self.front = Node(value)
            return

        node = self.front
        while node.next:
            node = node.next
        node.next = Node(value)

 

dequeue()

 

큐의 앞쪽(front)에서 데이터를 꺼내는 작업

• 먼저 front의 값이 있는지 확인한다.
• front의 값이 있다면 front.next의 값을 front로 지정하고 기존 front의 값을 반환한다.

    def dequeue(self):
        if not self.front:
            return None

        node = self.front
        self.front = self.front.next
        return node.val

 

peek()

 

큐의 앞쪽(front)에 있는 데이터를 제거하지 않고 확인하는 작업

• 먼저 front의 값이 있는지 확인한다.
• front의 값이 있다면 front에 해당하는 node의 값을 반환한다.

def peek(self):
        if not self.front:
            return None

        node = self.front
        return node.val

 

is_empty()

 

빈 큐 인지 확인하는 작업

• 큐가 비어있으면 True를, 비어있지 않으면 False를 반환한다.

def is_empty(self):
    return self.front is None

 

참고

[자료구조] 큐(Queue)란? | c언어 큐 구현 (tistory.com)