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