큐 다루기

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software Engineer

큐

FIFO: 선입선출
- 먼저 삽입된 항목이 가장 먼저 제거됨

큐

FIFO: 선입선출
- 먼저 삽입된 항목이 가장 먼저 제거됨

큐

FIFO: 선입선출
- 먼저 삽입된 항목이 가장 먼저 제거됨

큐 - 구조

국제 요리 이름이 적힌 큐의 개략적 표현.

큐 - 구조

국제 요리 이름이 적힌 큐의 개략적 표현. "head"가 큐의 시작 부분을 가리킨다.

시작: head

큐 - 구조

국제 요리 이름이 적힌 큐의 개략적 표현. "tail"이라는 단어가 큐의 끝을 가리킨다.

시작: head
끝: tail

큐 - 특징

두 가지 국제 요리 이름이 적힌 큐의 개략적 표현. "head"는 큐의 앞, "tail"은 큐의 끝을 가리킨다.

큐 - 특징

새 요소가 큐의 tail에 삽입된 큐의 개략적 표현.

끝에만 삽입 가능
- Enqueue

큐 - 특징

첫 번째 요소가 제거될 예정임을 나타내는 큐의 개략적 표현.

끝에만 삽입 가능
- Enqueue
head에서만 제거 가능

큐 - 특징

첫 번째 요소가 제거되어 두 개의 요소만 남은 큐의 개략적 표현.

끝에만 삽입 가능
- Enqueue
head에서만 제거 가능
- Dequeue
다른 종류의 큐:
- 양방향 큐(Deque)
- 원형 큐
- 우선순위 큐

큐 - 실제 활용 사례

프린터의 인쇄 작업
- 문서는 수신된 순서대로 인쇄됨
요청 순서가 중요한 애플리케이션
- 콘서트 티켓 예매
- 택시 서비스

큐 - 구현

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None

큐 - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

노드로 구현된 요소 하나짜리 큐의 개략적 표현.

큐 - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

노드로 구현된 요소 하나짜리 큐의 개략적 표현. "head"와 "tail"이 해당 노드를 가리킨다.

큐 - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:

두 개의 노드로 구현된 큐의 개략적 표현. 새 노드가 삽입 준비 중이다.

큐 - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node

세 개의 요소를 가진 큐의 개략적 표현. "tail"은 아직 두 번째 노드를 가리킨다.

큐 - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node
    self.tail = new_node

세 개의 요소를 가진 큐의 개략적 표현. "tail"이 마지막으로 삽입된 노드를 가리킨다.

큐 - dequeue

세 개의 요소를 가진 큐의 개략적 표현. "head"는 첫 번째 노드, "tail"은 마지막 노드를 가리킨다.

def dequeue(self):

  if self.head:

큐 - dequeue

세 개의 요소를 가진 큐의 개략적 표현. "head"와 "current_node"는 첫 번째 노드, "tail"은 마지막 노드를 가리킨다.

def dequeue(self):
  if self.head:
    current_node = self.head

큐 - dequeue

세 개의 요소를 가진 큐의 개략적 표현. "head"는 첫 번째 노드, "current_node"는 두 번째 노드, "tail"은 마지막 노드를 가리킨다.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next

큐 - dequeue

두 개의 요소를 가진 큐의 개략적 표현. "head"는 첫 번째 노드, "tail"은 마지막 노드를 가리킨다. 큐 외부에 "current_node"가 가리키는 노드가 있다.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

큐 - dequeue

"current_node"와 "tail"이 가리키는 노드. "head"는 null을 가리킨다.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None


    if self.head == None:

큐 - dequeue

"current_node"가 가리키는 노드. "head"와 "tail"은 null을 가리킨다.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

    if self.head == None:
      self.tail = None

Python의 SimpleQueue

모듈: queue
- Queue
- SimpleQueue

import queue


orders_queue = queue.SimpleQueue()


orders_queue.put("Sushi")
orders_queue.put("Lasagna")
orders_queue.put("Paella")


print("The size is: ", orders_queue.qsize())

The size is: 3

print(orders_queue.get())
print(orders_queue.get())
print(orders_queue.get())

Sushi
Lasagna
Paella

print("Empty queue: ", orders_queue.empty())

Empty queue: True

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘