[자료구조] 큐(Queue) -Data Structure with 파이썬

큐(Queue)

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

 

또는 반대로 LILO(Last-In, Last-Out) 방식

 

넣는 데이터가 같은 자료형이 아니어도 됨.

 

표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. (출처)

 

 

스택과 꺼내는 순서가 반대

 

http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

 

장단점

• 데이터 접근, 삽입, 삭제가 빠르다.
• 큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능하다

 

큐(Queue)의 핵심 연산

• Enqueue
  • 큐에 데이터를 넣는 기능
  • 반환 X
• Dequeue
  • 큐에서 데이터를 꺼내는 기능
  • 데이터 반환

 

다른 연산들

• QueueInit
  • 큐의 초기화를 진행한다. (큐 생성 후 제일 먼저 호출되어야함)
  • 반환 X
• QIsEmpty
  • 큐가 빈경우 True(0이외의 것) 아닌경우 False(0) 반환
• QPeek
  • 저장순서가 가장 앞선 데이터를 반환하되 삭제 하지 않는다.

 

---

파이썬에서는 queue 라이브러리 활용

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
  • Queue(): FIFO or LILO 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 LIFO(Last-In, First-Out)구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력
  • deque() : 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조

Queue(), LifoQueue(), PriorityQueue()의 메소드들은 공통적으로 똑같다.

• empty()
  • 큐가 비어 있으면 True를, 그렇지 않으면 False를 반환
• full()
  • 큐가 가득 차면 True를, 그렇지 않으면 False를 반환
• get()
  • 생성된 큐 객체 특성에 맞추어, 아이템 1개를 반환
• get_nowait()
  • 블로킹(blocking)없이 큐 객체에 들어있는 아이템을 반환 큐 객체에 아이템이 없는 경우에는 queue.Empty 예외 발생
• join()
  • 큐의 모든 항목을 꺼내서 처리할 때까지 블록한다.
  • 완료되지 않은 작업 카운트가 0으로 떨어지면, join()이 블록 해제됩니다.
• put(item) 
  • put(item[, block[, timeout]])
    • 아이템을 입력한다. (넣는다.)
• put_nowait()
  • 블로킹(blocking)없이 큐 객체에 아이템을 입력한다. 큐 객체가 꽉 차 있는 경우에는 queue.Full예외 발생
• qsize()
  • 큐에 입력된 아이템의 개수를 반환
• task_done()
  • 앞서 큐에 넣은 작업이 완료되었음을 나타냄

---

예)

import queue

'''-----------------Queue()---------------------------- '''
data_queue = queue.Queue()
data_queue.put("coding")
data_queue.put(1)
print(data_queue.qsize())
# 2
print(data_queue.get())
#'coding'
print(data_queue.qsize())
# 1


'''-----------------LifoQueue()---------------------------- '''
data_queue = queue.LifoQueue()
data_queue.put("coding")
data_queue.put(1)
print(data_queue.qsize())
# 2
print(data_queue.get())
# 1


'''-----------------PriorityQueue()---------------------------- '''
data_queue = queue.PriorityQueue()
data_queue.put((10, "ka"))
data_queue.put((5, 1))
data_queue.put((15, "ca"))
print(data_queue.qsize())
# 3
print(data_queue.get())
# (5, 1)

주의할 점 

PriorityQueue()로 큐를 만들때의 put함수의 인자로 튜플로써 (우선순위번호, 데이터) 를 넣어주어야한다.

 

여기서 우선순위가 가장 높은 것은 1이다.

---

배열 기반 큐 구현

파이썬에서 배열은 리스트로 한다.

'''FIFO 구조 '''
queue_list = list()

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

for index in range(10):
    enqueue(index)
    
print(dequeue())
print(queue_list)
'''
0
[1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

 

원형큐

 

연결리스트 기반 큐 구현

 

덱 (Deque) 구현

 

덱을 기반으로 큐 구현