[백준] 18258번 : 큐2(큐)- 파이썬[Python]

문제

18258번: 큐 2

풀이

import sys
from collections import deque

t= int(sys.stdin.readline())
que = deque()   # 빈 큐 만들기

for i in range(t):
  command=sys.stdin.readline().split()


  if command[0]=='push':
    que.append(command[-1])
  elif command[0]=='pop':
    if not que:
      print(-1)
    else:
      print(que.popleft())
  elif command[0]=='size':
    print(len(que))
  elif command[0]=='empty':
    if not que:
      print(1)
    else:
      print(0)
  elif command[0]=='front':
    if not que:
      print(-1)
    else:
      print(que[0])
  elif command[0]=='back':
    if not que:
      print(-1)
    else:
      print(que[-1])

출처 : https://wellsw.tistory.com/122

 

deque함수를 사용하면 기존에 list로 큐를 구현하는 것보다 시간복잡도를 대폭 줄일 수 있다.
리스트의 경우 pop()하면 뒤의 원소들이 이동하기 때문에 시간복잡도가 O(n)인데,

출처 : https://dev.to/v_it_aly/python-deque-vs-listwh-25i9

Deque의 경우 리스트 하나하나가 객체로 이루어진 Double linked list로 구현되어 있기 때문에
양 끝의 추가, 삭제 (큐,스택)가 시간복잡도 O(0)을 만족하게 된다.