[자료구조] 파이썬 Queue

Queue란

큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조입니다.(FIFO 구조)
큐에 데이터를 추가하는 작업을 인큐, 꺼내는 작업을 디큐라고 합니다
데이터를 꺼내는 쪽을 프런트 데이터를 넣는 쪽을 리어 라고합니다.

인큐

데이터를 인큐 한다면

queue = [1,2,3]
queue.append(4)
queue.append(5)
[1,2,3,4,5]
queue.pop(0)
1
queue.pop(0)
2

와 같이 구현 할 수 있다. 하지만 pop(0)의 시간 복잡도는 O(N)이기 떄문에 연산이 느려진다. 때문에 list 자료 구조로 사용하지 않는다
그렇다면 python은 어떤것을 쓰는가

collections 모듈의 deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료 구조입니다.

deque는 list에는 없는 popleft()라는 메서드를 제공하는데요. 이 메서드를 사용하면 첫 번째 데이터를 제거할 수 있습니다. 데이터의 흐름은 list 객체의 pop(0) 메서드를 사용할 때 처럼 뒤에서 앞으로 흐르게 됩니다.

from collections import deque

queue = deque([1,2,3])
queue.append(4)
queue.append(5)
print(queue)
deque([4, 5, 6, 7, 8])
print(queue.popleft())
1
print(queue.popleft())
2
print(queue)
deque([3, 4, 5])

Queue를 활용한 기본 백준 문제

https://www.acmicpc.net/problem/18258

[18258번: 큐 2

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net](https://www.acmicpc.net/problem/18258)

위 문제는 기본 queue를 구현하는 문제입니다.

from collections import deque
import sys

N = int(sys.stdin.readline())
queue = deque()
for i in range(N):
  command = sys.stdin.readline().split()
  if(command[0] == 'push'):
    queue.append(command[1])
  if(command[0] == 'pop'):
    if(len(queue) == 0):
      print(-1)
    else:
      print(queue.popleft())
  if(command[0] == 'size'):
    print(len(queue))
  if(command[0] == 'empty'):
    print(1) if len(queue) == 0 else print(0)
  if(command[0] == 'front'):
    print(-1) if len(queue) == 0 else print(queue[0])
  if(command[0] == 'back'):
    print(-1) if len(queue) == 0 else print(queue[-1])