0.들어가기에 앞서
지금까지 배운 자료구조 중 스택(Stack)과 큐(Queue)에 대해서 배워 본 바가 있다. 하지만 데크(Deque)라는 자료구조도 존재한다.
하지만 데크는 보다시피 C#에서는 자동완성이 되지도 않고 사용이 불가능한 자료구조이다.
검색해보니 파이썬, C++, 자바 등에서 사용 가능한 자료구조라고 하며, C#에서는 지원하지 않는 기능이라고 한다.
데크는 무엇이며 왜 C#에는 없는 기능일까? 한 번 알아보기로 했다.
1. Deque란 무엇인가?
Deque는 "double-ended que"의 약자로 스택과 큐를 일반화 한 것이다.
간단하게 말하자면, 스택과 큐의 기능을 동시에 가지고 있는 자료구조이다.
스택과 큐의 기능이 따지고 보면 아주 상반된 기능인데 이게 어떻게 가능한 것일까?
- 스택 : 선입후출 방식의 자료구조 ( 가장 마지막에 입력된 자료가 처리되는 방식 )
- 큐 : 선입선출 방식의 자료구조 ( 가장 처음에 입력된 자료가 처리되는 방식 )
이 두 가지 기능을 동시에 사용할 수 있다는 뜻은, 가장 쉽게 생각했을 때 선입 선출도 가능하고 선입 후출도 가능하다는 것으로 생각해볼 수 있다.
데크는 위와 같이 데이터를 앞에서도 삽입할 수 있고 제거할 수 있으며, 뒤로도 삽입할 수 있고 제거할 수 있는 방식이다. 그 약자와 같이 '양쪽으로 사용할 수 있는 Queue'인 셈이다. 이게 어떻게 가능할까? Deque의 기능을 알아보면서 어떤 식으로 작동하는지 알아보자.
2. Deque의 메서드
Deque에서 자주 쓰이는 메서드를 알아보고자 한다. 크게 아래와 같이 분류할 수 있다고 생각했다.
-
삽입의 기능
- deque.append(x) : x를 데크의 오른쪽 끝에 삽입한다.
- deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입한다.
- deque.insert(x, i) : x를 데크의 i번째 위치에 삽입
-
제거의 기능
- deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다.
- deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다.
-
확장의 기능 ( 데크의 크기를 제한해 뒀을 경우 사용함 )
- extend(iterable) : iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장한다.
- extendleft(iterable) : iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장한다.
-
제거의 기능(내용을 찾기)
- deque.remove(x) : x를 데크에서 찾아 삭제한다 ( x가 데크에 없을 시 오류 )
-
회전
- deque.rotate(i) : 양수면 오른쪽, 음수면 왼쪽으로 데이터를 회전시킴
이와 같이 삽입이나 삭제에서도 양방향으로 가능하고, 마치 앞뒤로 스택이 달려있는 형태처럼 작동하는 것을 알 수 있다.
3. Deque의 특징과 사용처
Deque는 위와 같이 삽입과 삭제에 있어서 효율성이 좋은 특성을 가진다. 따라서 Push와 Pop을 하는 상황에서 유용하게 쓰일 수 있는 자료구조이다.
반면에 해당 구조에서 탐색 등의 능력에선 효율성이 떨어지는 특성을 보이는데,
처음부터 자료를 찾아봐야 하는 O(n)의 효율성을 가진 특성과 더불어,
'데이터가 연속적으로 저장되지 않는다'는 특성이 존재한다.
따라서 사용할 수 있는 경우는 아래와 같이 사용할 수 있다.
- 비슷한 특성을 가진 List보다 빠른 속도로, Push와 Pop이 빈번한 알고리즘에서 유용하게 사용
