파이썬으로 구현하는 덱(Deque)

덱(Deque)이란?

double-ended queue로, 큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다. 덱은 원형 큐(Circular Queue)를 확장하면 손쉽게 구현할 수 있다.

 

원형 큐 구현에 관해서는 해당 게시글을 참고하시면 좋습니다

https://codingsmu.tistory.com/123

파이썬으로 구현하는 원형 큐(Circular Queue)

 

 

0. 멤버 변수&초기화

먼저 덱 클래스의 멤버 변수(member variable)와 초기화 과정을 보자

class Deque:

    rear = 0
    front = 0
    MAX_SIZE = 100
    deq = list()
    
    def __init__(self):
    	self.rear = 0
        self.front = 0
        self.deq = [0 for i in range(self.MAXSIZE)]

추가로, 현재 덱의 front/rear 값을 반환하는 함수도 편의를 위해 같이 구현하도록 하자

def get_front(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return -1
    front = (self.front+1) % MAX_SIZE
    return self.deq[front]
    
    
def get_rear(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return -1
    return self.deq[self.rear]

 

1. 공백 상태

덱이 비워져 있는 경우 rear == front 이다

def is_empty(self):
	if self.rear == self.front:
    	return True
    return False

 

 

2. 포화 상태

앞에서, 공백 상태를 front == rear로 구분하기 때문에 포화상태의 경우 위의 사진처럼 한 칸이 비어있다.

따라서 배열에 한 칸을 비움으로써 공백 상태와 포화 상태를 구분하기로 한다

def is_full(self):
	if (self.rear+1)%self.MAX_SIZE == self.front:
    	return True
    return False

 

 

 

3. 데이터 삽입

3-1. 뒤(rear)에서 삽입

덱에 A B C D를 순서대로 후단에 삽입했을 때 동작 과정

rear에서 삽입이 이루어지므로, front는 값의 변경이 없고 rear += 1을 하며 데이터를 삽입한다

def add_rear(self, x):
	if is_full():
    	print("ERROR: FULL")
        return
    self.rear = (self.rear+1)%(self.MAX_SIZE)
    self.queue[self.rear] = x

 

3-2. 앞(front)에서 삽입

front 변수는 항상 공백을 가리켜야 하므로 앞에서 삽입이 이루어질 때, 한칸씩 차이를 두고 데이터를 삽입해야 한다

이 경우 front에서 삽입이 이루어지므로, rear는 값의 변경이 없고 front -= 1을 하며 데이터를 삽입한다

단, 여기서 주의해야 할 점은 3-1에서 처럼, self.front = (self.front - 1) % MAX_SIZE 연산을 하면 안된다는 점이다.

이 경우, front 변수가 0일 때, 위의 수식을 계산하면 -1이 나와 배열의 인덱스 범위를 벗어나게 된다

따라서, front 변수 업데이트 시  self.front = (self.front - 1 + MAX_SIZE) % MAX_SIZE를 해줘야 한다.

def add_front(self, x):
	if is_full():
    	print("ERROR: FULL")
        return
    self.deq[self.front] = x
    self.front = (self.front - 1 + MAX_SIZE) % MAX_SIZE

 

 

 

4. 데이터 삭제

4-1. 앞(front)에서 삭제

front에서 삭제가 일어날 경우, rear 값의 변경이 없고 front += 1을 하며 데이터를 삭제한다

def del_front(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return
    self.front = (self.front +1) % MAX_SIZE
    return self.queue[self.front]

 

4-2. 뒤(rear)에서 삭제

rear에서 삭제가 일어날 경우, front 값의 변경이 없고, rear -=1을 하며 데이터를 삭제한다

단, 여기서 주의해야 할 점은 4-1에서 처럼, self.rear = (self.rear - 1) % MAX_SIZE 연산을 하면 안된다는 점이다.

이 경우, rear 변수가 0일 때, 위의 수식을 계산하면 -1이 나와 배열의 인덱스 범위를 벗어나게 된다

따라서, rear 변수 업데이트 시  self.rear = (self.rear - 1 + MAX_SIZE) % MAX_SIZE를 해줘야 한다.

def del_rear(self):
	if is_empty():
    	print("ERROR: EMPTY")
        return
    tmp = self.deq[self.rear]
    self.rear = (self.rear - 1 + MAX_SIZE) % MAX_SIZE
    return tmp

 

 

 

Optional. (Print 함수)

추가로, 현재 큐에 저장된 요소를 출력해주는 함수는 아래와 같다

def deque_print(self):
	i = (self.front+1) % MAX_SIZE
    if is_empty():
    	print("ERROR: EMPTY")
        return
    while i != self.rear:
    	print(self.deq[i], ' ')
        i = (i+1) % MAX_SIZE
    print(self.deq[i])