Queue - C와 Python 비교 - 2

지난 원형큐 설명에 이어 deque(덱 큐)에 대해 설명하겠다.

덱 큐는 원형큐에 비해 매우 파워풀하다. 원형큐는 front가 삭제 rear가 삽입으로 정해져 있었다면 그에 비해 덱큐는 front와 rear가 모두 삭제와 삽입이 자유롭다는 것이다. 사실 이는 덱이라고 불리지만 원형큐로 구현하면 시간복잡도가 O(1) 이기 때문에 효율적이다. 그래서 덱큐라고 명칭한다.

덱큐와 원형큐가 다른 점은 앞서 말했듯이 front와 rear가 모두 삭제가 가능하다는 것이다. 이를 구현하기 위해선 원형큐에선 시계방향의 회전만 했다면 덱큐는 반시계방향 회전을 한다. 이로 인해 delete_rear와 add_front가 구현될 수 있다. 

덱큐는 원형큐를 상속하여 구현해보겠다. 일단 python코드이다.

# 덱큐 -> 원형큐를 상속시켜서 구현
class CircularDeque(CircleQueue):
    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]

원형큐를 상속했기 때문에 그 전 글에 있던 circlequeue 클래스를 보고 오면 된다.

2020/07/13 - [자료구조] - Queue - C와 Python 비교

Queue - C와 Python 비교

덱큐를 C로 구현해보겠다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}DequeType;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}


void init_deque(DequeType* q) {
	q->front = q->rear = 0;
}

int is_empty(DequeType* q) {
	return (q->front == q->rear);
}

int is_full(DequeType* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
void deque_print(DequeType* q) {
	printf("DEQUE(front = %d rear = %d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % (MAX_QUEUE_SIZE);
			printf("%d | ", q->data[i]);
			if (i == q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}
void add_rear(DequeType* q, element item) { // enqueue
	if (is_full(q))
		error("큐가 포화상태입니다.");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;

}
element delete_front(DequeType* q) { // dequeue
	if (is_empty(q))
		error("큐가 공백입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}
element get_front(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백입니다");
	return q->data[(q->front)] % MAX_QUEUE_SIZE;
	
}
void add_front(DequeType* q, element val) {
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->data[q->front] = val;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
element delete_rear(DequeType* q) {
	int prev = q->rear;
	if (is_empty(q))
		error("큐가 공백입니다");
	q->rear = (q->rear -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}
element get_rear(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백입니다");
	return q->data[q->rear];
}

C에선 상속개념이 없기 때문에 원형큐 코드와 합쳐서 구현하였다.

이제 덱큐에 대한 자세한 설명을 하겠다. 사실 원형큐와 거의 비슷해서 설명할 것이 크게 없다고 생각하지만 새로운 코드가 있기 때문에 설명하겠다. 새로운 기능인 addFront에 대해 설명하겠다. 만약 꽉 차있지 않으면 큐의 front 자리에 아이템을 집어 넣고 front를 하나 빼준다. 즉 반시계 방향으로 회전하는 것이다. 그리고 front가 0보다 작아지면 안되므로 작아질 때는 MAX_QSIZE에서 하나 빼 준 값을 front로 재정의해준다.

deleteRear도 addFront와 같은 맥락이므로 설명 생략하겠다.

마지막으로 getRear인데 rear자리에 있는 것을 반환하는 코드이다.

이렇게 구현한 덱큐를 테스트해보는 메인 부분을 작성해보겠다.

int main(void) {
	DequeType queue;

	init_deque(&queue);
	
	for (int i = 0; i < 3; i++) {
		add_front(&queue, i);
		deque_print(&queue);
	}
	for (int i = 0; i < 3; i++) {
		delete_rear(&queue);
		deque_print(&queue);
	}
	return 0;
}

C는 하나씩 front로 넣고 다시 하나씩 후단에서 빼는 코드이다. 

다음으로 python이다.

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()

처음 구현한 것은 짝수는 뒤로 삽입하고 홀수는 앞으로 삽입 하는 것이다.

그리고 두번째로 처음 0번째,1번째 인덱스를 삭제하고 다음으로 뒤에서 0번째,1번째,2번째를 삭제하는 것이다.

마지막 세번쩨는 앞으로 9~13까지의 값을 삽입하는 것이다. 이의 결과는 다음과 같다.