자료구조 - Queue 알아보기

개념 정리
코드 구현(with Python)
파이썬 라이브러리

• Queue()
• PriorityQueue()

참고 자료

Queue - 큐

FIFO(First In First Out)
먼저 넣은 데이터가 먼저 나오는 구조로 데이터를 저장하는 형식

> *멀티 태스킹을 위한 프로세스 스케쥴링 구현에 많이 사용

장점과 단점

장점

• 데이터의 빠른 입력/추출

단점

• 맨 앞의 데이터만 접근 가능

시간 복잡도

• 데이터 입력/추출: O(1)

큐 구조

• enqueue: 마지막 순번으로 데이터 입력
• dequeue: 첫번째 데이터 추출

큐 종류

• Queue()
  • 일반적인 큐, FIFO
• PriorityQueue()
  • 우선순위 큐
  • 데이터를 입력할 때 우선순위 값을 같이 넣어주고, 추출할 때 우선순위가 높은 순으로 데이터를 추출한다.
• CircularQueue()
  • 순환 큐
  • 첫번째 데이터가 마지막 데이터와 연결되어 있는 구조
• LifoQueue() == Stack

코드 구현

queue_list = list()

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

Test - enqueue()

for i in range(10):
    enqueue(i)

print("queue size:", len(queue_list))
print("queue data:", queue_list)

queue size: 10
queue data: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Test - dequeue()

data = dequeue()

print("dequeue data:", data)
print("queue size:", len(queue_list))
print("queue data:", queue_list)

dequeue data: 0
queue size: 9
queue data: [1, 2, 3, 4, 5, 6, 7, 8, 9]

파이썬 라이브러리 - Queue()

import queue

# init queue
queue_by_library = queue.Queue()
print("Initialize Queue")
print("queue size:", queue_by_library.qsize())
print()

# enqueue
for i in range(10,0,-1):
    queue_by_library.put(i)

print("After Enqueue")
print("queue size:", queue_by_library.qsize())
print()

# dequeue
data = queue_by_library.get()

print("After Dequeue")
print("dequeue data:", data)
print("queue size:", queue_by_library.qsize())

Initialize Queue
queue size: 0

After Enqueue
queue size: 10

After Dequeue
dequeue data: 10
queue size: 9

파이썬 라이브러리 - PriorityQueue()

• 우선순위 지정시 기본적으로 작은 값이 우선순위가 높다

import queue

# init queue
priority_queue = queue.PriorityQueue()

print("Initialize Queue")
print("queue size:", priority_queue.qsize())
print()

# enqueue
priority_queue.put((10, "dog"))
priority_queue.put((5, "cat"))
priority_queue.put((15, "bird"))

print("After Enqueue")
print("queue size:", priority_queue.qsize())
print()

# dequeue
print("Excute Dequeue")
print(priority_queue.get())
print(priority_queue.get())
print(priority_queue.get())
print()

print("After Dequeue")
print("queue size:", priority_queue.qsize())
print()

Initialize Queue
queue size: 0

After Enqueue
queue size: 3

Excute Dequeue
(5, 'cat')
(10, 'dog')
(15, 'bird')

After Dequeue
queue size: 0

참고 자료

• 패스트캠퍼스 <알고리즘/기술면접 완전 정복 올인원 패키지> (DAVE LEE 강사님)