Deque(ue) 덱

Double-Ended queue : 양방향 큐

덱의 특징

이름 그대로 front/rear 양방향에서 삽입/삭제 모두 수행 가능한 자료구조이다.
queue를 상속받아 덱을 구현한다.

몇가지 메소드는 인터페이스 변경이 필요하며,
몇가지 메소드는 추가적이 구현이 요구된다. 

- 선형 자료구조 중 리스트 다음으로 자유로운 자료구조
- 덱을 그대로 스택/큐 로 활용할 수 있다.
	-> 데이터와 메소드의 기능이 동일하게 대응하기 때문

주요 데이터

- front : 삽입/삭제 가능한 덱의 전단
- rear : 삽입/삭제 가능한 덱의 전단

스택의 주요연산

*생성자 :

Class CircularDeque(CircularQueue):
  def __init__( self ) :
      super().__init__()



*인터페이스 변경 멤버s :
 
  - deleteFront()	
      - 큐의 dequeue() 인터페이스 변경으로 구현

  - addRear()			
      - 큐의 enqueue() 인터페이스 변경으로 구현 
      - Stack의 push() 메소드와 완벽히 대응

  - getFront()		
      -큐의 peek() 인터페이스 변경으로 구현



*추가 구현 메소드 :

	- addFront()	
      	- front의 반시계방향 회전 필요
      
    - deleteRear()	
      	- rear의 반시계 방향 회전 필요
        
    - getRear()
        - rear의 반시계 방향 회전 필요
        - 스택의 peek() 메소드와 완벽히 대응
      
*재사용 멤버s (구현x) : 

	- isEmpty()
    - isFull()
    - size()
    - clear()

구현방법

1. 파이썬 내장 리스트 : 배열로 구현 
2. 연결된 구조를 이용한 스택 구현 : 단순연결리스트 (singly linked list)

파이썬 Array 기반 스택 구현 시 항목의 삽입,삭제 위치는 최후단이 유리하다

why? : 파이썬 내장 리스트인 array는 최후단삽입을 기본으로 한다 
  - 후단 이용 삽입/삭제 시 : O(1)
  - 전단 이용 삽입/삭제 시 : O(n)

덱의 응용

-