[자료 구조] Queue

Queue

---

• FIFO(First In First Out, 선착순) :  삽입할 땐 가장 최근에 저장된 값 다음에 저장되고(stack과 동일) 삭제할 땐 가장 오래전에 저장된 된 값부터 나간다.
• enqueue(val) : value를 큐의 오른쪽(rear)에 삽입 (push와 같음)
• dequeue(): 가장 왼쪽에 저장된 값을 삭제 후 리턴 
• dequeue를 상수시간에 실행하기 위해선, dequeue가 될 값의 인덱스(index)를 저장하고 관리한다 → dequeue가 되면, 인덱스 값이 하나 증가하여 다음 dequeue 될 예정인 값의 인덱스를 가리키도록 관리! 

 

▶ Queue class 생성

class Queue:
    def __init__(self):  # 생성자 함수
        self.items = []  # 데이터 저장을 위한 리스트 준비 
        self.front_index = 0  # 다음 dequeue될 값의 인덱스 기억 
    def enqueue(self, val):  # 삽입
        self.items.append(val) 
    def dequeue(self):  # 삭제 후 값 반환
        if self.front_index == len(self.items): # dequeue할 아이템이 없음
            print("Queue is empty") 
            return None 
        else:                  
            x = self.items[self.front_index]  # dequeue할 아이템이 있음
            self.front_index += 1
            return x

 

▶ Queue 객체 생성

Q = Queue()
Q.enqueue(5)
Q.enqueue(-2)
Q.enqueue(10)
print(Q.dequeue())  #5
print(Q.dequeue())  #-2
print(Q.dequeue())  #10
print(Q.dequeue())  #Queue is empty   None

 

 

▶ Python 라이브러리 활용

 

• queue : 가장 일반적인 큐 자료 구조

import queue

# queue
Q = queue.Queue()  # 객체 생성
Q.put(5)  # 삽입
Q.put(-2)
Q.put(10)
print(Q.qsize())  # queue의 아이템 개수 확인
print(Q.get())  # 삭제 후 값 반환 5
print(Q.get())  # 삭제 후 값 반환 -2
print(Q.qsize()) # 1

 

• LIFO queue (Last-in, First-Out) : 나중에 입력된 데이터가 먼저 출력되는 구조 ( =stack )

import queue

# LIFO queue (Last-in, First-Out)
lifoQ = queue.LifoQueue()  # 객체 생성
Q.put(5)  # 삽입
Q.put(-2)
Q.put(10)
print(Q.qsize())  # 아이템 개수 확인 3
print(Q.get())  # 삭제 후 값 반환 10 (마지막에 들어온 아이템)
print(Q.get())  # 삭제 후 값 반환 5 (마지막에 들어온 아이템)
print(Q.qsize())  # 아이템 개수 확인1

 

• Priority queue : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

import queue

# Priority queue
priQ= queue.PriorityQueue()  # 객체생성
priQ.put((6, 'pizza'))  # 삽입(우선순위, 값)
priQ.put((2, 'chicken'))
priQ.put((15, 'pasta'))
print(priQ.qsize())  # 아이템 개수 확인  3
print(priQ.get())  # 우선순위가 높은 아이템 제거 (2, 'chicken')
print(priQ.get())  # 우선순위가 높은 아이템 제거 (6, 'pizza')

 

 

▶ Dequeue (Double-ended Queue)

 

• Dequeue는 stack과 queue의 연산을 모두 지원하는 자료구조
• 왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐이다 -> 두 가지 버전의 push와 pop 연산을 구현, 나머지 연산은 Stack, Queue 클래스와 유사하게 구현
• Python에서는 collections라는 모듈에 deque란 클래스로 dequeue가 이미 구현됨
• 오른쪽 push = append, 왼쪽 push = appendleft 
• 오른쪽 pop = pop, 왼쪽 pop = popleft 

from collections import deque 

d = deque('ghi')  #세 개의 아이템으로 deque를 생성

d.append('j')   #새로운 값을 오른쪽에 삽입
d.appendleft('f')  #새로운 값을 왼쪽에 삽입
print(d)  #dequeu를 보여준다. -> deque(['f', 'g', 'h', 'i', 'j'])
d.pop()  #가장 오른쪽에 있는 값을 삭제하고 반환
d.popleft()  #가장 왼쪽에 있는 값을 삭제하고 반환
print(d)  #dequeu를 보여준다. -> deque(['g', 'h', 'i'])