[TIL] 자료구조 : 덱(Deque)

1. 덱(Deque,Double-ended-queue)

---

덱은 후단(rear)으로만 데이터를 삽입했던 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐. Double-ended Queue

• 양방향 연결리스트로 구 현이 되어있어 리스트보다 출입 연산이 효율적
• 실제로 많이 사용하지는 않는다 (양쪽의 입력과 출력을 모두 사용하는 경우도 잘 없다)
  • 큐를 구현 했을 때, 양쪽에서 출력 하고싶은 경우
  • 스택을 구현 했을 때, 양쪽에서 입력 하고싶은 경우 쓰게됨.
• 크기가 가변적이다.

2. 덱의 시간복잡도 (Big O)

---

• Insertion O(1)
• Deletion O(1)
• Search O(1) <-가장 앞, 뒤쪽만 가능

  But, 사이즈를 알아보는 연산의 경우
  - 배열인 경우 O(1)
  - 연결리스트인 경우 O(n)

3. 덱의 사용 예시

---

• 데이터 접근을 랜덤하게 하고 싶을 때, 검색을 거의 하지 않을 때 많이 사용.
• 복잡한 스케줄링에 큐/스텍 보다 효율이 잘나옴
• 우선순위 조절
• 큐와 스택을 모두 보완 하는 특성

덱의 메서드 목록

참고 자료(References)

---

https://velog.io/@kyy00n/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-stack-queue-deque#deque-double-ended-queue
https://jjeongttakgoori.tistory.com/32
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=justkukaro&logNo=220515795433