큐 (Queue)

 

큐는 배열과 마찬가지로 기본적이고 중요한 자료구조이며, 운영체제나 네트워크에서도 많이 사용됩니다.

특히, 운영체제에서 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 큐가 자주 이용될 수 있습니다. 프로세스 스케쥴링 방식을 이해하는 것이 큐 이해에 큰 도움이 될 수 있습니다. 

 

큐는 줄을 서는 행위와 유사하며, 은행에서 번호표를 받은 사람이 줄을 선다고 가정할 떄, 가장 빠른 번호표를 받은 사람이 은행 창구에 들어간다고 생각하시면 좋습니다.

특히, FIFO 정책이 많이 사용되며, First In First Out의 약자입니다. 먼저 입력된 데이터가 먼저 출력되는 것입니다.

LILO는 Last In Last Out의 약자로 FIFO의 반대로 마지막 입력된 데이터가 마지막에 출력되는 것입니다.

 

FIFO 구조를 보면 다음과 같습니다.

8 -> 6 -> 7 -> 1 -> 3 순으로 데이터를 집어 넣는 경우, 구조는 아래와 같습니다.                                                            

3

1

7

6

8         [Output]

만약에 8이 나오게 되면, 다음에 나올 순서는 6이 될 것입니다.

3

1

7

6

아래의 사이트에서 큐에 대해 더 연습하실 수 있습니다.

반응형

https://visualgo.net/en/list

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

여기서 Enqueue는 큐에 데이터 삽입을 의미하며, Dequese는 큐에 데이터 삭제를 의미합니다.

 

큐 라이브러리를 통해 개발하는 과정에서 많은 도움을 얻을 수 있습니다.

기본적인 큐 정책인 FIFO 외에도,  LifoQueue(), PriorityQueue() 등을 이용하실 수 있습니다.

LifoQueue()는 스택 구조로 나중에 입력된 데이터가 먼저 출력하도록 합니다. 

PriorityQueue()는 데이터마다 우선 순위가 매겨지며, 우선 순위에 따라 데이터를 출력하도록 합니다.

 

아래의 파이썬 코드를 확인해봅니다.

import queue
practice_queue = queue.Queue() 
practice_queue.put(8)
practice_queue.put(6)
practice_queue.put(3)
print(practice_queue.qsize())
print(practice_queue.get())
print(practice_queue.get())
print(practice_queue.qsize())

Queue 라이브러리를 임포트하고, 이후에 put() 메소드를 이용하여 8, 6, 3을 차례로 넣어줍니다. 그리고 get() 메소드를 이용해 먼저 넣어준 데이터를 꺼내도록 합니다.

queue.Queue() 로 선언하면 기본적인 FIFO 정책을 따르게 됩니다.

 

결과는 다음과 같습니다.

데이터 3개를 넣었기 때문에, qsize()는 3이 될 것이며, 이후 get() 메소드를 통해 먼저 들어간 8과 6을 꺼낸 것입니다.

다시 qsize()를 출력하면, 당연히 크기로 1이 나온 것입니다.

3
8
6
1

 

이번에는 LIFO 정책으로 큐에 데이터를 넣고 꺼내보도록 합니다.

아래와 같이 Queue를 임포트하고, 이번에는 queue.LifoQueue() 정책으로 큐를 만들어 줍니다.

import queue
practice_queue = queue.LifoQueue() 
practice_queue.put("해바라기")
practice_queue.put("장미")
practice_queue.put("민들레")
print(practice_queue.qsize())
print(practice_queue.get())
print(practice_queue.get())
print(practice_queue.qsize())

결과는 아래와 같은데요.

LIFO는 마지막에 입력된 데이터가 먼저 출력되는 구조입니다.

아래와 같이 사이즈에는 변화가 없으나, 마지막에 넣은 "민들레"가 먼저 나온 것을 확인할 수 있습니다.

3
민들레
장미
1

추가적으로 우선순위 정책에서는 큐에서 데이터를 어떻게 다루는지 확인해보도록 합니다.

아래와 같이 queue.PriorityQueue()로 선언하여 큐를 만들어줍니다.

PriorityQueue에 데이터를 넣을 때는 튜플 형식으로 넣게 됩니다. 따라서 (( )) 이러한 형식으로 데이터가 들어가는데, 첫 번째 인자로는 우선순위 번호, 두 번째 인자로는 데이터가 들어갑니다.

우선순위 번호는 낮을수록 더 우선합니다. 1이 제일 우선순위겠죠?

import queue
practice_queue = queue.PriorityQueue() 
practice_queue.put((8, "바나나"))
practice_queue.put((1, "사과"))
practice_queue.put((4, "딸기"))
print(practice_queue.qsize())
print(practice_queue.get())
print(practice_queue.get())
print(practice_queue.qsize())

출력하면 다음과 같습니다. 

우선순위 1번인 '사과'가 먼저 출력되고, 다음 우선순위인 '딸기'가 출력된 것입니다.

3
(1, '사과')
(4, '딸기')
1

 

그럼 큐에 데이터를 추가하고 삭제하는 프로그램을 코딩해봅니다.

아래와 같이, queue_list 변수를 리스트로 정의합니다.

enqueue 함수는 a라는 인자가 들어갔을 때, append 함수를 이용하여 리스트에 a를 첫번째 순서로 넣어주는 함수입니다.

dequese 함수는 먼저 들어간 함수를 꺼내주는 역할을 하는데, 0번째 인덱스의 데이터를 할당하고, 리턴할 수 있도록 코딩합니다. 당연히 두 번째 들어간 데이터가 나올 수 있도록 0번째 데이터는 delete 해줍니다. 

queue_list = list()

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

def dequeue():
 a = queue_list[0]
 del queue_list[0]
 return a
  
for index in range(10):
 enqueue(index)
 
print(queue_list)
print(len(queue_list))
dequeue()
print(queue_list)
print(len(queue_list))
dequeue()
print(queue_list)
print(len(queue_list))

반복문을 사용하여, 0~9까지 index 데이터를 넣고, 이후 출력 결과는 다음과 같습니다. 처음에는 아무 변화가 없었으나, dequeue() 함수로 0을 꺼냈기 때문에 사이즈는 9로 줄어들게 됩니다. 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
10
[1, 2, 3, 4, 5, 6, 7, 8, 9]
9
[2, 3, 4, 5, 6, 7, 8, 9]
8