개념
정의
접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
특징
- 선입선출(First-In First-Out, FIFO) 리스트
- 가장 먼저 들어온 데이터가 가장 먼저 나감
- 한쪽 끝(rear)에서 삽입이 일어남
- 반대쪽 끝(front)에서 삭제가 일어남
- 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 비동기 메세징(asynchronous messaging), 스트리밍(streaming), 너비 우선 탐색(breath first search) 등 소프트웨어 개발에서 널리 응용되고 있다.
파이썬
-
파이썬에서 큐를 사용하는 가장 간단한 방법은 범용 자료 구조인
list를 사용하는 것이다.list객체의pop(0)함수를 호출하면 첫 번째 데이터를 제거할수 있다.
하지만 이 방법은 추천되지 않는다. 글을 그대로 옮겨쓰기보단, 설명을 옮겨서 적어두겠다.
- 하지만 이렇게list를 큐 자료 구조의 효과를 내기 위해서 사용하는 것은 성능 측면에서 추천되지 않습니다. 파이썬의list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료 구조이기 때문에pop(0)
또는insert(0, x)는 성능적으로 매우 불리한 연산입니다.
이 두 연산은 시간 복잡도는O(n)이기 때문에 담고 있는 데이터의 개수가 많아질 수록 느려집니다. 왜냐하면 첫 번째 데이터를 제거한 후에는 그 뒤에 있는 모든 데이터를 앞으로 한 칸식 당겨줘야 하고, 맨 앞에서 데이터를 삽입하려면 그 전에 모든 데이터를 뒤로 한 칸씩 밀어줘야 하기 때문입니다.
이렇게 기존에queue가 담고 있던 모든 데이터를 앞/뒤로 쉬프트(shift)해주지 않으면queue[i]의 결과값이 정확하지 않을 것입니다. -
collections모듈의deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료 구조다. 이 deque를 활용해서 구현하는것이 파이썬 내의 큐 사용법 정석이다.-
from collections import dequedeque 는 그림으로 이해하면 편한데, 나중에 한번에 그려서 추가하겠다. 쉽게 설명하자면, 양옆에서 넣고 빼는게 가능한 자료형이고, 활용하기 쉬운편이다.
-
필기
-
스택과 마찬가지로, 개념을 이해하기 위해서는 백준 18258문제를 푸는게 좋다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
-
일단, 스택과 큐, 더 나아가서 힙은 무조건 알아둬야하는 자료형이다. 앞으로 학습하게 되는 dfs에는 스택, bfs, dp에는 큐를 활용하게 되는데, 정확하게 짚고 넘어가지 않으면 분명 브레이크가 걸릴것이다.
-
deque는 한번 더 정리하고 넘어가는게 좋을것 같다. deque는 양방향이기 때문에 append(), pop()과 더불어 appendleft(), popleft() 메소드가 있어 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거할 수 있다. appendleft(), popleft() 메소드는 각각 시간복잡도가 O(1)이기 때문에 리스트보다 더 효율적이다. 쉽게 말해서 큐를 풀이할때는 무조건 deque를 활용하는게 시간복잡도 면에서도, 풀이 면에서도 무조건 활용하는게 좋다.
-
공부 참고자료:
코드
백준 18258 풀이
#https://www.acmicpc.net/problem/18258
#큐 2
#18258
import sys
from collections import deque
input = sys.stdin.readline
queue = deque()
n = int(input())
for _ in range(n):
a = input().split()
if a[0] == 'push':
queue.append(a[1])
elif a[0] == 'pop':
if queue:
print(queue.popleft())
else:
print(-1)
elif a[0] == 'size':
print(len(queue))
elif a[0] == 'empty':
if queue:
print(0)
else:
print(1)
elif a[0] == 'front':
if queue:
print(queue[0])
else:
print(-1)
elif a[0] == 'back':
if queue:
print(queue[-1])
else:
print(-1)