Queue (FIFO, 순차적자료구조)

순차적 자료 구조 중 Last In First Out에 대표적으로 Stack이 있었다면, 

 

First In First Out 자료 구조에는 큐(queue)가 있다.

 

큐(Queue)

 

먼저 들어온 구조가 리스트 front에 자리잡고 스택과 같이 차곡차곡 쌓이다가 pop될때

 

(큐에서는 dequeue 라고한다), front에 있는 자료가 나가는 구조이다. 

 

stack에서 배웠던 push가 enqueue,  pop이 dequeue로 표현된다.

 

이 큐를 파이썬을 사용하여 클래스로 구현하면 다음과 같다.

 

 

class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0
    def enqueue(self, value): #push와 같은 역할
        self.items.append(value)
    def dequeue(self): #pop과 같은 역할
        if self.front_index == len(self.items):
            print("큐가 비었습니다.")
            return None
        else:
            X = self.items[self.front_index]
            self.front_index += 1 #인덱스를 증가시켜 리스트를 한칸 뒤부터 읽겠다
            return X

 

 

특이한점은 디큐부분이다. 스택에서는 삭제시킬때 pop을 하면 그만이었지만, 큐에서는

 

가장 앞의 자료를 삭제하는것이기 때문에 리스트에서 삭제하는 것이 아니라

 

그 뒤 자료부터 읽는 방식을 택한다. 가령 리스트에 [1, 2, 3, 4, 5] 가 있을 때,

 

디큐를 하면 1이 삭제되는것이 아닌, 1은 리스트에 그대로 있지만, front_index를 증가시켜

 

2부터 자료를 읽는 방식이다. 이 큐를 이용하여 많은 문제들을 해결 할 수 있으며,

 

많이 쓰이는 순차적 자료 구조 중 하나이다.