23 min to read
자료구조(6) - 큐, 환형 큐
큐와 환형 큐의 ADT를 만들고, 구현
🔚 짧게 하는 복습
✅ 1. 동적 배열로 스택과 주어진 ADT를 구현할 수 있다.
✅ 2. 스택의 활용을 안다.(읽어볼 거리 참고)
혹시 기억이 안 난다면, 다시 돌아가자
저번 수업에서는 LIFO가 특징이고 선형 자료구조인 스택에 대해 다루었다.
이번 시간에는 FIFO(First In First Out), 즉 먼저 들어온 원소가 먼저 나가는 선형 자료구조인 큐에 대해 다루어보겠다.
스택은 그냥 동적 배열만 구현하고 정적 배열을 과제로 남겼던 것과 달리, 이번에는 큐를 정적, 동적 배열까지 다 구현해볼 생각이다.
그리고 저번 과제 중 하나였던, 선형 자료구조를 정적 배열로 구현했을 때와 동적 배열의 구현했을 때에 구현 차이에 대해 알아보겠다.
스택에서는 top이라는 인덱스 하나가 굉장히 중요한 역할을 했는데, 큐는 두 인덱스가 필요하다.
아래 그림을 잘 보자.
하나는 rear로 스택의 top처럼 가장 나중에 들어온 원소, 하나는 front로 가장 먼저 들어온 원소를 가리키고 있어야 한다.
insert가 되면 rear 뒤에 원소가 추가되고, pop이 되면 front를 반환한다.
또한, 참조와 수정 요청이 들어오면 front가 가리키고 있는 원소가 참조 혹은 수정되어야 한다.
큐 역시도, 스택처럼 가장 먼저 들어온 원소 말고는 관심이 없다는 점이다.
그렇기에 큐의 ADT를 만들 때도 순회 기능이 없다.
큐 ADT
역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정이 가능하다.
정적 배열을 통한 큐의 ADT 구현
우선은 정적 배열을 통해, 최대 크기를 정해놓고 구현해보겠다.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10 //전처리를 통한 배열 최대 크기 설정
/*
자료 : 정수
기능1 삽입 : 원소를 큐에 입력한다.
기능2 수정 : 가장 먼저 입력된 원소의 값을 수정한다.
기능3 삭제 : 가장 먼저 입력된 원소를 큐에서 제거한다.
기능4 조회 : 가장 먼저 입력된 원소의 값을 조회한다.
*/
//+ empty한지 확인
int is_empty(const int rear, const int front) {
if (rear < front) {
return 1; //비었으면 참
}
else {
return 0;//아니면 거짓
}
}
int is_full(const int rear) {
if (rear == MAX -1) {
return 1; // 가득 찼으면 참
}
else {
return 0; // 아니면 거짓
}
}
//기능1 삽입
int insert(int* arr, const int value, int* rear) {
if (is_full(*rear)) {
printf("Queue is already full!\n\n");
return -1;
}//큐가 다 찼으면 오류 리턴
arr[++*rear] = value;
//rear 증가시키고 값 대입
printf("%d is sucessfully inserted in queue\n\n", value);
return 0;
}
//기능2 수정
int update(int* queue, const int value, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
queue[front] = value;
printf("Queue's top value is changed with %d\n\n", value);
return 0;
}
//기능3 제거
int pop(int* queue, const int rear, int* front) {
if (is_empty(rear, *front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
return queue[(*front)++];
//반환하고 front 증가, pop한 원소 리턴
}
//기능4 조회
int find_front(int* queue, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
return queue[front];// pop한 원소 리턴
}
int main(void) {
int queue[MAX] = { 0, };
// 정적 배열을 통한 큐 구현
int rear = -1;
// 참조를 편하게 하기위해 보통 -1을 디폴트 값으로 정한다.
int front = 0;
// 역시, 참조를 편하게 하기위해 보통 0을 디폴트 값으로 정한다.
insert(queue, 1, &rear);
insert(queue, 2, &rear);
insert(queue, 3, &rear);
printf("front : %d\n\n", find_front(queue, rear, front)); // 1 출력
update(queue, 4, rear, front); // front 4로 수정
printf("front : %d\n\n", find_front(queue, rear, front)); // 4 출력
for(int i= 0; i<4; i++){
printf("pop : %d\n\n", pop(queue, rear, &front)); // 4, 2, 3 출력 후 -1 에러코드
}
for (int i = 0; i <8; i++) {
insert(queue, i, &rear);
// 순서대로 입력되다 마지막에 full -1 에러코드
}
}
front, rear 두 개의 인덱스를 사용하고 처음에 -1, 0으로 설정하는 것만 알면 쉽다.
결과창
1 is sucessfully inserted in queue
2 is sucessfully inserted in queue
3 is sucessfully inserted in queue
front : 1
Queue's top value is changed with 4
front : 4
pop : 4
pop : 2
pop : 3
Queue is empty!
pop : -1
0 is sucessfully inserted in queue
1 is sucessfully inserted in queue
2 is sucessfully inserted in queue
3 is sucessfully inserted in queue
4 is sucessfully inserted in queue
5 is sucessfully inserted in queue
6 is sucessfully inserted in queue
Queue is already full!
정적 배열로 구현한 큐의 한계
정적 배열로 구현하면 장점은 구현이 쉽다. 그냥 배열 위에서 인덱스만 움직이면 된다.
단점은 불필요한 메모리 낭비가 많다. 많은 원소를 넣자고 MAX를 크게 잡자니, 대부분은 메모리가 사용되지 않고 빈다.
또한, insert와 pop이라는 구조 때문에 더 메모리가 불필요하게 많이 필요해진다.
예를 들면 100000개를 insert하고 100000를 pop하면, 이론상 100000만큼의 메모리만 필요하다.
하지만 큐의 구조상 200000개의 메모리가 모두 필요하다.
이를 동적 배열로 해결해보자.
동적 배열을 통한 큐의 ADT 구현
#include <stdio.h>
#include <stdlib.h>
typedef int* Queue;
/*
자료 : 정수
기능1 삽입 : 원소를 큐에 입력한다.
기능2 수정 : 가장 먼저 입력된 원소의 값을 수정한다.
기능3 삭제 : 가장 먼저 입력된 원소를 큐에서 제거한다.
기능4 조회 : 가장 먼저 입력된 원소의 값을 조회한다.
*/
//+ empty한지 확인
int is_empty(const int rear, const int front) {
if (rear <= front) {
return 1; //비었으면 참
}
else {
return 0;//아니면 거짓
}
}
//기능1 삽입
int insert(Queue* queue, const int value, int* rear) {
if (*queue == NULL) {
*queue = (Queue)malloc(sizeof(int));
}
else {
Queue newarr = (Queue)realloc(*queue, sizeof(int)*(*rear+1));
*queue = newarr;
}
*((*queue)+(*rear)) = value;
*rear += 1;
//값 대입시키고 증가
printf("%d is sucessfully inserted in queue\n\n", value);
return 0;
}
//기능2 수정
int update(Queue queue, const int value, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
queue[front] = value;
printf("Queue's top value is changed with %d\n\n", value);
return 0;
}
//기능3 제거
int pop(Queue* queue, int* rear, int* front) {
if (is_empty(*rear, *front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
int ret = *(*queue+(*front));
(*front)+=1; // front 증가
int size = *rear - *front;
if (size == 0) { //원소가 없으면
*queue = NULL; // Null로 돌리고
*rear = 0;
*front = 0;
//인덱스도 처음으로 초기화
}
else{ // 원소가 있다면
for (int i = *front - 1; i < *rear; i++) {
*(*queue + i - *front) = *(*queue + i);
}// 빈 공간 만큼 당겨서 앞에 공백을 지움
*rear -= *front;
*front -= *front;
// 인덱스를 당긴만큼 수정함.
Queue newarr = (Queue)realloc(*queue, sizeof(int) * size);
*queue = newarr;
//뒤에 남은 공간은 재할당으로 날려버림
}
return ret; //반환하고 front 증가, pop한 원소 리턴
}
//기능4 조회
int find_front(int* queue, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
return queue[front];// pop한 원소 리턴
}
int main(void) {
Queue queue = NULL; // 동적 배열을 통한 큐 구현
int rear = 0; // 동적할당을 편하게 하기위해 0로 했다.
int front = 0; // 인덱싱을 편하게 하기위해 0로 했다.
insert(&queue, 1, &rear);
insert(&queue, 2, &rear);
insert(&queue, 3, &rear);
printf("front : %d\n\n", find_front(queue, rear, front));
// 1 출력
update(queue, 4, rear, front); // front 4로 수정
printf("front : %d\n\n", find_front(queue, rear, front));
// 4 출력
for (int i = 0; i < 4; i++) {
printf("pop : %d\n\n", pop(&queue, &rear, &front));
}
// 4, 2, 3 출력 후 -1 에러코드
for (int i = 0; i < 8; i++) {
insert(&queue, i, &rear); // 순서대로 입력되다 마지막에 full -1 에러코드
}
}
이번엔 front, rear를 0, 0으로 설정했다.
구현에는 정답이 없다. 본인이 가장 편하게 다룰 수 있는 인덱스를 설정하는 것이 좋다.
필자는 rear는 insert에서 동적할당이 필요해서 디폴트를 0, front는 인덱싱이 직관적으로 디폴트를 0으로 했다.
이 코드에서는 pop이 상당히 어렵다.
그림으로 그리면
코드와 함께 잘 이해해보자.
-
먼저 리턴할 원소를 저장해놓고, front를 증가한다.
-
pop하게 되면 빈 곳이 생기는데, 그만큼 원소들을 당겨준다.
-
남은 공간은 재할당으로 제거한다.
결과창
1 is sucessfully inserted in queue
2 is sucessfully inserted in queue
3 is sucessfully inserted in queue
front : 1
Queue's top value is changed with 4
front : 4
pop : 4
pop : 2
pop : 3
Queue is empty!
pop : -1
0 is sucessfully inserted in queue
1 is sucessfully inserted in queue
2 is sucessfully inserted in queue
3 is sucessfully inserted in queue
4 is sucessfully inserted in queue
5 is sucessfully inserted in queue
6 is sucessfully inserted in queue
7 is sucessfully inserted in queue
동적 할당으로 만든 큐의 장단점.
동적 할당으로 만든 큐는 정적 할당보다 메모리 낭비가 훨씬 적다.
원소의 수만큼만 있으면 되기 때문이다.
하지만 여기서 다른 문제가 생기는데, 코드 실행에 시간이 굉장히 오래 걸린다는 점이다.
할당/ 재할당도 시간이 오래 걸리는 함수인 데다, pop은 모든 원소를 앞으로 당겨야 하므로 원소수가 많으면 많을수록 코드 실행시간이 길어진다.
또한, 무엇보다 구현이 어렵고 복잡하기도 하다.
그렇다면 이를 해결할 방법이 없을까?
환형 큐란?
여기서 정적 배열의 장점인 인덱스만 조정, 구현 쉬움과 동적 배열의 장점인 메모리 절약을 동시에 가진 큐를 만들어낸다.
바로 환형 큐인데, 영어로는 Circular queue, 즉 원형 모양의 큐이다.
(스택은 정적으로 만들어도 큐에 비하면 거의 메모리 낭비가 없었기 때문에, 더 최적화된 스택의 요구가 적었다.)
이는 우선 아래 그림을 보고 이해하는 것이 좋다. (enqueue는 insert, dequeue는 pop이라고 생각하면 된다.)
전체적으로 비슷한데 원형으로 만들었기 때문에, pop된 공간을 다시 사용하는 모습임을 알 수 있다.
환형 큐와 그냥 큐의 차이는 rear나 front가 한 바퀴(정적 배열의 최대 크기)를 넘어갔을 때 인덱스가 다시 처음으로 오냐, 아니냐의 차이이다.
예를 들어, 배열의 최대 크기가 rear 인덱스가 9이고, rear가 10이 될 때 그냥 큐는 종료된다.
반면에 환형 큐는 rear가 10이 될 때, 만약 배열의 첫 번째 공간이 비었다면 rear는 10이 아니라, 10을 빼고 다시 0이 되어서 인덱스를 넘어가지 않는 것이다.
즉 인덱스가 최대 크기를 넘어갈 때, 최대 크기를 빼서 처리한다.
그런데 이게 최대 크기를 넘어가는지 안 넘어가는지 확인할 필요도 없는 방법이 있다.
바로 modular 연산인데, 이를 매 인덱스 증가 시마다 붙이면 훨씬 쉽게 코드를 짤 수 있다.
환형 큐 구현
우선 인덱스 다루는 점이 꽤 어려운데,
-
우선 front, rear의 디폴트 값을 -1로 시작한다.
-
front가 -1일 때 입력되면, rear도 증가시키고 front도 0으로 만든다.
-
front든 rear이든 최대 사이즈를 넘어가면 다시 0으로 초기화시킨다.(modular 연산을 이용하자)
-
pop을 했는데 원소가 없다면 (front == rear), 다시 처음처럼 front, rear을 -1로 초기화시킨다.
-
full의 조건은 ((rear+1) == front) || (front == 0 && rear == size-1), 즉 무슨 말이냐 하면 그냥 정적 배열로 생각했을 때
서로 이웃한 칸이거나, 첫 칸과 마지막 칸인 경우이다. (직접 원형 큐가 가득 찬 경우를 정적 배열로 펼쳐서 그려보자)
직접 구현해보자.
#include <stdio.h>
#include <stdlib.h>
#define MAX 6 //전처리를 통한 배열 최대 크기 설정
/*
자료 : 정수
기능1 삽입 : 원소를 큐에 입력한다.
기능2 수정 : 가장 먼저 입력된 원소의 값을 수정한다.
기능3 삭제 : 가장 먼저 입력된 원소를 큐에서 제거한다.
기능4 조회 : 가장 먼저 입력된 원소의 값을 조회한다.
*/
//+ empty한지 확인
int is_empty(const int rear, const int front) {
if (front == -1) {
return 1; //비었으면 참
}
else {
return 0;//아니면 거짓
}
}
int is_full(const int rear, const int front) {
if (rear + 1 == front || (front == 0 && rear == MAX - 1)) {
return 1; // 가득 찼으면 참
}
else {
return 0; // 아니면 거짓
}
}
//기능1 삽입
int insert(int* arr, const int value, int* rear, int* front) {
if (is_full(*rear, *front)) {
printf("Queue is already full!\n\n");
return -1;
}//큐가 다 찼으면 오류 리턴
if (*front == -1) {
*front = 0;
}
*rear = (*rear + 1) % MAX;
arr[*rear] = value;
//modular 연산을 이용하여 rear 증가시키고 값 대입
printf("%d is sucessfully inserted in queue\n\n", value);
return 0;
}
//기능2 수정
int update(int* queue, const int value, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
queue[front] = value;
printf("Queue's top value is changed with %d\n\n", value);
return 0;
}
//기능3 제거
int pop(int* queue, int* rear, int* front) {
if (is_empty(*rear, *front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
int ret = queue[(*front)];
*front = (*front +1)%MAX;
if (*front == *rear) {
*front = -1;
*rear = -1;
}
return ret; //반환하고 front 증가, pop한 원소 리턴
}
//기능4 조회
int find_front(int* queue, const int rear, const int front) {
if (is_empty(rear, front)) {
printf("Queue is empty!\n\n");
return -1;
}//원소가 없으면 오류
return queue[front];// pop한 원소 리턴
}
int main(void) {
int queue[MAX] = { 0, }; // 정적 배열을 통한 큐 구현
int rear = -1;
// 참조를 편하게 하기위해 보통 -1을 디폴트 값으로 정한다.
int front = -1;
// 역시, 참조를 편하게 하기위해 보통 0을 디폴트 값으로 정한다.
insert(queue, 15, &rear, &front);
insert(queue, 20, &rear, &front);
insert(queue, 25, &rear, &front);
insert(queue, 30, &rear, &front);
insert(queue, 35, &rear, &front);
printf("front : %d\n\n", find_front(queue, rear, front)); // 35 출력
update(queue, 40, rear, front); // front 40로 수정
printf("front : %d\n\n", find_front(queue, rear, front)); // 40 출력
for (int i = 0; i < 2; i++) {
printf("pop : %d\n\n", pop(queue, &rear, &front)); // 40, 20 출력
}
insert(queue, 40, &rear, &front);
insert(queue, 45, &rear, &front);
insert(queue, 50, &rear, &front);
insert(queue, 55, &rear, &front); // full 오류
for (int i = 0; i < 7; i++) {
printf("pop : %d\n\n", pop(queue, &rear, &front));
}
// 25, 30, 35, 40, 45, 50, 55, 오류 출력
}
조건이 까다로운 것에 비해, 구현은 굉장히 쉽다.
거의 달라지는 것도 없고, 인덱싱도 직관적이다.
또한, 메모리 낭비도 정적 배열보다 확실히 줄어든 것을 알 수 있다.
결과창
15 is sucessfully inserted in queue
20 is sucessfully inserted in queue
25 is sucessfully inserted in queue
30 is sucessfully inserted in queue
35 is sucessfully inserted in queue
front : 15
Queue's top value is changed with 40
front : 40
pop : 40
pop : 20
40 is sucessfully inserted in queue
45 is sucessfully inserted in queue
50 is sucessfully inserted in queue
Queue is already full!
pop : 25
pop : 30
pop : 35
pop : 40
pop : 45
Queue is empty!
pop : -1
Queue is empty!
pop : -1
📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)
✅ 1. 정적 배열로 큐와 주어진 ADT를 구현할 수 있다.
✅ 2. 동적 배열로 큐와 주어진 ADT를 구현할 수 있다.
✅ 3. 정적 배열로 환형 큐와 주어진 ADT를 구현할 수 있다.
⚠️ 구현은 한 가지 방법이 정해진 것이 아니다. 인덱스를 다루는 법을 외우기보다는, 왜 이렇게 하기가 가장 쉬운지를 생각해보자.
💣 과제,
-
환형 큐를 모듈러가 아니라 뺄셈으로 구현해보자. (난이도 中)
-
deque라는 자료구조가 있다.(읽어볼 거리1 참고), 이의 push_back, push_front, pop_back, pop_front, find_back, find_front를 정적 배열로 구현해보자(난이도 中)
-
deque와 위의 ADT를 동적 배열로도 구현해보자(난이도 上)
🔜 더 공부해보기,
Comments