자료구조 - Queue 알아보기
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
