큐(queue)에 대해서 알아보기

큐(queue)에 대해서 알아보기

300x250

큐(queue)란?

프로그래밍 영역이 아닌 실생활에서 큐(queue)는 대기줄이라는 뜻을 갖고 있으며 실생활에서 큐와 자료구조에서 큐는 밀접한 관련이 있습니다.

먼저 실생활에서 놀이공원에서 놀이기구의 탑승 대기줄을 생각해봅시다.

놀이기구를 빨리 타기 위해서는 줄을 일찍 설수록 빨리 탈 수 있습니다. 이렇게 먼저 들어온 순으로 처리를 하는 형태를 선입선출 라고 하며 일반적인 큐가 이러한 형태를 따릅니다.

하지만 놀이 기구를 생각봤을 때, 예약을 하거나 특정 멤버십을 갖고 있는 사람이면 먼저 들여보내는 경우가 있죠?

이러한 형태처럼 우선순위에 따라 데이터를 먼저 처리하는 자료구조를 우선순위 큐라고 하며 이는 보통 '힙'을 이용해 구현할 수 있습니다.

보통의 큐와 우선 순위 큐는 내부 구조가 다르기도 하고 이 포스트에서는 일반적인 큐만 다룰 것이기 때문에 우선 순위 큐를 구현하는 '힙'에 대해서는 링크를 달아놓겠습니다.

https://lbdiaryl.tistory.com/152?category=1015060

파이썬에서의 큐의 구현

파이썬에서의 큐 구현 방식에는 대표적으로 리스트를 사용해서 구현하는 방식, queue모듈을 사용해서 구하는 방식, collection모듈의 deque를 사용하여 구현하는 방식 3가지 방식이 있습니다.

-덱(deque)은 양방향으로 자료를 처리할 수 있는 자료 구조를 말합니다. <=큐의 장점과 스택의 장점을 합친 자료 구조

1. 리스트를 사용하여 구현

q=[] q.append(1) q.append(2) q.append(3) print(q.pop(0)) print(q.pop(0)) print(q.pop(0))

출력 결과

2. queue모듈을 사용하여 구현

import queue q=queue.Queue() q.put(1) q.put(2) q.put(3) print(q.get()) print(q.get()) print(q.get())

출력 결과

3.deque를 사용하여 구현

from collections import deque q=deque() q.append(1) q.append(2) q.append(3) print(q.popleft()) print(q.popleft()) print(q.popleft())

출력 결과

+큐를 사용할 때 리스트를 사용하게 되면 0번째 인덱스에서 원소를 꺼낸 후 위치를 재조정하는 시간이 추가로 소요 되기때문에 리스트보다는 파이썬에서 제공하는 모듈을 사용하는 것이 좋습니다.

from http://lbdiaryl.tistory.com/160 by ccl(A) rewrite - 2021-09-16 20:26:57