[Python : 알고리즘] Queue 란?

Queue(큐)란 먼저 들어온 데이터가 먼저 나가는 '선입선출'의 자료구조 입니다.

Stack은 한쪽이 막힌 원통이였다면 Queue는 양쪽이 모두 뚫린 원통입니다.

위의 그림처럼

양쪽이 모두 뚫린 원통에서 파란색, 초록색 공을 오른쪽에서 집어넣고, 왼쪽에서 공을 뺄때 가장 먼저 넣었던 파란색 공이 나오게 됩니다.

이러한 형태를 Queue라고 하며, 공을 넣는 과정을 push, 공을 빼내는 과정을 pop이라고 합니다.

 

Queue에서는 push할때 원통의 오른쪽에서 집어넣는다, pop할때는 원통의 왼쪽에서 빼낸다 라고 생각하면 이해하기 쉽습니다.

 

파이썬에서는 'deque' 라이브러리를 사용해서 간단하게 Queue를 구현할 수 있으며, 

deque의 append()를 사용하여 Queue 자료구조의 push,

deque의 popleft()를 사용하여 Queue 자료구조의 pop을 구현할 수 있습니다.

 

from _collections import deque 

def queue_example():
    queue = deque() 
    queue.append(7)
    queue.append(5) 
    queue.append(2) 
    queue.popleft() 
    queue.append(1) 
    queue.append(6)
    queue.popleft()

먼저, Queue를 사용하기 위해 deque 라이브러리를 임포트 해주고

deque()를 사용해서 queue를 만들어줍니다.

 

queue.append(7)

7

queue.append(5)

7

5

queue.append(2)

7

5

2

queue.popleft()

7 (popleft)

5

2

5

2

queue.append(1)

5

2

1

queue.append(6)

5

2

1

6

queue.popleft()

5 (popleft)

2

1

6

2

1

6

이러한 연산이 이루어진 이후 최종 queue의 값은 [2, 1, 6] 이 됩니다.

 

위의 예제에 주석이 포함된 소스코드는

여기 에서 보실 수 있습니다.