개요
데크(Deque, Double-ended queue)는 앞, 뒤 모두에서 원소의 삽입과 삭제가 가능한 큐입니다. 스택과 큐를 합친 자료구조라고 생각하면 되겠습니다. 입력을 한 쪽 끝으로만 제한한 스크롤(Scroll)과 출력을 한 쪽 끝으로만 제한한 셸프(Shelf)도 있으나, 이 글에서는 기본적인 구조의 데크만 구현해보도록 하겠습니다.
또한, 전에 작성했던 스택과 큐 - Python 3의 Queue 클래스를 상속하여 데크를 구현해보도록 하겠습니다.
추상 자료형
구조
- 데크 (Deque, Double-ended queue)
- Arr : 큐에 저장될 데이터의 배열.
기능
- IsEmpty() : 데크가 비어있을 경우,
True를 반환함. 아닐 경우,False를 반환함. - Size() : 데크에 저장된 원소의 개수 반환.
- Front() : 데크의 맨 앞에 위치한 원소의 값 반환.
- Rear() : 데크의 맨 끝에 위치한 원소의 값 반환.
- Insert_Front(N) : 데크의 맨 앞에 새로운 원소
N삽입. - Insert_Rear(N) : 데크의 맨 뒤에 새로운 원소
N삽입. - Delete_Front() : 데크의 맨 앞에 위치한 원소 삭제.
- Delete_Rear() : 데크의 맨 뒤에 위치한 원소 삭제.
구현
# 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에서의 상속
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'
