Queue - C와 Python 비교

Queue는 대표적인 FIFO(First In First Out) 알고리즘이다. 즉 선입선출으로 먼저 들어온 값이 먼저 나가는 구조이다. LIFO구조인 stack과 비교된다. 구조상으로 스택과 다른 점은 삽입과 삭제 연산의 위치가 다르다는 것이다. 스택은 맨 위에부터 꺼내 쓰고 꺼내서 빼는 구조로 삽입과 삭제 연산의 위치가 같지만 Queue는 앞뒤에 문이 있다고 생각하면 된다. 따라서 앞의 문은 front, 뒤에 문은 rear 이다. 삽입이 일어나는 곳은 rear, 삭제가 일어나는 곳은 front 이다.

기본적으로 큐의 종류는 선형큐,원형큐,덱큐,우선순위 큐가 있다. 

이 중 가장 기본적으로 선형큐의 구현을 보여줘야하지만 선형큐는 다른 큐에 비해 비효율적인 면이 있다. 왜냐하면 삭제연산에서 리스트의 모든 항목들을 앞으로 땡겨야하므로 시간복잡도가 O(n)이 된다. O(n)은 언뜻보면 크게 안커보이지만 다른 큐들은 O(1)의 시간복잡도를 가지므로 상대적으로 비효율적이기 때문에 구현을 하지 않겠다.

따라서 시간복잡도의 효율성을 높이기 위해 리스트를 원형이라 생각하고 구현한다. 이 큐가 바로 원형큐이다. 

원형큐에서 rear는 가장 최근에 삽입된 항목의 위치를 front에는 가장 최근에 삭제된 항목의 위치를 저장한다. 처음 front = rear =0 으로 초기화시키고 삽입일 때는 rear+1 삭제일때는 front+1을 한다. 

원형큐의 삽입과 삭제과정

https://www.slideserve.com/whitby/chapter-3-stack-and-queue-2009-3-30 <- 그림 출처

이 때 주의할 것은 이 큐는 단순 리스트가 아니라 원형으로 생각한다는 점이다. 원형으로 생각하지 않고 점점 올려준다면 선형큐와 다를 것이 없다. 원형으로 생각하기 위해서 MAX_QSIZE로 나눠줘야한다. 그리고 그 나눠준 값의 나머지를 반환한다. 그러면 한바퀴 돌면 0이 된다. 따라서 (front+1) % MAX_QSIZE , (rear+1) % MAX_QSIZE 가 된다.

지금부터 원형큐를 구현해보겠다. 처음은 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;
}QueueType;

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

void init_queue(QueueType*q) {
	q->front = q->rear = 0;
}

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

int is_full(QueueType* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void queue_print(QueueType* q) {
	printf("QUEUE(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 enqueue(QueueType* q, element item) {
	if (is_full(q))
		error("큐가 포화상태입니다.");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;

}

element dequeue(QueueType* q) {
	if (is_empty(q))
		error("큐가 공백입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

다음은 파이썬이다.

MAX_QSIZE = 10 # 원형큐 사이즈
class CircleQueue: # 원형으로 움직이는 큐
    def __init__(self):
        self.front=0
        self.rear=0
        self.items = [None]*MAX_QSIZE
    def isEmpty(self):
        return self.front == self.rear
    def isFull(self):
        return self.front == (self.rear+1) % MAX_QSIZE # f
    def clear(self):
        self.front = self.rear
    def enqueue(self,item): # 삽입함수
        if not self.isFull():
            self.rear = (self.rear+1)%MAX_QSIZE # rear 회전
            self.items[self.rear] = item # rear 위치에 삽입
    def dequeue(self): # 삭제
        if not self.isEmpty(): # front 회전
            self.front = (self.front+1) % MAX_QSIZE # front 위치의 항목 반환
            return self.items[self.front]
    def peek(self): # 삭제하지 않고 반환
        if not self.isEmpty():
            return self.items[(self.front+1)%MAX_QSIZE] 
    def size(self):
        return (self.rear - self.front + MAX_QSIZE) % MAX_QSIZE
    def display(self):
        out = []
        if self.front<self.rear:
            out = self.items[self.front+1:self.rear+1]
        else:
            out = self.items[self.front+1:MAX_QSIZE] + self.items[0:self.rear+1]
        print('f={},r={}'.format(self.front,self.rear),out)

 

C에서의 MAX 큐 사이즈는 5 python에서의 MAX  큐 사이즈는 10으로 설정했다. 

파이썬 코드로 원형큐에 대해 설명하겠다. 처음 init으로 front와 rear의 값을 초기화 시켜준다. 그리고 items라는 큐 크기가 한정되어 있는 리스트를 만든다.

먼저 Empty는 front와 rear의 위치가 같으면 Empty라고 인식한다.(rear = front = 0)

full은 하나의 자리를 비워두고 front가 rear보다 하나 앞에 있으면 포화상태라고 정의한다. 왜냐하면 공백상태와 구분이 안되기 때문이다.

다음으로 삽입 함수이다. 만약 가득차있지 않으면 rear를 하나 늘리고 그 위치에 item을 삽입하는 것이다. 삭제도 마찬가지 맥락이다. peek함수는 삭제하지 않고 그 값을 반환 하는 것이다. dequeue와 다른 점은 self.front를 재정의하지 않은 것이다.

이를 이용한 main함수를 통해 구현이 잘 되어 있는지 확인한다.

C로 구현한 원형큐 코드는 큐가 꽉 찰 때 까지 입력을 받고 꽉 차면 삭제하는 것을 구현하였다.

int main(void) {
	QueueType queue;
	int element;

	init_queue(&queue);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&queue)) {
		printf("정수를 입력하시오: ");
		scanf("%d", &element);
		enqueue(&queue, element);
		queue_print(&queue);

	}
	printf("큐는 포화상태입니다.\n");

	printf("--데이터 삭제 단계--\n");

	while (!is_empty(&queue)) {
		element = dequeue(&queue);
		printf("꺼내진 정수 : %d\n", element);
		queue_print(&queue);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

결과

파이썬은 단순 삽입 삭제를 보여주는 것으로 구현하였다.

q = CircleQueue()
for i in range(8):
    q.enqueue(i)
q.display()
for i in range(5):
    q.dequeue()
q.display()
for i in range(8,14):
    q.enqueue(i)
q.display()

결과

매우 잘 나왔다.

나중에서야 안건데 python에선 queue 모듈이 기본적으로 구현이 되어있다...사실 이런 코드를 직접짜지 않아도 파이썬은 이미 구현이 되어있는거다..

모듈의 예시를 들어보겠다..

import queue
Q = queue.Queue(maxsize=20)
for v in range(1,10):
    Q.put(v) # enqueue
print("큐의 내용:",end=' ')
for _ in range(1,10):
    print(Q.get(),end =' ')
print()

put으로 enqueue하고 get으로 받아온다. 매우 간단하다.

심지어 스택도 구현되어있다. 스택의 특징인 LIFO로 함수이름이 구현되어 있다.

S = queue.LifoQueue(maxsize=20) # stack

https://docs.python.org/3/library/queue.html

queue — A synchronized queue class — Python 3.8.4rc1 documentation

큐 모듈 자료이니 참고하면 된다.