[자료구조]덱(Deque)의 이해와 구현

큐는 뒤로 넣고 앞으로 빼는 자료구조 !!

이다면

덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조 ! 이다 !!

deque

double-ended queue 의 줄임말이다.

따라서 덱의 ADT를 구성하는 핵심 함수 네 가지의 기능은 !

• 앞으로 넣기
• 뒤로 넣기
• 앞에서 빼기
• 뒤에서 빼기 이다.

이를 통해 덱의 ADT를 정의하자면 ...!

Operation:

void DequeInit(Deque * pdeq);
- 덱의 초기화 진행
- 덱 생성 후 제일 먼저 호출되어야 하는 함수

int DQIsEmpty(Deque * pdeq );
- 덱이 빈 경우 True 아니면 False

void DQAddFirst(Deque * pdeq, Data data);
- 덱의 머리에 데이터 저장, data로 전달된 값을 저장

void DQAddLast(Deque * pdeq);
- 덱의 꼬리에 데이터 저장, data로 전달된 값을 저장

Data DQRemoveFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 반환/소멸

Data DQRemoveLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환/소멸

Data DQGetFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환

Data DQGetLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환

덱 또한 연결리스트/배열로 구현 가능하지만 베스트는 양방향 연결리스트이다.

코드는... 그저 앞서 짠것들과 그렇게 크게 차이 나지않는다.
양방향 연결리스트에서 앞에서 삽입~ 뒤에서 삽입~ 앞에서 삭제 ~ 뒤에서 삭제~ 생각하면 되기 때문이당~
그냥..모든경우의 함수를 생각해주면된당!

디큐라고 안부르는 이유는 dequeue와 헷갈리기 때문 !!

덱은 스택 + 큐 !
-> 논란이 있다.. 그저 삽입하는 방법과 빼는 방법이 동일할뿐.... 나머지는 음...ㅋ

덱의 구현을 위한 양방향 연결리스트의 구조는 이전과 다른 점은 tail을 지정해준다는 점이다 !
code Level은 쉬우니 한번 쳐보고 말아야징