10845번 - 큐

💡 Queue는 앞과 뒤에 원소를 추가하거나 삭제할 때 리스트 보다 빠르다!!

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

dq = deque()

for _ in range(N):
    
    command = list(input().rstrip().split(' '))
    
    if command[0] == "push":
        dq.append(command[1])
    elif command[0] == "pop":
        if dq:
            print(dq.popleft())
        else:
            print(-1)
    elif command[0] == "size":
        print(len(dq))
    elif command[0] == "empty":
        if dq:
            print(0)
        else:
            print(1)
    elif command[0] == "front":
        if dq:
            print(dq[0])
        else:
            print(-1)
    else:
        if dq:
            print(dq[-1])
        else:
            print(-1)

• 위 문제는 그렇게 어렵지 않았다.
• Python에서는 Queue를 사용하기 위해서 deque를 사용하며, 사용하기 위해선 "from collections import deque"를 통해서 라이브러리를 import하고 사용할 수 있다!!
• 명령에 맞춰서 deque의 핵심적인 메소드인 popleft()를 사용해서 구현하였다

💡 List vs Deque

왼쪽: List / 오른쪽:Deque
끝에 추가 (append) => ✅ O(1) vs ✅ O(1)
끝에서 제거 (pop) => ✅ O(1) vs ✅ O(1)
앞에 추가 (insert(0, x)) => ❌ O(n) vs ✅ O(1)
앞에서 제거 (pop(0)) => ❌ O(n) vs ✅ O(1)

결론적으로 값을 앞이나 뒤에서 뺴거나 추가할 경우에는 List보다 Deque가 빠르다!!