2. Queue & Deque

2-1. Queue란

FIFO (First In, First Out) : 선입선출

큐(Queue)은 연결리스트를 기반으로 한 자료구조로 Stack과 함께 자주 사용하는 자료구조입니다.

큐도 스택과 마찬가지로 다음 연산을 사용합니다.

push : 원소를 넣는 연산 \(O(1)\)
pop : 가장 맨 앞 원소(front)를 빼는 연산 \(O(1)\)

가장 먼저 들어온 것이 가장 먼저 나오는 선입선출 구조를 가지고 있습니다.

이렇게 순서대로 처리하는 특징은 다음과 같은 task에 활용할 수 있습니다.

OS Scheduling
우선순위가 같은 작업 (Print)
메시지 큐(Mesage Queue)

Python에서는 Queue 자료구조는 Stack과 Queue를 합친 Deque을 사용합니다. collections 라이브러리의 deque를 사용합니다.

가장 앞의 pop은 popleft 그리고 가장 오른쪽(상위) pop은 pop 연산을 사용합니다.
앞에서는 appendleft로 가장 오른쪽에서는 append로 원소를 추가할 수 있습니다.

다음 문제들로 기본적인 문법을 익햐봅시다.

[BOJ 10845] 큐

import sys
from collections import deque
input = sys.stdin.readline

q = deque()

for i in range(int(input())):
    S = input().split()
    if S[0] == 'push': q.append(S[1])
    elif S[0] == 'pop': print(q.popleft() if len(q) else -1)
    elif S[0] == 'size': print(len(q))
    elif S[0] == 'empty': print(int(len(q)==0))
    elif S[0] == 'front': print(q[0] if len(q) else -1)
    elif S[0] == 'back': print(q[-1] if len(q) else -1)

[BOJ 10866] 덱

import sys
from collections import deque
input = sys.stdin.readline

dq = deque()

for i in range(int(input())):
    S = input().split()
    if S[0] == 'push_front': dq.appendleft(S[1])
    elif S[0] == 'push_back': dq.append(S[1])
    elif S[0] == 'pop_front': print(dq.popleft() if len(dq) else -1)
    elif S[0] == 'pop_back': print(dq.pop() if len(dq) else -1)
    elif S[0] == 'size': print(len(dq))
    elif S[0] == 'empty': print(int(len(dq)==0))
    elif S[0] == 'front': print(dq[0] if len(dq) else -1)
    elif S[0] == 'back': print(dq[-1] if len(dq) else -1)

Chapter. 2

2-1. Queue란