데크

데크(Deque)(Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 일종이다. 큐(Queue)와 스택(Stack)의 특징을 결합한 형태로, 큐처럼 FIFO(First-In, First-Out) 방식으로 동작할 수도 있고, 스택처럼 LIFO(Last-In, First-Out) 방식으로 동작할 수도 있다.

데크는 일반적으로 다음과 같은 연산을 지원한다.

• push_front(item): 데크의 맨 앞에 item을 삽입한다.
• push_back(item): 데크의 맨 뒤에 item을 삽입한다.
• pop_front(): 데크의 맨 앞에서 item을 삭제하고 반환한다. (만약 데크가 비어있다면 예외 발생)
• pop_back(): 데크의 맨 뒤에서 item을 삭제하고 반환한다. (만약 데크가 비어있다면 예외 발생)
• peek_front(): 데크의 맨 앞의 item을 반환한다. (삭제는 하지 않음. 데크가 비어있다면 예외 발생)
• peek_back(): 데크의 맨 뒤의 item을 반환한다. (삭제는 하지 않음. 데크가 비어있다면 예외 발생)
• is_empty(): 데크가 비어있는지 확인한다.
• size(): 데크에 들어있는 item의 개수를 반환한다.

데크는 배열 기반이나 연결 리스트 기반으로 구현할 수 있다. 배열 기반 데크는 일반적으로 고정된 크기를 가지며, 연결 리스트 기반 데크는 동적으로 크기를 조절할 수 있다.

데크는 다양한 알고리즘 및 자료 구조 문제 해결에 활용될 수 있다. 예를 들어, 큐나 스택의 기능을 모두 필요로 하는 경우, 또는 양방향으로 탐색해야 하는 경우에 유용하게 사용될 수 있다. 또한, 윈도우 슬라이딩 알고리즘과 같은 특정 알고리즘을 효율적으로 구현하는 데 사용되기도 한다.