[자료구조] 큐(Queue)

큐(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

 

큐의 용어

● Enqueue: 큐에 데이터를 넣는 기능

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

 

파이썬 queue 라이브러리를 활용하여 자료구조 사용하기

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

    - Queue(): 가장 일반적인 큐 자료구조

import queue

d_queue = queue.Queue() # d_queue를 Queue()를 통해 기본큐로 선언
d_queue.put('hello') #put을 이용하여 d_queue에 데이터 추가
d_queue.put(10)
d_queue.get() #get을 이용하여 데이터를 가져온다. 여기서 나오는 출력문은 hello가 된다.

    - LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택구조와 같음)

import queue

d_queue = queue.LifoQueue() #LifoQueue를 통해 LIFO큐를 선언
d_queue.put('hello') #Queue함수로 선언한것과 동일하게 put으로 데이터 삽입
d_queue.put(30)
d_queue.get() #FIFO와 반대로 LIFO는 마지막으로 들어간 데이터가 먼저나오기때문에 출력문은 30

    - PriorityQueue(): 데이터마다 우선순위를 부여하여 우선순위가 높은 순서대로 데이터를 출력한다.

import queue

d_queue = queue.PriorityQueue()
d_queue.put((3, 'hello')) #PriorityQueue는 튜플로입력받고 첫번째에는 우선순위 두번째에 데이터를 입력한다.
d_queue.put((5, 100))
d_queue.put((15, 'world'))
d_queue.get() #우선순위가 가장 낮은수를 출력하기 때문에 출력문은 (3, 'hello')가 된다.

 

파이썬 라이브러리를 사용하지않고 enqueue, dequeue구현

list_q = [] #리스트 선언

def enqueue(data):

    list_q.append(data) #추가하고싶은 데이터를 입력하면 리스트에 추가

def dequeue():

    data = list_q[0] #리스트의 0번째 데이터를 data에 대입
    del list_q[0]    #리스트의 0번째 데이터를 삭제
    return data      #data를 리턴해줌으로 삭제된 데이터를 보여준다.