[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

 

[ Contents ]

 

 

1. 큐(Queue)

줄 서기

큐(Queue): 선입선출(First-in-First-out), 가장 먼저 들어간 자료부터 꺼내는 자료구조

 큐는 '줄 서는 것'과 비슷합니다. 먼저 들어가서 기다린 자료부터 차례차례 꺼냅니다. 앞에서부터 꺼내며, 추가된 자료는 뒤에서부터 줄을 세웁니다.

 자료의 중간이나 뒤부터 꺼낼 수 없으며, 앞에서부터 차례차례 꺼내야 합니다.

 

 

 

2. 큐 함수

.push(a)	맨 뒤에 a 자료 추가 (enqueue)
.pop()	맨 앞의 자료 꺼내고 삭제 (dequeue)
.front()	맨 앞의 자료 반환
.rear()	맨 뒤의 자료 반환
.isEmpty()	비어있으면 1, 아니면 0 반환

 맨 앞의 자료만 삭제할 수 있고, 맨 뒤에 자료를 추가할 수 있습니다.

 맨 앞과 뒤의 자료를 확인할 수 있고, 큐가 비어있는지 알아볼 수 있습니다.

 

 

 

3. 큐 구현

class Queue:
    def __init__(self):
        self.queue = []

    # 크기 반환
    def __len__(self) -> bool:
        return len(self.queue)

    # 맨 뒤에 원소 삽입
    def push(self, item):
        self.queue.append(item)

    # 맨 앞 원소 삭제 및 반환   
    def pop(self):
        if not self.isEmpty():
            item = self.queue[0]
            self.queue = self.queue[1:] # 맨 앞 원소 제외
            return item
        else:
            return -1 #반환값 없음(비어있음)

    # 맨 앞 원소 반환
    def front(self):
        if not self.isEmpty():
            return self.queue[0]
        else:
            return -1 #반환값 없음(비어있음)

    # 맨 뒤 원소 반환
    def rear(self):
        if not self.isEmpty():
            return self.queue[-1]
        else:
            return -1 #반환값 없음(비어있음)

    # 빈 큐 여부
    def isEmpty(self) -> bool:
        return len(self.queue) == 0

 파이썬의 리스트를 활용해서 구현한 Queue입니다. 구현이 어렵진 않지만, 큐를 매번 만들어서 사용하려면 힘듭니다..

 

from collections import deque

queue = deque() #생성

 collections의 deque 라이브러리를 이용하면, 쉽게 queue를 구현할 수 있습니다.

 

.push(a)	queue.append()	맨 뒤에 a 자료 추가 (enqueue)
.pop()	queue.popleft()	맨 앞의 자료 꺼내고 삭제 (dequeue)
.front()	queue[0]	맨 앞의 자료 반환
.rear()	queue[-1]	맨 뒤의 자료 반환
.isEmpty()	not queue	비어있으면 1, 아니면 0 반환

 deque에는 front, rear와 isEmpty 기능이 없습니다. 그 대신에 리스트의 기능을 활용해서 사용할 수 있습니다.

 

 위 예시와 같이 사용합니다. queue[0]은 맨 앞 원소, queue[-1]은 맨 뒤 원소를 반환합니다. queue는 자료 리스트를 반환하며, 비어있을 경우 자료가 없으므로 0(False)을 반환합니다. Boolean형으로 not queue를 하면 isEmpty()와 동일한 기능을 할 수 있습니다.

 

 

cf) queue 라이브러리도 있지만, 범용성이 좋은 deque를 이용하는 게 좋습니다.

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

(deque 라이브러리를 활용한 스택 구현)