Deque
Deque는 앞서 다루었던 Stack과 Queue의 기능을 전부 가지고 있는 자료구조이다.
Double-ended Queue라는 뜻으로 말 그대로 양방향으로 push, pop을 할 수 있다.
참고로 Stack과 Queue와 마찬가지로 Deque 또한 여러 프로그래밍 언어에서 라이브러리를 지원하기 때문에 구현에 대해서는 자세히 다루지 않겠다.
아래의 그림은 Deque를 간략히 표현한 그림이다.
Deque는 앞뒤로 push, pop을 수행할 수 있기 때문에 각각의 연산이 front, back으로 각각 나누어져 있다.
Deque의 주요 연산
- Push Front : Deque의 가장 앞에 데이터를 넣는 연산이다. Deque의 Front의 이전 위치에 데이터가 삽입된다.
- Push Back : Deque의 가장 뒤에 데이터를 넣는 연산이다. Deque의 Back의 다음 위치에 데이터가 삽입된다.
- Pop Front : Deque의 가장 앞에 존재하는 데이터를 뽑아내는 연산이다.
- Pop Back : Deque의 가장 뒤에 존재하는 데이터를 뽑아내는 연산이다.
Queue와 마찬가지로 Deque를 구현할 때에도 원형 큐를 이용한다. 또한 Front, Back의 위치를 저장하는 변수가 필요하다. Queue와의 구현 상의 차이점은 Front에서의 push, Back에서의 pop을 추가로 구현하는 것 뿐이다.
아래에는 원형 큐에 대한 그림이다.
댓글