자료구조 - 덱(deque)

목차

1. 덱이란
2. 덱의 연산

---

덱이란?

덱(deque)은 double-ended queue의 줄임말로서 전단과 후단에서 모두 삼입과 삭제가 가능한 큐를 말합니다. 다만 여전히 중간에는 삼입, 삭제는 불가능합니다.

덱의 구조

 

반응형

---

덱의 연산

덱은 큐에서 몇가지 연산이 추가된다.

• addFront(e): 새로운 요소 e를 전단에 추가
• addRear(e): 새로운 요소 e를 후단에 추가
• deleteFront(): 덱의 전단 요소를 꺼내서 반환
• deleteRear(): 덱의 후단 요소를 꺼내서 반환
• getFront(): 덱의 전단 요소를 삭제하지 않고 반환
• getRear(): 덱의 후단 요소를 삭제하지 않고 반환
• isEmpty(): 덱이 비어있으면 True를 아니면 False를 반환
• isFull(): 덱이 가득 차 있으면 True를 아니면 False를 반환
• size(): 덱에 들어있는 전체 요소의 수를 반환

주의해야할 연산은 front와 rear를 감소시켜야 하는 deleteRear와 addFront입니다. 이들은 원형 큐의 enqueue나 dequeue와는 다르게 인덱스를 하나 줄여야 하는데, 이것을 반시계 방향 회전을 의미한다.

원형 덱의 삼입/삭제 연산

연산은 이런 방식으로 이루어 집니다.

b를 보면 C를 삭제할 경우에 rear가 반시계 방향으로 바뀌는 모습을 볼 수 있습니다. 또한 c는 전단 삼입을 하는 경우인데, 이러면 front가 반시계 방향으로 회전하게 됩니다.