덱

큐와 데이터는 동일

객체: 전단과 후단을 통한 접근을 허용하는 요소들의 모음
연산:
▪ addFront(e): 주어진 요소 e를 덱의 맨앞에 추가한다.
▪ deleteFront(): 덱이 비어있지 않으면 맨앞 요소를 삭제하고 반환한다.
▪ addRear(e): 주어진 요소 e를 덱의 맨뒤에 추가한다.
▪ deleteRear(): 덱이 비어있지 않으면 맨뒤 요소를 삭제하고 반환한다.
▪ isEmpty(): 큐가 비어있으면 true를 아니면 false를 반환한다.
▪ getFront(): 비어있지 않으면 맨앞 요소를 삭제하지 않고 반환한다.
▪ getRear(): 비어있지 않으면 맨뒤 요소를 삭제하지 않고 반환한다.
▪ isFull(): 덱이 가득 차 있으면 true을 아니면 false을 반환한다.
▪ display(): 덱의 모든 요소들의 출력한다.

덱의 구현

• 배열 사용
  • 원형큐 클래스를 확장하여 구현 -> 원형 덱
  • "상속"기능 사용
• 연결리스트 사용
  • 양쪽에서 삽입, 삭제가 가능해야 함.
  • 이중연결 리스트 사용

원형 덱의 연산

• 큐와 데이터는 동일
• 큐와 동일한 연산
  • isEmpty(), isFull(), display(), size()
  • addRear() : 원형큐의 enqueue()
  • deleteFront() : 원형큐의 dequeue()
  • getFront() : 원형큐의 peek()
• 덱에 추가된 연산
  • addFront(e)
  • deleteRear()
  • getRear()

원형 덱의 연산

• 덱의 연산에서 반대방향의 회전이 필요한 연산

rear ← (rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
front ← (front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

미로 탐색: 너비 우선 탐색

• 너비 우선 탐색(BFS, Breadth First Search) 

미로 탐색: 깊이 우선 탐색

• 깊이 우선 탐색(DFS, Depth First Search)