덱(Deque <- double-ended queue)은 양쪽끝(맨앞, 맨뒤)에서 삽입과 삭제가 모두 가능한 자료구조인데 마지막으로 들어간 자료가 젤 먼저 나오는 (LIFO = Last In First Out) 구조를 가진 스택(Stack) 과 젤 먼저 들어간 자료가 젤 먼저 나오게 되는 (FIFO) 큐(Queue) 를 합쳐놓은것과 동일하다.
근데 여기서 의문점이 생긴다.
그냥 양쪽에서 push, pop 할 용도라던지 스택과 큐를 합쳐놓은 기능이 필요하면 스택 , 큐를 따로 따로 생성해서 원하는 목적을 충분히 이룰수 있지 않겠느냐? 와 도대체 이런 자료구조는 언제 사용하면 좋을지? 이다
우선 첫번째 부터 의문점을 해결해보자
...
두번째는 실생활에서 덱을 이용한 사례를 참고하면 된다.
구현은 이중연결리스트나 배열을 이용하면 구현 가능하다.
자바에서는 덱 자료구조를 위해 Deque<E>의 인터페이스를 제공하고 인터페이스의 구현체로 ArrayDeque<E>(배열로 구현)나 LinkedList<E> (연결리스트로 구현)를 상황에 맞게 사용하면 되고, C++에서는 st::deque 을 제공해준다.
1
2
|
Deque<Integer> arrayDeque = new ArrayDeque<>();
Deque<Integer> listDeque = new LinkedList<>();
|
레퍼런스
'자료구조(Data Structure)' 카테고리의 다른 글
해시테이블(Hash Table) (0) | 2019.06.18 |
---|---|
셋(Set) (0) | 2019.06.18 |
이진탐색트리(Binary Search Tree) (0) | 2019.06.18 |
이진트리(Binary Tree) (0) | 2019.06.18 |
우선순위큐(Priority Queue) (0) | 2019.06.18 |