[C] 큐 : 선형큐, 원형큐, 덱

방가방가 안녕들 하신가요.

 

오늘은 큐에 대해 복습을 하려고 합니다.

 

큐란?

선입선출 (FIFO: first in first out) 구조로,

먼저 들어온 데이터가 먼저 나가는 자료구조를 의미한다.

쉽게 말하면 선착순이다.

 

추상 자료형의로 정의하면..

create(max_size) >> 최대 크기가 max_size인 비어있는 큐 생성

init(q) >> 큐 초기화

is_empty(q) >> 큐의 사이즈가 0이면  return true, 아니면 return false

is_full(q) >> 큐의 사이즈가 max_size와 같으면 return true, 아니면 return false

enqueue(q,e) >> is_full 검사를 하고 자리가 있다면 q의 끝에 e를 추가

dequeue(q) >> is_empty 검사를 하고 데이터가 있다면 맨 앞 데이터를 제거하여 반환

 

이 정도만 구현하면 된다..

 

---

 

선형 큐에 대해 이야기 하자면,

우선 변수 front와 rear을 만든다.

최종적으로 front는 큐의 첫 번째 데이터의 하나 앞을 가리키고

rear은 큐의 마지막 데이터를 가리킨다.

 

인덱스를 -1, 0, 1, 2, 3 ... 순서대로 되어있다고 치면

인덱스 0부터 데이터가 들어가고

데이터가 아무것도 없으면 -1을 가리킨다.

 

그러므로 front와 rear은 데이터가 아무것도 없으면 -1을 가리킨다.

데이터를  추가하면 front는 그대로, rear만 +1을 해주면 되고

데이터를 삭제하면, front를 +1하고 rear은 그대로 두면 된다.

 

그럼 구현을 해보자..

선형 큐

#include<stdio.h>
//exit 사용하려고 include 했다
//exit를 쓰면 아예 프로그램이 멈춰버린다
//return과 차이점 >> return은 호출한 곳, 즉 main으로 가게 된다.
#include<stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element; //큐에 들어갈 데이터의 자료형을(이번에는 int) element로 대신 명명
typedef struct {
	//front와 rear은 데이터와 상관없이 인덱스 값이므로 int로 설정
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
}QueueType;

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

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

//큐에 있는 데이터 차례로 출력하는 함수
//front는 데이터의 하나 앞을 가리키니 i=q->front+1
//rear은 마지막 데이터를 가리키니 q->rear까지 i++
void queue_print(QueueType* q) {
	for (int i = q->front + 1; i < q->rear; i++)
		printf("%d->", q->data[i]);
	printf("%d", q->data[q->rear]);
	printf("\n");
}

int is_full(QueueType* q) {
	//rear은 인덱스 값이니 (0부터 시작), Max Size -1이면 꽉찬 것
	if (q->rear == MAX_QUEUE_SIZE - 1)
		return 1;
	else return 0;
}

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

void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		error("Queue is full.");
		return;
	}
	//마지막 요소를 가리키는 인덱스 rear을 +1 시키고
	//큐의 rear번째 인덱스에 item 삽입
	q->data[++(q->rear)] = item;
}

element dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("Queue is empty.");
		return -1;
	}
	//front를 먼저 증가시키고 dequeue한 item을 return
	return q->data[++(q->front)];
}

int main() {
	element item = 0;
	QueueType q;
	init_queue(&q);
	char select="";

	while (select != 'q') {
		printf("-------------------------------\n");
		printf("데이터를 enqueue하려면 e를\n");
		printf("데이터를 dequeue하려면 d를\n");
		printf("프로그램을 종료하려면 q를 입력하세요.\n");
		printf("-------------------------------\n");
		scanf(" %c", &select);
		if (select == 'e') {
			printf("enqueue할 데이터를 입력하세요: ");
			scanf(" %d", &item);
			enqueue(&q, item);
			queue_print(&q);
		}
		else if (select == 'd') {
			item = dequeue(&q);
			printf("데이터를 dequeue했습니다.\n dequeue한 데이터는 %d 였습니다.\n", item);
			queue_print(&q);
		}
		else if (select == 'q') printf("queue 프로그램을 종료합니다.\n");
		else printf("잘못 입력하셨습니다.\n");
	}
}

짜잔

 

테스트를 해봤다

-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
e
enqueue할 데이터를 입력하세요: 5
5
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
e
enqueue할 데이터를 입력하세요: 10
5->10
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
e
enqueue할 데이터를 입력하세요: 15
5->10->15
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
d
데이터를 dequeue했습니다.
 dequeue한 데이터는 5 였습니다.
10->15
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
d
데이터를 dequeue했습니다.
 dequeue한 데이터는 10 였습니다.
15
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
a
잘못 입력하셨습니다.
-------------------------------
데이터를 enqueue하려면 e를
데이터를 dequeue하려면 d를
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
q
queue 프로그램을 종료합니다.

결과창은 이렇게 나온다

차례대로

e 5

e 10

e 15

d

d

a

q 를 입력한 것이다..

 

---

 

그 다음은 원형 큐이다

원형 큐는 왜 쓰냐면

선형 큐를 쓰면 dequeue할 때마다 자꾸 front가 뒤로 넘어가서 메모리 낭비가 너무 심함

(배열로 치면 0, 1, 2, 3 ...인덱스에 이렇게 데이터 넣어놓고

dequeue하면서 0 인덱스의 데이터 빼내고, 1 인덱스의 데이터 빼내고 이런느낌...

그러면 평생 0번, 1번 인덱스에는 아무것도 안들어가면서 메모리 낭비..)

 

그래서 원형 형태로 만들어서 메모리를 효율적으로 써보자.. 이런 취지이다.

선형 큐에서 dequeue할 때마다 데이터를 앞으로 이동시키는 것 보다

원형 큐를 쓰는게 훨씬 효율적이라고 한다.

효율 is 중요..

 

선형 큐와 마찬가지로 front는 첫 번째 데이터 하나 앞을, rear은 마지막 요소를 가리킨다.

도저히 말로는 설명하기 어려우니 사진 첨부를 ...

원형 큐

위의 사진은 원형큐가 포화상태일 때다.

front는 첫 번째 데이터의 앞을 가리켜야하므로

공간 하나는 비어있는 채로 유지된다.

front ==  rear 일 경우는 큐가 비어있을 때 뿐이다.

공간 하나를 포기하더라도 원형 큐를 쓰는 게 효율적이다!

 

구현을 해보자

원형 큐

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

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
}QueueType;

//큐 초기화 함수
//큐가 비어있을 때는 front와 rear이 같고 0번 인덱스를 가리킨다.
void init_queue(QueueType* q) {
	q->front = q->rear = 0;
}

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

//마지막 데이터를 rear이 가리키고
//그 다음에 비어있는 공간이 있고
//빈 공간을 front가 가리킨다
//따라서 (rear+1)%max_size == front면 포화상태
//max_size 5일때 0 1 2 3 4 이렇게 돌아야 하므로 % max_size 한것임
int is_full(QueueType* q) {
	if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) return 1;
	else return 0;
}

//front == rear은 큐가 비어있을 때만 성립
int is_empty(QueueType* q) {
	if (q->front == q->rear) return 1;
	else return 0;
}

void enqueue(QueueType* q, element item) {
	//overflow check
	if (is_full(q)) {
		error("queue overflow");
		return;
	}
	// 0 1 2 3 4 0 1 2.... 일정 인덱스 반복해야함
	//q->rear = q->rear + 1 라고 하면 0 1 2 3 4 5 6 ... 이 되어버림
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;

}

element dequeue(QueueType* q) {
	//underflow check
	if (is_empty(q)) {
		error("queue underflow\n");
		return -1;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

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

int main() {
	QueueType q;
	init_queue(&q);

	enqueue(&q, 10);
	//q.rear =1 , q.front =0 이 됨

	enqueue(&q, 20);
	enqueue(&q, 30);
	enqueue(&q, 40);
	//max_size는 5 이지만
	//front를 위해 남겨둔 하나의 빈공간 때문에
	//실제로 데이터는 4개만 들어감
	print_queue(&q);

	dequeue(&q);
	dequeue(&q);
	print_queue(&q);
}

결과창은 다음과 같다

 10 20 30 40
 30 40

 

---

 

덱

덱은 대체 무엇이냐.. 하면

deque, double-ended queue의 줄임말이다.

front와 rear에서 모두 삽입 삭제가 가능하다!

완전 스택이랑 큐랑 섞어둔 것이다.

 

덱은 원형 큐를 조금만 수정하면 만들 수 있다.

대신 함수가 나머진 비슷한데 삽입 삭제를 ...

 

add_front(dq,e) >> 덱의 앞에 데이터 추가

add_rear(dq,e) >> 덱의 뒤에 데이터 추가

delete_front(dq) >> 덱의 맨 앞 반환하고 삭제

delete_rear(dq) >> 덱의 맨 뒤 반환하고 삭제

 

이렇게 쓰도록 하겠다.

 

구현을 해보자..

원형 큐랑 다른 부분 위에 주석 쓰도록 하겠다...

덱

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

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
}DequeType;

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

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

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

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

//=enqueue
void add_rear(DequeType* q, element item) {
	if (is_full(q)) {
		error("deque is full.");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

//=dequeue
element delete_front(DequeType* q) {
	if (is_empty(q)) {
		error("deque is empty.\n");
		return -1;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

//새로 추가된 함수 (1/2)
//맨 앞 데이터 삽입하기
void add_front(DequeType* q, element item) {
	if (is_full(q)) error("deque is full.\n");
	q->data[q->front] = item;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	//front가 0을 가리키고 있었다면
	//data[0]에 데이터를 삽입하고
	//인덱스 4번으로 front 이동 (4 0 1 2 3 4 0 .....)
}

//새로 추가된 함수 (2/2)
//맨 뒤 데이터 삭제하기
//rear을 변경시키면 return 하기 곤란하므로 temp에 원래 rear값 저장
element delete_rear(DequeType* q) {
	int temp = q->rear;
	if(is_empty(q)) error("deque is empty.\n");
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return temp;
}

//deque의 front, rear, 데이터 값 출력
void deque_print(DequeType* q) {
	int i;
	printf("deque front=%d rear=%d\n", q->front, q->rear);
	if (!is_empty(q)) {
		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");
}

int main() {
	DequeType q;
	init_deque(&q);
	element item = 0;
	char select = "";

	while (select != 'q') {
		printf("-------------------------------\n");
		printf("데이터를 앞에 삽입하려면 a를\n");
		printf("데이터를 뒤에 삽입하려면 b를\n");
		printf("맨 앞 데이터를 삭제하려면 c를\n");
		printf("맨 뒤 데이터를 삭제하려면 d\n");
		printf("프로그램을 종료하려면 q를 입력하세요.\n");
		printf("-------------------------------\n");
		scanf(" %c", &select);
		if (select == 'a') {
			printf("삽입할 데이터를 입력하세요: ");
			scanf(" %d", &item);
			add_front(&q, item);
			deque_print(&q);
		}
		else if (select == 'b') {
			printf("삽입할 데이터를 입력하세요: ");
			scanf(" %d", &item);
			add_rear(&q, item);
			deque_print(&q);
		}
		else if (select == 'c') {
			item = delete_front(&q);
			printf("데이터를 삭제했습니다.\n삭제한 데이터는 %d 였습니다.\n", item);
			deque_print(&q);
		}
		else if (select == 'd') {
			item = delete_rear(&q);
			printf("데이터를 삭제했습니다.\n삭제한 데이터는 %d 였습니다.\n", item);
			deque_print(&q);
		}
		else if (select == 'q') printf("deque 프로그램을 종료합니다.\n");
		else printf("잘못 입력하셨습니다.\n");
	}
}

 

휘유,

결과창은 다음과 같다.

 

a 1

b 2

b 3

c

d

e

q를 입력해봤다.

 

-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
a
삽입할 데이터를 입력하세요: 1
deque front=4 rear=0
1->
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
b
삽입할 데이터를 입력하세요: 2
deque front=4 rear=1
1->2->
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
b
삽입할 데이터를 입력하세요: 3
deque front=4 rear=2
1->2->3->
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
c
데이터를 삭제했습니다.
삭제한 데이터는 1 였습니다.
deque front=0 rear=2
2->3->
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
d
데이터를 삭제했습니다.
삭제한 데이터는 2 였습니다.
deque front=0 rear=1
2->
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
e
잘못 입력하셨습니다.
-------------------------------
데이터를 앞에 삽입하려면 a를
데이터를 뒤에 삽입하려면 b를
맨 앞 데이터를 삭제하려면 c를
맨 뒤 데이터를 삭제하려면 d
프로그램을 종료하려면 q를 입력하세요.
-------------------------------
q
deque 프로그램을 종료합니다.

 

 

데이터 삽입과 삭제..

나중에는 연결리스트로 데이터 삽입과 삭제를 하는데...

(미래의 나에게 미리 응원을..)

 

.

.

그나저나

분량 조절 실패한듯...

노트북이 뜨거와요

 

하지만 어쩔 수 없었다..

선형 큐 원형 큐랑 덱을 나눠서 포스팅하긴 애매해서...

다음번에는 큐와 덱의 응용 문제를 풀어보고자한다.

 

7월도 벌써 중순인데 눈 깜빡하면 2022년 일 것 같다.

뭐 어찌됐든 가는 시간을 최대한 잘 쓰는게

평생의 숙제이니까..

 

...파이팅!

 

참고자료는 저의 영혼의 교재 "C언어로 쉽게 풀어쓴 자료구조" (생능출판, 천인국 공용해 하상호 지음) 입니다.