[Python 자료구조 #큐2] 원형 덱

* 덱(데크, deque)

• 큐가  FIFO의 단 방향으로만 삽입 삭제가 가능한 자료구조라면, 덱은 전단(front)과 후단(rear) 양쪽에서 삽입과 삭제가 가능한 자료구조이다.
• 원형 큐를 상속하여 원형 덱(CircularDeque) 클래스를 구현한다.
• 덱 ADT(추상 자료형)
• CircularQueue는 이전 포스팅 참고.

from CircularQueue import *	# CircularQueue를 포함한다.

class CircularDeque(CircularQueue) :	         	 # 원형 큐의 크기는 10으로 설정했었다.
#    def __init__( self ) :		                  # 여기서는 생성자를 굳이 호출할 필요가 없다.
#        super().__init__()		                  # 부모의 생성자를 호출하기 위해서는 super().를 붙인다.


# 이미 구현된 ADT이므로 인터페이스만 만들어준다.
    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 ):			 # 후단 peek
        return self.items[self.rear]

자식 생성자에 부모 생성자를 꼭 호출해와야 하는 것은 아니다.
자식 생성자를 따로 생성하지 않으면 부모 생성자를 자동으로 실행한다. 그러나, 부모 생성자가 인수를 필요로 하는 경우에는 자식 생성자는 인수를 입력하지 않았기에 argument(인수)오류가 발생한다.
자식 생성자를 굳이 따로 선언하면 부모와 다른 생성자가 생성되는 것이고,
부모의 생성자를 호출하고 싶으면 super().을 붙어야 한다.
참고 : https://newbie-developer.tistory.com/146

덱 예제

dq = CircularDeque()	# 덱 객체 생성. front=rear=0


# 첫 번째 실행
for i in range(9):	# i : 0~8
    if i % 2 == 0:	# 짝수는 후단에 삽입
        dq.addRear(i)
    else:		# 홀수는 전단에 삽입
        dq.addFront(i)
dq.display()		# front=6, rear=5


# 두 번째 실행
for i in range(2):	# 전단에서 두 번의 삭제 : f=8
    dq.deleteFront() 
for i in range(3):	# 후단에서 세 번의 삭제 : r=2
    dq.deleteRear()
dq.display()


# 세 번째 실행
for i in range(9, 14):	#i : 9~13 : front=3
    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]

 

 

1. 첫 번째 dq.display()에 대한 결과는 

[f=6,r=5] ==>  [7, 5, 3, 1, 0, 2, 4, 6, 8] 이다.

초기에 비어 있는 리스트의 요소에는 None값이 들어있다.

 

print(dq)로 dq의 리스트 요소들을 확인하면 아래와 같다. 

dq = [1, 0, 2, 4, 6, 8, None, 7, 5, 3]

 

 

 

 

 

 

 

 

2. 두 번째 dq.display()에 대한 결과는

[f=8,r=2] ==>  [3, 1, 0, 2]

 

print(dq)로 dq의 리스트 요소들을 확인하면 아래와 같다. 

dq = [1, 0, 2, 4, 6, 8, None, 7, 5, 3]

직접 만들었어요..

 

 

 

 

 

 

 

 

3. 세 번째 dq.display()에 대한 결과는

[f=3,r=2] ==>  [13, 12, 11, 10, 9, 3, 1, 0, 2]

 

print(dq)로 dq의 리스트 요소들을 확인하면 아래와 같다. 

dq = [1, 0, 2, 4, 13, 12, 11, 10, 9, 3]

 

display()에선 출력되지 않을 뿐 dq 리스트에는 

전단삭제와 후단삭제로 덱에서 삭제된 값들이 그대로 있다.