자료구조 공부를 하다가 큐를 공부하는데, 연습문제에 양방향 대기열인 Deque를 구현하라는 문제가 나왔다. 방금 배운 큐 와는 좀 다른 자료구조인것같아서 알아보았다.
아무리 봐도 나는 이게 선입선출 방식의 큐 라는 게 잘 이해가 가지 않았다....
큐(Queue)
선입선출(FIFO) 방식으로 작동하는 자료구조로, 1, 2, 3, 4 ,5 순서로 값이 추가되었으면 1, 2, 3, 4, 5 순서로 제거된다. front 와 rear 를 이용하여 맨 처음 요소의 인덱스와 맨 끝 요소( + 1) 인덱스를 저장한다.
데크(Deque)
덱(Deque)는 양방향에서 요소를 추가하고 제거할 수 있는 양방향 큐 이다. 단방향 큐를 일반적인 리스트(list) 로 구현할 때 요소를 추가하고 제거할 때의 복잡도는 O(n) 인 반면, 양방향에서 값을 추가하고 제거하는 처리의 복잡도는 O(1)로 구현할 수 있다.
큐와 데크의 다른 점은 위의 그림과 같다. 큐는 맨 뒤 요소 (rear) 에 값을 추가하고, 맨 앞 요소 (front) 의 값을 삭제하는 방식이지만 데크는 맨 앞에 추가할수고, 맨 뒤를 삭제할 수도 있다.
즉, 스택처럼 사용할 수도 있고 큐 처럼 사용할 수도 있는 자료구조인 것이다.
어려운 구조는 아닌데 선입선출 방식에 집착하다 보니 헷갈렸다. 아예 다른 자료구조라고 생각하고 이해하는 편이 더 나았다.
구현
Deque 구현(C)
고민했던 부분
배열로 구현하는데, front의 인덱스가 0일때 push_front를 할 때나 rear의 인덱스가 max일때 push_end 를 할 때의 처리를 어떻게 해야할지 고민했다.
처음 구현할 때는 front의 인덱스가 0일때 push_front 를 하면 에러를 출력했지만 뭔가 덱에서 원하는 구조는 아닌 것 같았다.
그래서 front 의 인덱스가 0일때 push_front 를 실행하면 인덱스가 뒤로 돌아 max 에 값이 추가되고, front 의 인덱스가 max가 된다. print 를 실행하면 front 부터 rear 까지 출력하기 때문에 인덱스가 뒤쪽에 있어도 순서대로 출력된다.
굳이 배열로 하지 않을거라면, 연결리스트 등을 사용하는 편이 더 나을 것 같다. 라고 생각했지만, 위 댓글에서 말씀주셨듯이
Deque 안에 있는 특정 Element 로 접근할때 시간복잡도가 O(1) 인 것을 보장해주는 자료구조 이기 때문에 구현이 복잡해도 배열로 만들어야 한다!
+) 시간복잡도를 생각하지 않은 단순 구현은 연결리스트로 구현해 놓은 책들도 있다.
참고자료
Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편
