[10845] 큐

 

deque 라는 자료구조가 있는데

양방향으로 append랑 pop을 지원한다.

원래 list에서 pop(0), insert(0, v)는 O(n)의 시간복잡도를 가지는데

deque에서는 단순히 O(1)의 시간복잡도를 가진다.

 

따라서 큐와 같이 앞에도 데이터 입출력이 이루어질 때 효과적이다.

import sys
from collections import deque 

N = int(sys.stdin.readline().strip())

q = deque([])

for _ in range(N):
    commands = sys.stdin.readline().split()

    if commands[0] == "push":
        q.append(int(commands[1]))
    elif commands[0] == "pop":
        print(q.popleft() if len(q) else -1)
    elif commands[0] == "size":
        print(len(q))
    elif commands[0] == "empty":
        print(0 if len(q) else 1)
    elif commands[0] == "front":
        print(q[0] if len(q) else -1)
    elif commands[0] == "back":
        print(q[-1] if len(q) else -1)