자료구조: Queue

Queue?

가장 처음에 삽입된 데이터를 먼저 뺄 수 있는 방식(First in First Out) 형식의 자료구조

 

Queue의 연산

• enqueue(data) : data를 Queue의 가장 마지막에 추가한다.

• dequeue() : Queue의 가장 최근에 추가된 data를 제거하고 반환한다.

• peek() : pop()과 달리 가장 최근에 추가된 data를 반환하고, 제거하진 않는다.

• is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다.

 

Queue를 활용하는 경우

• 선입선출이 필요한 경우

  • 프로세스 관리, 우선순위 대기열, 프린터 출력 처리 등

• BFS 구현

  • Queue의 선입선출 방식을 통해 BFS를 구현할 수 있다.

  • DFS의 경우 Stack을 사용하면 된다.

 

Python으로 Queue 구현하기

class Queue:
    def __init__(self, size):
        self.size = size
        self.items = []

    def enqueue(self, data):
        if len(self.items) < self.size:
            self.items.append(data)
        else:
            return -1

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def is_empty(self):
        return True if not self.items else False

• Stack과 다른점은 pop과 peek를 할 경우 리스트의 0번째 인덱스를 접근한다는 것이다.