문제 17
C++ Queue
처음에 빈 큐가 있다.
$Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
push x: 큐의 뒤에 정수 $x$를 추가한다.pop: 큐의 맨 앞 원소를 삭제한다.front: 큐의 맨 앞 원소를 출력한다.back: 큐의 맨 뒤 원소를 출력한다.size: 큐의 크기를 출력한다.
pop, front, back 쿼리는 항상 올바른 상태에서만 주어진다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $x$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9)$
출력
front, back, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
9 push 3 push 5 front back size pop front push 7 back
예제 출력 1
3 5 2 5 7
공식 해설
먼저 넣은 원소부터 제거하므로 선입선출 자료구조인 큐를 사용한다. 새 원소는 뒤에 추가하고 삭제는 앞에서만 수행한다.
front와 back에는 양 끝 원소를, size에는 남은 원소 수를 출력한다. 조회·삭제는 큐가 비어 있지 않을 때만 주어진다.
각 명령은 분할 상환 $O(1)$에 처리할 수 있으므로 전체 시간복잡도와 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
C++에서는 queue<int>의 push(x), pop(), front(), back(), size()로 처리한다.
C 구현
push 횟수가 $Q$ 이하이므로 $Q$칸 배열에 head와 tail을 둔다. 추가는 tail, 삭제는 head를 늘리며 앞·뒤는 a[head], a[tail - 1]이다. 원소를 앞으로 당기는 작업은 하지 않는다.
Python 구현
collections.deque의 append(), popleft(), q[0], q[-1]을 사용한다. list.pop(0)는 남은 원소를 이동하므로 $Q$가 커지면 느려진다.
from collections import deque
q = deque()
q.append(x)
front = q[0]
q.popleft()Java 구현
ArrayDeque<Integer>의 addLast(), removeFirst(), peekFirst(), peekLast(), size()를 사용한다. 뒤에 넣고 앞에서 꺼내는 연산은 다음과 같다.
ArrayDeque<Integer> q = new ArrayDeque<>();
q.addLast(x);
int front = q.peekFirst();
q.removeFirst();Rust 구현
VecDeque<i32>의 push_back(), pop_front(), front(), back()을 사용한다. Vec의 첫 원소를 remove(0)로 지우는 구현은 선형 시간이므로 피한다.
front()는 참조를, pop_front()는 제거한 값을 반환한다. 조회·삭제가 가능한 상태로 주어지므로 front()의 반환값을 unwrap()으로 얻을 수 있다.
use std::collections::VecDeque;
let mut q = VecDeque::<i32>::new();
q.push_back(x);
let front = *q.front().unwrap();
q.pop_front();JavaScript 구현
큐는 배열과 앞쪽 인덱스 head로 구현한다. 삽입은 q.push(x), 삭제는 head++, 앞 원소는 q[head], 뒤 원소는 q[q.length - 1], 크기는 q.length - head이다.
Array.shift()를 반복하면 남은 원소를 이동시킬 수 있으므로 피한다. 이미 꺼낸 숫자 칸을 남겨 두어도 총 $Q$개 이하이며 $O(Q)$ 공간이다. 큐가 비었다가 다시 삽입되는 경우에도 head를 임의로 $0$으로 돌리지 않는다.