Double-Ended Queue

Deque?

큐는 분명히 한 쪽에만 데이터를 삽입할 수 있다. 괜히 FIFO란 말이 있겠는가. 여기서 확장해서, 양쪽으로 데이터의 삽입과 삭제를 할 수 있게 한 것이 Double-Ended Queue, 줄여서 Deque, a.k.a 'Deck', 덱이다.

 

덱의 필수요소

• Add First e: 덱의 맨 앞에 원소 e 삽입.
• Add Last e: 덱의 맨 뒤에 원소 e 삽입.
• Delete First: 덱 맨 앞의 원소 뽑아서 return하고 삭제. 덱이 비어 있으면 에러 return.
• Delete Last: 덱 맨 뒤의 원소 뽑아서 return하고 삭제. 덱이 비어 있으면 에러 return.
• First: 덱 맨 앞의 원소를 return. 비어 있으면 error 리턴.
• Last: 덱 맨 뒤의 원소를 return. 비어 있으면 error 리턴.
• Empty: 덱이 비어 있으면 True, 아니면 False 리턴.
• Length: 덱의 길이 return.

실제 덱의 예시

빈 덱 D가 있다고 가정하자...

명령어	return	덱의 상태
Add First a		a
Add First b		b, a
Add Last c		b, a, c
First	b	b, a, c
Last	c	b, a, c
Empty	False	b, a, c
Length	3	b, a, c
Delete Last	c	b, a
Delete First	b	a
Length	1	a

덱의 구현 예시

class Deque:
  def __init__(self):
    self.d=[]
  def length(self):
    return len(self.d)
  def empty(self):
    return not self.length()
  def AddFirst(self, e):
    self.d=[e]+self.d
  def AddLast(self, e):
    self.d=self.d+[e]
  def DelectFirst(self):
    if self.empty():
      raise Empty()
    else:
      x=self.d[0]
      self.d=self.d[1:]
      return x
  def DelectLast(self):
    if self.empty():
      raise Empty()
    else:
      x=self.d[-1]
      self.d=self.d[:-1]
      return x
  def First(self):
    if self.empty():
      raise Empty()
    else:
      return self.d[0]
  def Last(self):
    if self.empty():
      raise Empty()
    else:
      return self.d[-1]