덱 (Deque)

덱 (Deque)

덱이란 double-ended queue의 줄임말로서 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

ADT Deque

• 객체 : n개의 element형의 요소들의 순서 있는 모임
• 연산 : 
  • create() ::=
  • intit(dq) 
  • is_empty(dq)
  • is_full(dq)
  • add_front(dq,e)
  • add_rear(dq,e)
  • delete_front(dq)
  • delete_rear(dq)
  • get_front(q)
  • get_rear(q)

 

덱은 스택과 큐의 연산들을 모두 가지고 있다.

add_front와 delete_front 연산은 스택의 push와 pop과 동일하다.

add_rear와 delete_rear 연산은 큐의 enqueue와 dequeue과 동일하다.

만약 덱의 front와 관련된 연산들만을 사용하면 스택이 되고,

삽입은 rear, 삭제는 front만을 사용하면 큐로 동작한다.

덱에서의 일련의 연산