[자료구조] queue(큐) (C)
참고 | DO IT C언어 자료구조 입문편
🤷♀️ 이번 시간에는 큐에 대해서 알아보겠다.
- 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조다.
- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조를 이루고 있다.
- 대표적인 예시로
- 은행 창구에서 차례를 기다리는 대기열
- 마트에서 계산을 기다리는 대기열
📢 배열을 이용해 큐를 구현해보자.
<그림 출처|https://juyeop.tistory.com/13>
위의 그림의 왼쪽은 실제 링 버퍼 큐에서 이루어지는 데이터 입 출력 과정을 표시한 것이다. 프런트의 값부터 순차적으로 데이터가 추가되는 모습을 볼 수 있다. 그림의 오른쪽은 링 버퍼 큐의 모양을 배열 큐 모습으로 변환시켜 놓은 것아다.
링 버퍼 큐는 배열 큐와 달리 데이터가 디큐가 된 후 인덱스 자리를 옮겨줘야 하는 등 불편한 점이 존재하지 않다. 지금까지 배열 큐와 링 버퍼 큐에 대해서 알아보았다. 이 둘은 각기 다른 것이 아닌 큐를 구현하는 모양의 차이다. 대부분의 사람들이 큐를 구현할 때는 배열 모양보다는 링 버퍼 모양으로 큐를 구현하는 것이 보편적이다.
큐를 헤더파일로 선언해보자.
#ifndef __IntQueue
#define __IntQueue
typedef struct {
int max; //큐의 최대 용량
int num; // 현재의 최대 개수
int front; // 프런트
int rear; // 리어
int* que; // 큐의 맨 앞 요소에 대한 포인터 스택에서 stk역할
}IntQueue;
int Initialize(IntQueue* q, int max);
int Enque(IntQueue* q, int x);
int Deque(IntQueue* q, int* x);
int Peek(IntQueue* q, int* x);
void clear(IntQueue* q);
int Capacity(const IntQueue* q);
int Size(const IntQueue* q);
int IsEmpty(const IntQueue* q);
int IsFull(const IntQueue* q);
int Search(const IntQueue* q, int x);
void Prinf(const IntQueue* q);
void Terminate(IntQueue* q);
#endifQueue Initialize 함수
int Initialize(IntQueue* q, int max) // 초기화 함수
//큐를 구현하기 위해 배열의 메모리 공간 확보 등의 준비 작업하는 함수.
//큐는 처음 만들면, 큐는 비어 있으므로 num, front, rear 값을 모두 0으로 한다.
{
q->num = q->front = q->rear = 0;
if ((q->que = calloc(max, sizeof(int))) == NULL)
{
q->max = 0;
return -1;
}
q->max = max;
return 0;
}
Queue Enque 함수
int Enque(IntQueue* q, int x) // 큐에 데이터를 인큐하는 함수다.
{
if (q->num >= q->max)//인큐에 성공하면 0을 반환하지만,
{//큐가 가득 차서 인큐할 수 없으면(num >= max) - 1을 반환한다.
return -1;
}
else
{
//que[rear]에 데이털 82를 인큐하고 rear와 num 값을 1만큼 증가하면, 인큐 작업이 끝난다.
//만약 인큐하기 전의 rear 값이 11이면 Enque 함수를 수행한 다음에는 rear값이 12가되면서 max와 같아지는 문제가 발생한다.
q->num++;
q->que[++q->rear] = x;
if (q->rear == q->max)
{
q->rear = 0;
}
return 0;
}
}
Queue Deque함수
int Deque(IntQueue* q, int* x)
{
if (q->num <= 0) // 큐가 비어 있으면
{
return -1;
}
else
{
q->num--; //num값을 감소시킨다.
*x = q->que[q->front++]; // 버퍼링을 통해서 Deque를 하게 되면 가장 먼저 앞에 있었던 front가 나가게 되고 front를 증가시킨다.
if (q->front == q->max)
q->front = 0;
return 0;
}
}Deque 및 Enque는 두 가지 관점이있다.
- front에서 Deque / Enque 할 경우 & 링 버퍼
- Back에서 Deque 및 Enque 할 경우 & 링 버퍼와 연결지어 생각해야한다. (인덱스 초과 문제가 발생하기 때문에)
- 인덱스 초과 문제를 해결하기 위한 아이디어로
큐의 front == 큐의 용량(max) 같아지면, front의 값을 배열의 처음인 0으로 변경한다. (rear도 동일하다.)
Queue Search
int Search(const IntQueue* q, int x) // Search의 근본적인 목적은 x와 같은 값이 있는지를 찾아보는 함수다.
{//검색의 시작 지점은 배열의 첫 요소가 아니라 큐의 첫 요소다.
int i, idx;
for (i = 0; i < q->num; i++)
{
if (q->que[idx = (i + q->front) % q->max] == x)
return idx;
}
return -1;
}
num = 7이고, max 가 11이라고 가정할 떄, que[7], que[8], que[9], que[10], que[11], que[0], que[1]에 값이 있다. que[7]이 front 쪽 que[1]이 rear - 1 이다.
(i+q->front) % q->max라고 한다면,
i : 0 > 1 > 2> 3 > 4 > 5 > 6
idx : 7 > 8 > 9 > 10 > 11 > 0 > 1 이다.
나머지 Queue 함수구현
int Peek(const IntQueue * q, int* x) // que[front] 함수만 확인한다.
{
if (q->num <= 0)
return -1;
*x = q->que[q->front]; //Peek 함수자체가 가장 꼭대기에 있는 것을(앞에 있는 것) 보여주기 때문에
return 0;
}
void Clear(IntQueue* q) //큐의 모든 데이터를 삭제하는 함수다.
{
q->num = q->front = q->rear = 0;
}
int Capacity(const IntQueue* q) //큐의 최대용량를 의미한다.
{
return q->max;
}
int Size(const IntQueue* q)
{
return q->num;
}
int IsEmpty(const IntQueue* q) // 큐가 비어있는지 확인하는 함수.
{
return q->num <= 0;
}
int IsFull(const IntQueue* q)
{
return q->num >= q->max;
}
void Printf(const IntQueue* q)
{
int i;
for (i = 0; i < q->num; i++)
{
printf("%d", q->que[(i + q->front) % q->max]);
}
putchar('\n');
}
void Terminata(IntQueue* q)
{
if (q->que != NULL)
{
free(q->que);
}
q->max = q->num = q->front = q->rear = 0;
}
앞에 Queue를 활용한 프로그램을 만들어보자.
IntQueue.c(main)
#include <stdio.h>
#include "IntQueue.h"
int main(void)
{
IntQueue que;
if(Initialize(&que, 64) == -1)
{
puts("큐의 생성에 실패했습니다.");
return -1;
}
while (1)
{
int m, x;
printf("현재 데이터 수 %d \ %d \n", Size(&que), Capacity(&que));
printf("(1)인큐 (2)디큐 (3)피크 (4)출력 (5)종료 :");
scanf_s("%d", &m);
if (m == 0)
{
break;
}
switch (m)
{
case 1:
printf("데이터 : "); scanf_s("%d", &x);
if (Enque(&que, x) == -1)
{
puts("\a오류 : 인큐에 실패했습니다.");
}
break;
case 2:
if (Deque(&que, &x) == -1)
puts("\a오류 : 디큐에 실패했습니다.");
else
printf("디큐한 데이터는 %d입니다.\n", x);
break;
case 3:
if (Peek(&que, &x) == -1)
{
puts("\a오류 : 피크에 실패했습니다.");
}
else
{
printf("피크한 데이터는 %d입니다.\n",x);
break;
}
case 4:
Print(&que);
}
}
Terminata(&que);
return 0;
}IntQueue.h
#ifndef __IntQueue
#define __IntQueue
typedef struct {
int max;
int num;
int front;
int rear;
int* que;
}IntQueue;
int Initialize(IntQueue* q, int max);
int Enque(IntQueue* q, int x);
int Deque(IntQueue* q, int* x);
int Peek(IntQueue* q, int* x);
void clear(IntQueue* q);
int Capacity(const IntQueue* q);
int Size(const IntQueue* q);
int IsEmpty(const IntQueue* q);
int IsFull(const IntQueue* q);
int Search(const IntQueue* q, int x);
void Prinf(const IntQueue* q);
void Terminata(IntQueue* q);
#endifqueue.c
#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"
//typedef struct {
// int max;
// int num;
// int front;
// int rear;
// int* que;
//}IntQueue;
int Initialize(IntQueue* q, int max) // 초기화 함수
//큐를 구현하기 위해 배열의 메모리 공간 확보 등의 준비 작업하는 함수.
//큐는 처음 만들면, 큐는 비어 있으므로 num, front, rear 값을 모두 0으로 한다.
{
q->num = q->front = q->rear = 0;
if ((q->que = calloc(max, sizeof(int))) == NULL)
{
q->max = 0;
return -1;
}
q->max = max;
return 0;
}
int Enque(IntQueue* q, int x) // 큐에 데이터를 인큐하는 함수다.
{
if (q->num >= q->max)//인큐에 성공하면 0을 반환하지만,
{//큐가 가득 차서 인큐할 수 없으면(num >= max) - 1을 반환한다.
return -1;
}
else
{
//que[rear]에 데이털 82를 인큐하고 rear와 num 값을 1만큼 증가하면, 인큐 작업이 끝난다.
//만약 인큐하기 전의 rear 값이 11이면 Enque 함수를 수행한 다음에는 rear값이 12가되면서 max와 같아지는 문제가 발생한다.
q->num++;
q->que[++q->rear] = x;
if (q->rear == q->max)
{
q->rear = 0;
}
return 0;
}
}
int Deque(IntQueue* q, int* x)
{
if (q->num <= 0) // 큐가 비어 있으면
{
return -1;
}
else
{
q->num--; //num값을 감소시킨다.
*x = q->que[q->front++]; // 버퍼링을 통해서 Deque를 하게 되면 가장 먼저 앞에 있었던 front가 나가게 되고 front를 증가시킨다.
if (q->front == q->max)
q->front = 0;
return 0;
}
}
int Peek(const IntQueue * q, int* x) // que[front] 함수만 확인한다.
{
if (q->num <= 0)
return -1;
*x = q->que[q->front]; //Peek 함수자체가 가장 꼭대기에 있는 것을(앞에 있는 것) 보여주기 때문에
return 0;
}
void Clear(IntQueue* q) //큐의 모든 데이터를 삭제하는 함수다.
{
q->num = q->front = q->rear = 0;
}
int Capacity(const IntQueue* q) //큐의 최대용량를 의미한다.
{
return q->max;
}
int Size(const IntQueue* q)
{
return q->num;
}
int IsEmpty(const IntQueue* q) // 큐가 비어있는지 확인하는 함수.
{
return q->num <= 0;
}
int IsFull(const IntQueue* q)
{
return q->num >= q->max;
}
void Print(const IntQueue* q)
{
int i;
for (i = 0; i < q->num; i++)
{
printf("%d", q->que[(i + q->front) % q->max]);
}
putchar('\n');
}
void Terminata(IntQueue* q)
{
if (q->que != NULL)
{
free(q->que);
}
q->max = q->num = q->front = q->rear = 0;
}
int Search(const IntQueue* q, int x) // Search의 근본적인 목적은 x와 같은 값이 있는지를 찾아보는 함수다.
{//검색의 시작 지점은 배열의 첫 요소가 아니라 큐의 첫 요소다.
int i, idx;
for (i = 0; i < q->num; i++)
{
if (q->que[idx = (i + q->front) % q->max] == x)
return idx;
}
return -1;
}<결과>
📢 링버퍼에 대하여
- 링버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.
- 대표적인 예로 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때, 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버린다.
- 다음 예제를 보자.
#include <stdio.h>
#define N 10
int main()
{
int i;
int a[N];
int cnt = 0;
int retry;
puts("정수를 입력하세요 ");
do
{
printf("&d번째 정수 :", cnt + 1);
scanf_s("%d", &a[cnt++ % N]);
printf("계속할까요 (Yes.. / No..) : ");
scanf_s("&d", &retry);
} while (retry == 1);
i = cnt - N;
if (i < 0) i = 0;
for (; i < cnt; i++)
{
printf("%2d번째 정수 = %d\n", i + 1, a[i % N]);
}
return 0;
}- 1,2,3,4,5,6,7,8,9,10,11를 입력하는 예제다.
- 배열에 남아있는 10개만 저장되고 처음에 입력한 1은 제외된다.
입력한 값을 저장하는 위치의 인덱스는 a[cnt++ % N]로 구현한다.
- 첫 번째 값을 입력했다.
- cnt 0 / 10으로 나눈 나머지는 0이다. 입력값은 a[0]에 저장된다.
- cnt 1 / 10으로 나눈 나머지는 1이다. 입력값은 a[1]에 저장된다.
.....
- cnt 10 / 10으로 나눈 나머지는 0이다. 입력값은 a[0]에 저장된다.
- cnt 11 / 10으로 나눈 나머지는 1이다. 입력값은 a[1]에 저장된다.
<결과>
※내용정리
- 큐에 대한 정의 및 예시
- 큐 & 링버퍼
- Queue 함수 구현 및 예시
- 링버퍼 예시
Author And Source
이 문제에 관하여([자료구조] queue(큐) (C)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qlwb7187/자료구조-queue큐-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
