덱

양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐 연산을 모두 지원하는 자료구조

front와 rear에서 모두 삽입과 삭제가 가능하지만, 중간에서의 삽입과 삭제는 허용되지 않는다.

Deque ADT

• Deque() : 비어 있는 새로운 덱을 만든다.
• isEmpty() : 덱이 비어있으면 True를 아니면 False를 반환
• addFront(x) : x를 덱 맨 앞에 추가
• deleteFront() : 맨 앞의 항목을 꺼내서 반환
• getFront() : 맨 앞의 항목을 반환
• addRear(x) : x를 덱 맨 뒤에 추가
• deleteRear() : 맨 뒤 항목을 꺼내서 반환
• getRear() : 맨 뒤의 항목을 반환
• isFull() : 덱이 가득차 있으면 True, 아니면 False
• siez() : 덱의 모든 항목들의 개수 반환
• clear() : 덱을 공백상태로 만든다.

덱의 구현

원형 큐에서 처럼 front와 rear를 두면, 삽입과 삭제에서의 시간복잡도를 O(1)으로 만들 수 있다.
원형 큐를 상속받아서 front와 rear를 사용하여 구현했다.

• 원형 큐

  MAX_QSIZE = 10				    
  class CircularQueue :
      def __init__( self ) :		
          self.front = 0			
          self.rear = 0			
          self.items = [None] * MAX_QSIZE	
  
      def isEmpty( self ) : return self.front == self.rear
      def isFull( self ) : return self.front == (self.rear+1)%MAX_QSIZE
      def clear( self ) : self.front = self.rear
  
      def enqueue( self, item ):
          if not self.isFull():			            
              self.rear = (self.rear+1)% MAX_QSIZE	
              self.items[self.rear] = item		    
  
      def dequeue( self ):
          if not self.isEmpty():			            
              self.front = (self.front+1)% MAX_QSIZE	
              return self.items[self.front]	        
  
      def peek( self ):
          if not self.isEmpty():
              return self.items[(self.front + 1) % MAX_QSIZE]
  
      def size( self ) :
         return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
  
      def display( self ):
          out = []
          if self.front < self.rear :
              out = self.items[self.front+1:self.rear+1]
          else:
              out = self.items[self.front+1:MAX_QSIZE] \
                  + self.items[0:self.rear+1]		
          print("[f=%s,r=%d] ==> "%(self.front, self.rear), out)
  

class CircularDeque(CircularQueue) :	          
    def __init__( self ) :		                  
        super().__init__()		                  

    def addRear( self, item ): self.enqueue(item )
    def deleteFront( self ): return self.dequeue()
    def getFront( self ): return self.peek()		
   
    def addFront( self, item ):			          
        if not self.isFull():
            self.items[self.front] = item        
            self.front = self.front - 1		      
            if self.front < 0 : self.front = MAX_QSIZE - 1

    def deleteRear( self ):			      
        if not self.isEmpty():
            item = self.items[self.rear]
            self.rear = self.rear - 1		
            if self.rear < 0 : self.rear = MAX_QSIZE - 1
            return item			     

    def getRear( self ):			 
        return self.items[self.rear]

테스트

dq = CircularDeque()		        
for i in range(9):			        
	if i%2==0 : dq.addRear(i)		
	else : dq.addFront(i)		    
dq.display()				        
for i in range(2): dq.deleteFront()	
for i in range(3): dq.deleteRear()	
dq.display()
for i in range(9,14): dq.addFront(i)
dq.display()
>>
[f=6,r=5] ==>  [7, 5, 3, 1, 0, 2, 4, 6, 8]
[f=8,r=2] ==>  [3, 1, 0, 2]
[f=3,r=2] ==>  [13, 12, 11, 10, 9, 3, 1, 0, 2]

python 에서의 deque

python의 기본 모듈이 collections에서 deque를 import해서 사용할 수 있다.
python collections.deque 참고