[6] Queue, 큐

👇🏻 오늘의 짤 : 최근에 피트 데이비슨이랑 아주 🔥 하게 장안의 화제가 되고 있는 킴언니의 짤을 준비했다.

도박장가면 킴 카다시안을 찾으세요. 도박 중독은 1336으로 신고하세요.

---

몇일 전에 롯데월드에 갔는데 내가 가장 좋아하는 게 아틀란티스다. 근데 그거 RG 다들. 아틀란티스 줄 엄청 긴거. 기본으로 1시간은 기다려야 함. 어쨌든, 난 그걸 타다가 사촌동생이 주먹으로 눈알을 쳐서 각막이 벗겨진 경험이 있다. 심지어 생일 전 날..ㅎ

 

 

아틀란티스에 줄을 서 있다고 생각해보자. 앞과 뒤로 많은 사람들이 줄 서 있고 앞 사람이 차례로 놀이기구를 타야 내 차례가 돌아온다.

아틀란티스에 줄 선 모든 사람들은 큐(Queue)의 원소를 자처하고 있는 것이다.

 

큐(Queue) :  데이터들이 순서대로 줄 서 있는 자료형
FIFO (First In First Out, 선입선출)으로 동작하기 때문에 가장 먼저 들어온 데이터가 가장 먼저 삭제된다. 
큐는 top 원소로만 접근이 가능한 스택과는 다르게, 맨 앞, 뒤에 데이터를 삽입하고 삭제할 수 있다.

 

 

큐를 구현하기 전에, 큐에 관해 알아야할 용어들이 있다.

  1. enqueue : 큐의 끝에 데이터 삽입

  2. dequeue : 가장 먼저 삽입한 데이터를 빼기

  3. front, rear : 가장 먼저 들어온 데이터, 가장 늦게 들어온 데이터

  

파이썬으로 큐를 구현하는 방법은 세가지이다. 

 

✓ List로 구현

 

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

    def enqueue(self, data):
        self.queue.append(data)
    
    def dequeue(self):
        return self.queue.pop(0)
    
    def print_queue(self):
        print(self.queue)
    
    def isEmpty(self):
        return not self.queue

queue = Queue()
print(queue.isEmpty()) # True

for data in range(0,10):
    queue.enqueue(data)

queue.print_queue() # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(len(queue.queue)):
    queue.dequeue()

queue.print_queue() # []

 

 

✓ deque로 구현

deque(double-ended queue, 데크) : 앞과 뒤 양방향에서 데이터를 처리할 수 있는 자료구조로 메소드를 제공한다.

list와 비슷하지만 내부가 doubly linked list로 구현되어 있기 때문에 데이터를 처리 속도가 O(1)로 매우 빠르다. 

 

append(data)	데이터를 큐에 오른쪽에 추가
appendleft(data)	데이터를 큐에 왼쪽에 추가
clear()	큐에 있는 모든 데이터를 비움
insert(i, data)	i번째 자리에 data를 삽입
pop()	큐의 오른쪽 데이터를 반환하고 삭제
popleft()	큐의 왼쪽 데이터를 반환하고 삭제
remove(value)	큐의 데이터 중 먼저 위치한 value를 삭제

 

from collections import deque

queue = deque([])

for data in range(1,10):
    queue.append(data)

print(queue) # deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(list(queue))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

print(queue.popleft()) # 1
print(queue.popleft()) # 2

print(list(queue)) # [3, 4, 5, 6, 7, 8, 9]

 

✓ Queue로 구현

파이썬 Queue 모듈에서는 큐(Queue), 우선순위큐(Priority Queue), 스택(LIFO Queue)와 공용 메소드를 제공하므로 갖다 쓰면 된다.

 

Queue.qsize()	큐의 크기를 반환
Queue.empty()	큐가 비어 있으면 True, 그렇지 않으면 False를 반환
Queue.full()	큐가 가득 차면 True, 그렇지 않으면 False를 반환
Queue.put(item)	큐에 item 삽입
Queue.get()	큐에서 항목을 제거하고 반환

 

import queue

Queue = queue.Queue()

for data in range(0,10):
    Queue.put(data)

print(Queue.queue) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print(list(Queue.queue)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(Queue.get()) # 0
print(Queue.get()) # 1

print(list(Queue.queue)) # [2, 3, 4, 5, 6, 7, 8, 9]

 

근데 print(Queue.queue)를 했을 때, deque 타입으로 출력이 되는데 Queue 모듈이 deque로 설계되어 있을 수도 있다는 생각이 든다. 근데 확실히는 모르겠다..ㅎ

 

끝 ! 

 

👇🏻 github Queue 코드 확인하기

✓ list로 구현

https://github.com/Seeun-Lim/Data-Structure/blob/main/Queue-list.py

GitHub - Seeun-Lim/Data-Structure

 

✓ deque로 구현

https://github.com/Seeun-Lim/Data-Structure/blob/main/Queue-deque.py

GitHub - Seeun-Lim/Data-Structure

 

✓ Queue로 구현

https://github.com/Seeun-Lim/Data-Structure/blob/main/Queue-Queue.py

GitHub - Seeun-Lim/Data-Structure