부산대학교자료구조
Scientific Inference Lab

First In, First Out

Deque ADT

덱(deque)은 앞쪽과 뒤쪽 양 끝에서 모두 값을 추가하거나 삭제하는 ADT다. 같은 끝을 쓰면 스택, 반대 끝을 쓰면 큐처럼 동작하며, Python의 collections.deque는 양 끝 연산을 O(1)로 제공한다.

양 끝 연산add_front, remove_front, add_rear, remove_rear가 있다.
스택과 큐 표현넣고 빼는 끝이 같으면 LIFO, 다르면 FIFO가 된다.
collections.dequeappend와 popleft로 큐를 만들며 양 끝이 O(1)이다.

넣고 빼는 끝을 고르면 덱이 스택도 큐도 된다

사용 방식과 단계를 바꾸면 A, B, C를 넣고 모두 꺼낼 때 쓰는 연산, 덱의 모양, 꺼낸 순서가 바뀐다.

위 줄은 덱이며 왼쪽이 앞쪽, 오른쪽이 뒤쪽이다. 초록 테두리 칸은 방금 넣은 값이다. 아래 줄은 꺼낸 순서다.

회문 검사는 앞쪽과 뒤쪽에서 하나씩 꺼내 비교한다

단어와 비교 횟수를 바꾸면 양 끝에서 꺼낸 문자 쌍, 덱에 남은 문자, 판정이 바뀐다.

칸 하나가 덱에 넣은 문자다. 회색 점선 칸은 이미 꺼낸 문자, 초록 칸은 방금 비교해 같았던 쌍, 빨간 칸은 달랐던 쌍이다.