[자료구조] 덱

덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다.

덱의 구조

 

덱의 추상자료형

객체 : n개의 element형의 요소들의 순서 있는 모임
연산 : 
  create() ::= 덱을 생성한다.
  init(dq) ::= 덱을 초기화한다.
  is_empty(dq) ::= 덱이 공백 상태인지를 검사한다.
  is_full(dq) ::= 덱이 포화 상태인지를 검사한다.
  add_front(dq, e) ::= 덱의 앞에 요소를 추가한다.
  add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다.
  delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제한다.
  delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제한다.
  get_front(dq) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
  get_rear(dq) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.

 

덱에서의 일련의 연산

 

 

참고

• C언어로 쉽게 풀어쓴 자료구조 책