[자료구조] Deque에 대해 알아보고 구현해보기 (Swift)

Deque란?

Deque 자료구조는 Queue의 특성과 Stack의 특성을 모두 갖는 자료구조 입니다.

왼쪽, 오른쪽 방향으로 삽입 삭제가 가능합니다.

왼쪽으로 삽입 오른쪽에서 삭제, 오른쪽으로 삽입 왼쪽에서 삭제 한다면 Queue 자료구조에 특성일 것이고
왼쪽으로 삽입 왼쪽에서 삭제, 오른쪽으로 삽입 오른쪽에서 삭제 한다면 Stack 자료구조의 특성일 것입니다.

시간 복잡도

• 삽입 : $O(1)$
• 삭제 : $O(1)$
• 검색 : $O(n)$

구현

Deque을 어떻게 구현할 수 있을까요?

연결리스트를 사용하지 않고, Array 2개를 사용해서 구현해보았습니다.

Queue를 구현할 때, index를 사용해서 구현한 것 처럼 요소를 가리킬 2개의 index를 두었습니다.

왼쪽이나 오른쪽으로 삽입하는 연산은 어떻게 구현할 수 있을까요?
각 뱡향에 따라 사용될 Array에 단순히 append 해주었습니다.

그렇다면 왼쪽에서 삭제 연산을 구현할 때, 왼쪽 Array에서 removeLast를 해서 삭제해주면 되겠네요.

하지만 하나 더 생각해야할 것이 왼쪽 Array가 비어있고, 오른쪽 Array가 비어있지 않다면
오른쪽 Array에서 가져와서 삭제연산을 해줘야 할 것입니다.

이 삭제 연산을 구현하기 위해 요소를 가리킬 index를 사용하였습니다
오른쪽 Array를 가리키고 있는 index의 요소를 반환하고 index 값에 1을 늘려주는 방식으로 구현할 수 있습니다.

오른쪽 삭제 연산도 마찬가지 입니다.

Deque이 비어있는지, 요소의 개수 등을 확인할 때도 이 index를 고려해서 구해주었습니다.

isEmpty, size, front, back, pushLeft, popLeft, pushRight, popRight를 구현하였습니다.

후기

Stack과 Queue 보다는 까다로웠습니다.
연결리스트를 사용하지 않고 구현해봤는데, 원하는 방식대로 동작해서 뿌듯했고 백준에서 Deque 문제에 테스트해보았을 때도 문제는 없었습니다.