문과생이 이해한 선형큐

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

 

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

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

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

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

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

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

void dequeue(QueueType* q) {
	if (is_empty(q)) {
		fprintf(stderr, "큐가 공백상태입니다. ");
		return -1;
	}
	q->data[++(q->front)];
}

void print_e(QueueType* q) {
	for(int i = 0; i <= q->rear; i++) 
		printf("%d ", q->data[i]);
	printf("\n");
}

void print_d(QueueType* q) {
	for (int i = q->front; i <= q->rear; i++)
		printf("%d ", q->data[i]);
	printf("\n");
}

int main() {
	QueueType q;

	init(&q);

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

	printf("________________________\n\n");

	dequeue(&q); print_d(&q);
	dequeue(&q); print_d(&q);
	dequeue(&q); print_d(&q);

	return 0;
}

 

 교과서에 나온 코드는 뭔가 짜증나게 생겨서 보기쉽게 수정 좀 햇다. 사실 처음에 자료구조 독학했을 때 큐를 지금 코드의 구조체인 front, rear, data[MAX]를 전부 전역변수로 설정했다. 근데 내가 C를 야매로 공부해서 구조체랑 포인터 개념을 잘 모름. 그래서 구조체 버릴까 말까 고민 엄청하다가 연결리스트랑 스택은 구조체 썼는데 큐에서 못쓰는 거 보고. 내가 아직도 많이 부족하구나.. 현타와서 그냥 구조체 써서 코드를 짰다.

 

 

#main문

 정말 tmi지만 우리 학과에서 강조하는 건 초등학생들한테 설명해도 이해할 수 있을 정도로 쉽게 설명할 줄 알아야 한다는 거. 당신들은 이제부터 초등학생

 

 일단 구조체 변수 q를 선언하고 62번 초기화 함수를 통해 구조체를 초기화한다. 

 

#삽입- enqueue

 

enqueue를 할 때 인자값으로 구조체 변수 q의 주소값과 삽입할 data를 보내준다. 

 

 여기서 좀 헤맨게 왜 enqueue를 할 때는 q의 주솟값을 보내줬으면서 is_full() 검사를 할 땐 그냥 q를 보내주지??????????????????????????????????????????????????????? 

 

 결론은 이거였다. 

 

 구조체 변수의 주소값 10번지를 enqueue의 인자로 보내고, 함수가 그거를 포인터로 받았으니까 현재 메모리 상태는 저런 상태인거다...!!! 그러니까 is_full할 때 q를 보내주는 건 10'를 보내준거. 

 

 

  어쨋든 큐에 넣기 전에 일단 q가 다 찻으면 못 넣으니까 큐가 다 찼는지 어떤지 검사하자. 

 

 

 ~~~~~~~~~~여기서 잠깐~~~~~~~~~~~

▲ 일단 이게 크기가 4인 큐를 초기화 한 상태이다. (비어있는 상태)

 

 이렇게 front와 rear가 같은 인덱스를 가리키고 잇으면 큐는 비어있는 상태이다. 그도 그럴 것이 큐는 선입선출(먼저 들어간 것이 먼저 나옴)로 rear가 데이터를 채워 나가면(enqueue) front는 가만히 있다가 출력할 때 front를 움직여 출력하기(dequeue) 때문에. 그런 둘이 같은 인덱스를 가리키고 있따? 그럼 큐는 비어있는 상태인 것이다. 

 

 비단 초기화한 상태일 때 뿐이 아니라 [0]이든 [1]이든 front와 rear가 같은 인덱스를 가리키면 큐는 텅텅 빈 거임. 

 

 

▲ 이게 크기가 4인 큐가 다 찬 모습. 

 

 앞서 말했듯 입력할 땐 rear를 쓰고 출력할 땐 front를 쓰는데. rear가 MAX(=4)-1의 자리까지 갔다면 큐는 다 찬 상태가 된다. 이때 front의 위치는 어디든 상관없다. 이게 바로 선형큐의 문제점인데, 

 

 

 이렇게 앞의 인덱스가 비어있어도 rear가 갈 곳이 없어서 남은 빈칸들을 못 쓴다는거다. 그래서 선형큐는 잘 안 쓰인다고 함.

 

 

아무튼 본론으로 넘어와서 현재 MAX가 100고, rear는 -1이니까 is_full 함수는 false를 리턴한다. 여기서 MAX-1을 해주는 이유는 인덱스가 0번부터 시작하기 때문이라는 건 알겠쥬?

 

 

 그리고 대망의 enqueue! q->data는 현재 구조체 변수 q에 있는 data 배열에 item을 삽입할 거다. 

 

  여기서 또 헷갈렸던 건 포인터... *p++이랑 (*p)++이랑 헷갈렷었다. 

 

 뭐 요로코롬 있으면 *p++은 현자 [0]을 가리키고 있는 포인터는 [1] 인덱스를 가리킨다. (*p)++는 현재 포인터가 가리키고 있는 10을 ++한다는 의미. 일단 괄호가 우선순위가 높으므로 값을 가져오고 그 값을 후위 연산한다는 의미이고. 괄호가 없을 때는 ++의 우선순위가 높으므로 일단 ++부터한 다음 포인터로 가리킨다는 의미인듯!

 

 

 

 사설이 길엇는데 이제 enqueue한 것을 print할 시간이다! 낄낄

 

 책에서는 대게 복잡하게 짯길래 내가 못 알아먹겠어서 새로 짜버렸다ㅜ 일단 q의 주소값을 넘겨주고, data배열의 0번부터 현재 rear가 있는 곳까지 반복한다. 

 

 일단 enqueue를 10, 20, 30까지 했다고 하면 현재 메모리는 다음과 같은 상태일 거다. 

 

 

 

 그럼 i가 0에서부터 rear(=2)까지 반복할 거다. 그래서 출력하면 다음과 같음. 

 

 

 

#dequeue

 

 

 dequeue를 하려면 일단 큐가 비었는지 안 비었는지 알아야 겠쥬? 큐가 비었는지 안 비었는지 확인하는 방법은 앞서 말했다 싶이 front와 rear가 같을 때임. 지금 front는 -1이고 rear는 2니까 비어있지 않음!

 

 

 맨날 bool값 쓰다가 int형 쓸라니까 헷갈려서 주석으로 0은 false라고 써놈...

 

 

 enqueue랑 비슷하쥬? 이렇게 front를 움직이면서 출력하면 data에 들은 값을 선입선출 형식으로 출력할 수 잇다. 

 

 

 요것도 enqueue랑 비슷한데 틀린거라곤 for문의 초기문과 조건문? 엔큐처럼 i=0부터 시작하면 의미없으니까 q->front부터 시작한다. 그래서 출력하면!!!

 

 

 

---

 

 선형 큐 대게 쉽다고 생각햇는데 막상 짜려니까 대게 헷갈리는 거 보고 많이 부족하다는 걸 알아부림.. 특히 구조체랑 포인터 이해 못해서 영구실 칭구한테 자꾸 꼬치꼬치 캐물음ㅜ 더 열심히 노력해야 겠다는 생각.