데크(Deque, Double-ended queue)는 앞, 뒤 모두에서 원소의 삽입과 삭제가 가능한 큐입니다. 스택과 큐를 합친 자료구조라고 생각하면 되겠습니다. 입력을 한 쪽 끝으로만 제한한 스크롤(Scroll)과 출력을 한 쪽 끝으로만 제한한 셸프(Shelf)도 있으나, 이 글에서는 기본적인 구조의 데크만 구현해보도록 하겠습니다.
또한, 전에 작성했던 스택과 큐 - Python 3의 Queue
클래스를 상속하여 데크를 구현해보도록 하겠습니다.
True
를 반환함. 아닐 경우, False
를 반환함.N
삽입.N
삽입.# Deque (Double-ended queue)
class Deque(Queue):
# Previous Push() and Pop() can't be used on deque.
def Push(self, N):
raise AttributeError("'Deque' object has no attribute 'Push'")
def Pop(self):
raise AttributeError("'Deque' object has no attribute 'Push'")
def Insert_Front(self, N):
self.Arr.insert(0, N)
def Insert_Rear(self, N):
self.Arr.append(N)
def Delete_Front(self):
return self.Arr.pop(0) if self.IsEmpty() == 0 else None
def Delete_Rear(self):
return self.Arr.pop() if self.IsEmpty() == 0 else None
# Front(), Back(), IsEmpty(), Size() are inherited and will be used continuously.
Python 3에서의 상속은 간단합니다. 자식 클래스를 선언할 때, 부모 클래스를 인자로 넣어주면 됩니다. 예시를 확인해보세요:
class parant:
def func_a:
# func_a
def func_b:
# func_b
class child(parant):
# child
상속받은 자녀 클래스는 다음의 특성을 갖습니다:
child
클래스에 func_a
를 정의한 내용이 없어도 child.func_a()
는 잘 실행됩니다.Queue
에는 IsEmpty()
, Size()
, Push(N)
, Pop()
, Front()
, Rear()
의 6가지 메소드가 있었습니다. Deque
는 Queue
를 상속받으므로 Queue
에 정의된 메소드를 사용할 수 있습니다. 다만, Push()
와 Pop()
은 예외입니다.
Deque
는 앞, 뒤에서 삽입, 삭제가 동시에 일어납니다. 앞에서만 삭제하고 뒤에서만 삽입하는 Queue
의 Pop()
과 Push(N)
은 Deque
에 적용할 수 없습니다. 따라서 이 두 메소드를 Deque
에서 사용할 수 없게 메소드 오버라이딩 처리를 해 주어야 합니다. 다시 말해서 Deque
에서의 Pop()
과 Push()
를 다시 정의해야 하겠습니다.
Deque
는 이미 Pop()
과 Push()
를 상속받았으므로 이를 삭제하는 건 불가능합니다. 따라서 적절한 대안으로, 이 두 함수를 실행했을 때 프로그램이 중단되도록 처리해 보겠습니다.
raise
명령어는 의도적으로 예외를 발생시킵니다. 사용 방법은 다음과 같습니다:
raise (예외 종류)[오류 메시지]
이를 Pop()
과 Push()
에 적용해 보죠. 발생하는 예외의 종류는 AttributeError
가 적절하겠습니다. AttributeError
는 속성(Attribute)의 이름이 잘못되었거나 존재하지 않을 경우 발생합니다. Deque
에는 Pop()
과 Push()
가 사실상 없는 것과 마찬가지니 AttributeError
의 발생 조건과 부합하네요.
class Deque(Queue):
def Pop(self):
raise AttributeError("'Deque' object has no attribute 'Pop'")
def Push(self, N):
raise AttributeError("'Deque' object has no attribute 'Push'")
위와 같이 코딩한 후, Deque
클래스를 호출해 Pop()
또는 Push()
를 실행하면 다음과 같이 예외가 발생합니다:
Traceback (most recent call last):
File "Queue.py", line 63, in <module>
deque.Pop()
File "Queue.py", line 31, in Pop
raise AttributeError("'Deque' object has no attribute 'Push'")
AttributeError: 'Deque' object has no attribute 'Push'