문과생이 이해한 원형큐

▲출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

 

#include<stdio.h>
#include<stdlib.h>
#define MAX 5

typedef struct {
	int front;
	int rear;
	int data[MAX];
}QueueType;

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

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

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

void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		fprintf(stderr, "큐 포화상태");
		return;
	}
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear]=item;
}

void dequeue(QueueType* q) {
	if (is_empty(q)) {
		fprintf(stderr, "큐 공백상태");
		return;
	}
	q->front = (q->front + 1) % MAX;
	q->data[q->front];
}

void print(QueueType* q) {
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1);
			printf("%d ", q->data[i]);
		} while (i != q->rear);
	}
	printf("\n");
}

int main() {
	QueueType q;

	init(&q);

	enqueue(&q, 10); print(&q);
	enqueue(&q, 20); print(&q);
	enqueue(&q, 30); print(&q);

	dequeue(&q); print(&q);
	dequeue(&q); print(&q);
	dequeue(&q); print(&q);

	return 0;
}

 

 선형큐의 문제점을 해결하기 위해 나타난 원형 큐. 요것도 print 이상하게 되길래 print만 좀 수정함.

 

 

#main()

 

 일단 58번 줄의 초기화까지 마치면 메모리....!!!

 

 요로코롬 있다. 참고로 이번에 MAX는 5라서 인덱스가 4까지 있당. 

 

 선형큐와 다르게 0번부터 시작하는 이유는, 메모리 상에는 선형큐와 마찬가지로 저렇게 배열 형태로 저장될 건데. 추상적으로 우리는  

 

 

 큐를 이렇게 쓸 거라서 그렇다. (사진 출처 : 강의 자료 쌔벼옴) 그리고 이렇게 인덱스를 -1부터가 아니라 0부터 시작하기 때문에 공백과 포화 상태를 구별하기 위해 한 칸은 항상 비워둔다. 

 

 

#enqueue

 

 일단 enqueue 함수 인자로 q의 주소값과 큐에 넣을 데이터를 보낸다. 

 

 

 

 

 일단 큐가 비었는지 안 비었는지 확인해야겠쥬? is_full을 보면 선형큐와 확연히 다른 연산을 하고 잇는 것을 알 수 있다. 왜냐면 선형큐는 이미 쓴 칸을 다시 쓰지 않기 때문에 MAX-1 사이즈만큼만 쓸 수 있다. 근데 원형큐는 이미 쓴 칸을 또 쓸 수 있음ㅇㅇ. 이게 뭔 말이냐면. 

 

 

 

 큐가 현재 이렇게 포화 상태라고 해보자. 이 상태에서 enqueue 'E'를 할꺼다. 현재 rear는 4이고. 

 

 

 이 엔큐 연산을 하면. rear=1이 된다. 이렇게 이미 쓴 자리를 다시 쓸 수 있다는 거. 선형큐에서는 어림도 없는 연산인거쥬. 

 

 

 

 

 다시 is_full로 돌아와서 

 

 이게 포화 상태인데, 공백상태와 포화상태를 구별하기 위해 한 칸을 안 쓰기 때문에 +1을 하게 된다. 현재 front=0, rear=4. 17번 연산을 해보면 이게 왜 포화상태인지 알게 될 거다. 

 

 

 아무튼 현재 front와 rear는 0으로 저 연산을 하면 rear=1, front는 0이 나오므로 false를 리턴하게 된다. 

 

 

 31번 연산을 하면 rear=1이 되고, 큐가 가리키는 data배열의 1번 인덱스에 item값을 넣어주면 된다. 

 

 요로케!!!

 

 

#dequeue

 

일단 엔큐를 마치고 난 후의 메모리 상태다. 

 

 큐가 공백상태인지 아닌지는 선형큐와 똑같이 front와 rear가 같은 곳을 가리키면 된다. 지금 front는 0, rear는 3에 있으니까 false를 리턴함. 

 

front도 rear와 똑같은 연산을 해주면 됨. 

 

 요러케. 근데 데큐를 한다고 해서 [1]의 10이 사라지는 건 아니다. 그냥 print할 때 안 할 뿐.. 

 

 

#print

 

 선형큐에서는 엔큐할 때랑 데큐할 때 print문을 나눳는데 여기선 하나로 합침.. 생각해보면 선형큐에서도 이렇게 print()짜면 될 것 같기도 하고..

 

  일단 이 상태에서 print문 돌린다 치자. 변수 i를 front값인 1로 초기화 시키고 바로 do-while문으로 들어간다. 그리고 i++하면 하면서 i가 rear 즉 3이 아닐때까지 반복한다. 이때 i가 3이 되도 do-while문이니까 일단 실행하고 반복문이 끝나게 된다. 

 

<수정한 print>

 

 어디선가 주워들은 말로 do-while문은 잘 안쓴다카서 while로 바꿔 봄. 

 

#include<stdio.h>
#include<stdlib.h>
#define MAX 5

typedef struct {
	int front;
	int rear;
	int data[MAX];
}QueueType;

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

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

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

void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		fprintf(stderr, "큐 포화상태");
		return;
	}
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear]=item;
}

void dequeue(QueueType* q) {
	if (is_empty(q)) {
		fprintf(stderr, "큐 공백상태");
		return;
	}
	q->front = (q->front + 1) % MAX;
	q->data[q->front];
}

void print(QueueType* q) {
	if (!is_empty(q)) {
		int i = q->front;
		while (i != q->rear) {
			i++;
			printf("%d ", q->data[i]);
		} 
	}
	printf("\n");
}

int main() {
	QueueType q;

	init(&q);

	enqueue(&q, 10); print(&q);
	enqueue(&q, 20); print(&q);
	enqueue(&q, 30); print(&q);

	dequeue(&q); print(&q);
	dequeue(&q); print(&q);
	dequeue(&q); print(&q);

	return 0;
}