[자료구조와 알고리즘] 자료구조(2) - 큐

365.48km·2023년 1월 2일

queue 알고리즘 자료구조 큐

자료구조와 알고리즘

목록 보기

3/6

1. 큐(Queue)란?

Key Ponint 💡 큐의 구조

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
일종의 줄을 서는 행위와 유사하다.
FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out) 방식으로 스택과 꺼내는 순서가 반대

2. 알아둘 용어

Key Ponint 💡 큐의 용어

Enqueue : 큐에 데이터를 넣는 기능
Dequeue : 큐에서 데이터를 꺼내는 기능

3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

Key Ponint 💡 queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 를 제공.

Queue() : 가장 일반적인 큐 자료 구조
LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조라고 보면 됨)
PriorityQueue() : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

3.1. Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In-First-Out)


import queue # queue 라는 라이브러리 사용하기 위해서 import queue

data_queue = queue.Queue() # 라이브러리명.큐 클래스
# 일반적인 FIFO 정책을 쓴 Queue가 만들어진다.

# queue 라이브러리는 함수명 put / get을 사용한다.
# put은 데이터를 삽입
data_queue.put("funcoding")
data_queue.put(1)

# queue의 사이즈를 확인하기 위해서 qsize를 사용
data_queue.qsize() # 2


# get : 꺼내는 함수, get은 별도의 인자를 사용하지 않는다. 

data_queue.get() # 맨 먼저 넣어진 데이터가 출력이 된다. = funcoding

data_queue.qsize() # 'funcoding'을 뺴주었기 때문에 qsize()는 1이 된다.

data_queue.get() # 다시 get을 실행하면 다음에 넣어진 데이터가 출력된다. = 1

data_queue.qsize()  #'funcoding' 과 '1' 이 queue에서 빠져나온 것을 알 수 있다. = 0

3.2. LifoQueue()로 큐 만들기 LIFO(Last-In, First-Out)

Key Ponint 💡 마지막에 넣은것이 가장 먼저 추출이 된다. = 스택


import queue  # queue 라는 라이브러리 사용하기 위해서 import queue
data_Queue = queue.LifoQueue()

data_Queue.put('funcoding')
data_Queue.put(1)
data_Queue.qsize()

data_Queue.get() # 마지막에 넣은것이 가장 먼저 추출이 되므로 1이 출력이 된다.
data_Queue.qsize() # 1이 빠져 나왔기 때문에 qsize는 한 개가 된다.
data_Queue.get() #'funcoding'은 가장 처음에 집어 넣었으므로, 가장 마지막에 출력이 된다.
data_Queue.qsize() # 다 빠져나왔으므로 qsize는 0이다.

3.3. PriorityQueue()로 큐 만들기

Key Ponint 💡 우선순위 큐

이 정책은 각각의 데이터를 넣을 때마다 우선수위 번호를 같이 넣는 것.

이 안에서 데이터를 추출할 때는 가장 우선순위가 높은 데이터를 추출한다

우선순위에 따라 데이터를 추출하는 순서가 달라진다.


import queue
data_PriQueue = queue.PriorityQueue()

# 데이터 삽입
# 데이터를 넣을 때 데이터만 삽입하는 것이 아니라 우선순위도 삽입하여야 한다.

data_PriQueue.put((10,"korea"))  # ()는 튜플을 나타내는 기호 (우선순위, "데이터")
data_PriQueue.put((5,1)) # 우선순위는 5번이고 실제 적용되는 데이터는 1
data_PriQueue.put((15, "USA")) # 우선순위는 15번이고 실제 적용되는 데이터는 "USA"

data_PriQueue.qsize()  # qsize는 세 개이다.

# 숫자가 낮은것이 먼저 출력된다.
data_PriQueue.get()  # 우선순위중 가장 빠른 것은 5번이었던 1이 출력된다. 
# (5, 1)


data_PriQueue.get() 
# (10, 'korea')

data_PriQueue.get() 
# (15, 'USA')

data_PriQueue.qsize() # 모두 다 빠져나왔으므로 qsize는 0이 된다.