큐(Queue)

큐(Queue)의 개념

입구와 출구가 각각 한 쪽 끝에 존재하는 자료구조
FIFO : First In First Out 방식이다.

큐(Queue)의 연산

• push : 큐에 자료를 넣는 연산
• pop : 큐에서 자료를 빼는 연산
• front : 큐의 가장 앞에 있는 자료를 반환하는 연산
• back : 큐의 가장 뒤에 있는 자료를 반환하는 연산
• empty : 큐가 비어있는지 여부를 반환하는 연산, 비어있다면 1, 아니면 0을 반환한다.

큐(Queue)의 구현

파이썬에서는 큐를 리스트 또는 연결리스트로 구현한다. 아래는 리스트로 구현한 큐다.

class Queue:
    def __init__(self) :
        self.myQueue = []
	#q에 정수 n을 넣는다.
    def push(self, n) :
        self.myQueue.append(n) 
	#queue에서 가장 앞에 있는 정수를 제거하고, 만약 queue에 들어있는 값이 없을 경우에는 아무 일도 하지 않는다.
    def pop(self) :
        if self.empty() == 1:
            return        
        del self.myQueue[0] 
	#queue에 들어 있는 정수의 개수를 return 한다.
    def size(self) :
        return len(self.myQueue)
	#queue이 비어있다면 1, 아니면 0을 return 한다.
    def empty(self) :
        if self.size() == 0:
            return 1
        else:
            return 0
	#queue의 가장 앞에 있는 정수를 return 하고, 만약 queue에 들어있는 값이 없을 경우에는 -1을 return 한다.
    def front(self) :
        if self.empty() == 1 :
            return -1
        else :
            return self.myQueue[0]
	#queue의 가장 뒤에 있는 정수를 return 하고, 만약 queue에 들어있는 값이 없을 경우에는 -1을 return 합니다.
    def back(self) :
        if self.empty() == 1 :
            return -1
        else :
            return self.myQueue[-1]  

리스트로 큐를 구현하게 되면 리스트의 마지막 인덱스까지 자료가 있을 때 자료를 추가하게 되면 문제가 생긴다. 이런 문제점을 보완하기 위한 자료구조가 '원형 큐'이다. 원형 큐의 경우, 큐가 끝에 도달하면 큐의 맨 앞으로 보내 문제를 해결한다.
연결 리스트로 구현한 큐를 '링크드 큐'라고 한다.

큐(Queue) 사용하기

파이썬 기본 라이브러리의 queue 모듈의 Queue 클래스를 사용할 수 있다.

import queue
q = queue.Queue()

큐(Queue)가 활용되는 대표 예시

스케줄링(Scheduling)

어떤 작업이 병렬적으로 이루어져도 괜찮을 때, 작업들 사이에 의존관계가 없을 시 큐에 저장하여 관리할 수 있다.

사진 출처

• https://doorbw.tistory.com/116