큐 - Dev-hwon's blog

Published: Jan 20, 2020 by Dev-hwon

Queue (큐)

들어오는 순서대로 접근 가능
선입선출(FIFO) 구조
배열의 인덱스 접근이 제한
시간복잡도 O(1)

1. 주요 기능

enqueue: 큐 뒤쪽에 항목 삽입
dequeue: 큐 앞쪽에 항목을 반환하고, 제거
peek/front: 큐 앞쪽의 항목을 조회
empty: 큐가 비어 있는지 확인
size: 큐의 크기 확인

2. 큐 사용처

멀치 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용
너비 우선 탐색(BFS)에서 사용

Code

class Queue(object):
  def __init__(self):
    self.in_stack = []
    self.out_stack = []

  def _transfer(self):
    while self.in_stack:
      self.out_stack.append(self.inin_stack.pop())

  def enqueue(self, item):
    return self.in_stack.append(item)

  def dequeue(self):
    if not self.out_stack:
      self._transfer()
    if self.out_stack:
      return self.out_stack.pop()
    else:
      print('Queue is empty.')

  def size(self):
    return len(self.in_stack) + len(self.out_stack)

  def peek(self):
    if not self.out_stack:
      self._transfer()
    if self.out_stack:
      return self.out_stack[-1]
    else:
      print('Queue is empty.')

  def __repr__(self):
    if not self.out_stack:
      self._transfer()
    if self.out_stack:
      return repr(self.out_stack)
    else:
      print('Queue is empty.')

  def isEmpty(self):
    return not (bool(self.in_stack) or bool(self.out_stack))

queue 라이브러리 활용

queue 라이브러리에 다양한 큐 구조 Queue(), LifoQueue(), PriorityQueue() 제공
- Queue(): 일반적인 큐 구조
- LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택)
- PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

알아보기