5.10 파이썬 큐(Queue) : FIFO, LIFO 예제

파이썬 큐(queue, 대기열)이란 무엇인가?

큐는 데이터를 보관하는 컨테이너입니다. 먼저 입력된 데이터가 먼저 제거되므로 대기열을 "선입선출"(FIFO)이라고도 합니다. 대기열에는 앞과 뒤에 두 개의 끝이 있습니다. 항목은 후면에서 입력되고 전면에서 제거됩니다.

목차

파이썬 큐의 작동

줄은 실제 예와 쉽게 비교할 수 있습니다. 매표소에서 줄을 서서 기다리는 사람들의 줄은 먼저 서 있는 사람이 먼저 표를 받고 다음 사람이 뒤따르는 식입니다. 큐 데이터 구조에도 동일한 논리가 적용됩니다.

다음은 큐를 도식적으로 표현한 것입니다.

파이썬 큐 작동 설명

Rear은 대기열 내부에 항목이 삽입되는 지점을 나타냅니다. 이 예에서 7은 이에 대한 값입니다.

Front 는 대기열에서 항목 이 제거되는 지점을 나타냅니다. 대기열에서 항목을 제거하면 그림과 같이 첫 번째 요소가 1입니다.

 

항목 1은 대기열에 가장 먼저 삽입된 항목이고 제거하는 동안 가장 먼저 나오는 항목입니다. 따라서 대기열을 FIRST IN FIRST OUT(FIFO)이라고 합니다.

FIRST  IN  FIRST  OUT(FIFO)

큐(대기열)에서 항목은 순서대로 제거되며 그 사이에서 제거할 수 없습니다. 큐에서 항목 5를 무작위로 제거할 수는 없습니다. 이렇게 하려면 5 이전의 모든 항목을 제거해야 합니다. 큐에 있는 항목은 삽입된 순서대로 제거됩니다.

 

파이썬의 큐(queue, 대기열) 유형

파이썬에는 주로 두가지 유형의 큐가 있습니다.

• 선입선출 큐( First In First Out Queue): 이를 위해 먼저 들어가는 요소가 가장 먼저 나옵니다. FIFO를 사용하려면 큐 모듈에서 Queue() 클래스를 호출해야 합니다.
• 후입선출 큐: 여기에서 마지막으로 입력된 요소가 가장 먼저 나옵니다. LIFO를 사용 하려면 대기열 모듈에서 LifoQueue() 클래스를 호출해야 합니다.

파이썬 큐 설치

파이썬에서 큐로 작업하는 것은 매우 쉽습니다. 다음은 코드에서 대기열을 사용하기 위해 따라야 할 단계입니다.

 

1단계) 아래와 같이 큐의 모듈을 가져오기만 하면 됩니다.

import queue

모듈은 기본적으로 파이썬에서 사용할 수 있으며 대기열 작업을 시작하기 위해 추가 설치가 필요하지 않습니다. 대기열 FIFO(선입 선출) 및 LIFO(후입 선출)의 두 가지 유형이 있습니다.

 

2단계) FIFO queue로 작업하려면 아래와 같이 가져온 queue 모듈을 사용하여 Queue 클래스를 호출합니다.

import queue
q1 = queue.Queue()

3단계) ​​LIFO 대기열을 사용하려면 아래와 같이 LifoQueue() 클래스를 호출합니다.

import queue
q1 = queue.LifoQueue()

Queue 및 LifoQueue 클래스 내에서 사용 가능한 메서드

다음은 Queue 및 LifoQueue 클래스 내에서 사용할 수 있는 중요한 메서드입니다.

• put(item): 이것은 큐 안에 item을 넣을 것입니다.
• get(): 대기열에서 항목을 반환합니다.
• empty(): 대기열이 비어 있으면 true를 반환하고 항목이 있으면 false를 반환합니다.
• qsize(): 큐의 크기를 반환합니다.
• full(): 큐가 가득 차면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

선입선출(FIFO) 큐

선입선출의 경우 먼저 들어가는 요소가 먼저 나옵니다.

큐에 항목 추가

큐에 항목을 추가하는 예를 살펴보겠습니다. 큐 작업을 시작하려면 먼저 아래 예제와 같이 큐 모듈을 가져옵니다.

항목을 추가하려면 다음 예제와 같이 put() 메서드를 사용할 수 있습니다.

import queue
q1 = queue.Queue()
q1.put(10) #이것은 큐에 항목 10을 추가합니다.

기본적으로 큐의 크기는 무한하며 항목을 원하는 수만큼 추가할 수 있습니다. 큐의 크기를 정의하려는 경우 다음과 같이 동일하게 수행할 수 있습니다.

import queue
q1 = queue.Queue(5) #최대 크기는 5입니다.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # true를 반환합니다.

출력

True

이제 큐의 크기는 5이고 5개 이상의 항목을 사용하지 않으며 q1.full() 메서드는 true를 반환합니다. 항목을 더 추가해도 코드가 더 이상 실행되지 않습니다.

 

큐에서 항목 제거

큐에서 항목을 제거하려면 get()이라는 메서드를 사용할 수 있습니다. 이 메서드는 호출될 때 대기열의 항목을 허용합니다.
다음 예는 큐에서 항목을 제거하는 방법을 보여줍니다.

import queue
q1 = queue.Queue()
q1.put(10)

item1 = q1.get()

print('대기열에서 제거된 항목은 ', item1)

출력

대기열에서 제거된 항목은  10

 

후입선출(LIFO) 큐

후입선출 큐인 경우 마지막에 입력된 요소가 가장 먼저 나옵니다.
LIFO로 작업하려면, 즉, 선입선출 대기열의 마지막에 대기열 모듈을 가져와 LifoQueue() 메서드를 사용해야 합니다.

큐에 항목 추가

여기서는 LIFO 대기열에 항목을 추가하는 방법을 이해합니다.

import queue
q1 = queue.LifoQueue()
q1.put(10)

위의 예와 같이 LifoQueue에서 put() 메서드를 사용해야 합니다.

 

큐에서 항목 제거

후입선출 큐에서 항목을 제거하려면 get() 메소드를 사용할 수 있습니다.

import queue
q1 = queue.LifoQueue()
q1.put(10)

item1 = q1.get()

print('LIFO 대기열에서 제거된 항목은 ', item1)

출력

LIFO 대기열에서 제거된 항목은  10

큐에 2개 이상의 항목 추가

위의 예에서 단일 항목을 추가하고 FIFO 및 LIFO 큐에 대한 항목을 제거하는 방법을 보았습니다. 이제 하나 이상의 항목을 추가하고 제거하는 방법을 살펴보겠습니다.

FIFO 큐에 항목 추가

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # 이것은 0에서 20까지의 항목을 대기열에 추가합니다.

FIFO 큐에서 항목 제거

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # 이것은 0에서 20까지의 항목을 대기열에 추가합니다.

while not q1.empty():
print("The value is ", q1.get()) # get()은 대기열에서 항목을 제거합니다.

출력

The value is  0
The value is  1
The value is  2
The value is  3
The value is  4
The value is  5
The value is  6
The value is  7
The value is  8
The value is  9
The value is  10
The value is  11
The value is  12
The value is  13
The value is  14
The value is  15
The value is  16
The value is  17
The value is  18
The value is  19

LIFO 큐에 항목 추가

import queue
q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i) # 이것은 0에서 20까지의 항목을 대기열에 추가합니다.

LIFO 큐에 항목 제거

import queue
q1 = queue.LifoQueue()

for i in range(20):
    q1.put(i) # 이것은 0에서 20까지의 항목을 대기열에 추가합니다.


while not q1.empty():
print("The value is ", q1.get()) # get()은 대기열에서 항목을 제거합니다.

출력

The value is  19
The value is  18
The value is  17
The value is  16
The value is  15
The value is  14
The value is  13
The value is  12
The value is  11
The value is  10
The value is  9
The value is  8
The value is  7
The value is  6
The value is  5
The value is  4
The value is  3
The value is  2
The value is  1
The value is  0

큐 정렬

다음 예는 큐 정렬을 보여줍니다. 큐에 사용되는 알고리즘은 버블 정렬입니다.

import queue
q1 = queue.Queue()
#대기열에 항목 추가
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#큐에서 버블 정렬 사용
n =  q1.qsize()
for i in range(n):
    x = q1.get() # 요소가 제거됨
    for j in range(n-1):
        y = q1.get() # 요소가 제거됨
        if x > y :  
            q1.put(y)   #작은 것이 큐의 시작 부분에 놓입니다.
        else:
            q1.put(x)  # 더 작은 것이 큐의 시작 부분에 놓입니다.
            x = y     # 더 큰 것은 x로 대체되고 다으번 요소와 다시 비교됩니다.
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

출력

3 4 5 10 11 21

큐 반전

큐를 뒤집기 위해 다른 큐와 재귀를 사용할 수 있습니다.
다음 예는 큐를 반대로 가져오는 방법을 보여줍니다.

import queue
q1 = queue.Queue()

q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

def reverseQueue (q1src, q2dest) :  
    buffer = q1src.get()
    if (q1src.empty() == False) :
reverseQueue(q1src, q2dest)      #재귀 사용
    q2dest.put(buffer)
return q2dest

q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)

while (qReversed.empty() == False): 
print(qReversed.queue[0], end = " ")  
        qReversed.get()

출력

10 3 21 4 5 11

 

요약

• 큐는 데이터를 보관하는 컨테이너입니다. 대기열에는 FIFO 및 LIFO의 두 가지 유형이 있습니다.
• FIFO(선입선출 대기열)의 경우 먼저 가는 요소가 가장 먼저 나옵니다.
• LIFO(Last in First out Queue)의 경우 마지막에 입력된 요소가 가장 먼저 나옵니다.
• 큐의 항목은 put(item) 메서드를 사용하여 추가됩니다.
• 항목을 제거하려면 get() 메서드를 사용합니다.

Python Queue: FIFO, LIFO 예제