1. 큐 알아보기
큐(Queue)
- 데이터를 일시적으로 쌓아 놓은 자료구조
- 선입선출(FIFO :First in First out)
: 가장 먼저 넣은 데이터를 가장 먼저 꺼냄
- 인큐(en-queue)
: 큐에 데이터를 넣는 작업
- 디큐(de-queue)
: 데이터를 꺼내는 작업
- 프런트(front)
: 데이터를 꺼내는 쪽
- 리어(rear)
: 데이터를 넣는 쪽
2. 배열로 큐 만들기
ex) 배열의 프런트(front)부터 4개(19,22,37,53)의 데이터가 들어 있는 상태
-배열 이름 que
-que[0]~que[3]까지의 데이터가 저장
1) 24 인큐
- 리어(rear)의 데이터가 저장된 que[3]의 다음 요소 que[4]에 24 저장
- 복잡도 O(1)
2) 19 디큐
- que[0]에 저장된 19를 꺼낸 다음 두 번째 이후의 요소를 모두 맨앞으로 옮김
- 디큐를 하면서 두 번째 이후의 모든 요소를 하나씩 앞쪽으로 옮겨야 (shift)함
- 복잡도 O(n)
3. 링 버퍼로 큐 만들기
링 버퍼(ring buffer)
- 배열의 처음이 끝과 연결되었다고 보는 자료구조
프런트(front)
- 논리적인 맨 처음 요소의 인덱스
리어(rear)
- 논리적인 맨 끝 요소의 하나 뒤에 인덱스 (다음 요소를 인큐할 위치를 미리 지정)
- 변수 프런트와 리어의 값은 인큐와 디큐를 수행함에 따라 변화
- 프런트와 리어의 값을 업데이트하며 인큐와 디큐 수행
ex)
1) 7개의 데이터 (35,56,24,68,95,73,19)가 차례대로 que[7],que[8],..,que[11],que[0],que[1]에 저장
프런트값은 7, 리어 값 2
2) 82 인큐
- que[2] (리어가 가리키고 있는 위치)에 82를 저장한 다음 리어 값을 1증가
3) 35를 디큐
- 프런트 요소(que[7])의 값 35를 빼고 프런트값을 1증가
3.1 큐 구조체 IntQueue
- 큐를 관리하는 구조체
//큐를 구현하는 구조체
typedef struct {
int max; //큐의 최대 용량
int num; //현재의 요소 개수
int front; //프런트
int rear; //리어
int *que; //큐의 맨 앞 요소에 대한 포인터
}IntQueue;1) 큐로 사용할 배열(que)
- 인큐하는 데이터를 저장하기 위한 큐
- 사용할 배열의 첫 번째 요소에 대한 포인터
2) 큐의 최대 용량 (max)
- 큐의 최대 용량을 저장하는 int형 멤버
- 배열 que에 저장할 수 있는 최대 요소의 개수
3) 프런트 (front)
- 인큐하는 데이터 가운데 첫 번째 요소의 인덱스를 저장하는 멤버
4) 리어(rear)
- 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤에 인덱스를 저장하는 멤버
- 다음 인큐시에 데이터가 저장될 요소의 인덱스를 미리 준비함
5) 현재 데이터 개수(num)
- 큐에 쌓아 놓은 데이터 수
- num =0 -> 큐가 비어 있음
- num=max -> 큐가 가득 차 있음
3.2 초기화 함수 Initialize
- 큐를 구현하기 위한 배열 생성 등의 준비 작업을 하는 함수
- 큐를 처음 만들면 큐는 비어 있으므로 num,rear,front값을 모두 0으로 초기화
- 매개변수 max로 받은 "큐의 최대 용량"을 멤버 max에 저장
- 저장할 수 있는 요소의 개수가 max인 배열 que의 메모리 공간을 확보
//큐 초기화
int Initialize(IntQueue *q, int max)
{
q->num=q->front=q->rear=0;
if((q->que=(int*)calloc(max,sizeof(int)))==NULL) {
q->max=0; //배열 생성에 실패
return -1;
}
q->max=max;
return 0;
}
3.3 인큐 함수 Enque
- 큐에 데이터를 인큐하는 함수
//큐에 데이터를 인큐
int Enque(IntQueue *q,int x)
{
if(q->num>=q->max)
return -1; //큐가 가득 참
else {
q->num++;
q->que[q->rear++]=x;
if(q->rear == q->max)
q->rear=0;
return 0;
}
}- num 값 1증가, 인큐할 데이터 x를 que[rear]에 저장
- rear값 1증가
- rear값을 1만큼 증가했을 때 큐의 최대 용량의 값인 max와 같아지면 rear값을 배열의 처음 인덱스인 0으로 변경해야함
(인덱스 초과 문제)
3.4 디큐 함수 Deque
- 큐에서 데이터를 디큐하는 함수
//큐에 데이터를 디큐
int Deque(IntQueue *q, int *x)
{
if(q->num<=0)
return -1; //큐는 비어있음
else {
q->num--;
*x = q->que[q->front++];
if(q->front==q->max)
q->front=0;
return 0;
}
}- num값 1감소, que[front]에 저장한 값 x를 꺼냄
- front값 1증가
- 1만큼 증가한 front값이 큐의 최대 용량의 값인 max와 같아지면 front값을 배열의 처음 인덱스인 0으로 변경해야함
(인덱스 초과 문제)
3.5 피크 함수 Peek
- 맨 앞의 데이터(디큐에서 꺼낼 데이터)를 '몰래 엿보는'함수
//큐에서 데이터를 피크
int Peek(const IntQueue *q, int *x)
{
if(q->num<=0) //큐는 비어있음
return -1;
*x=q->que[q->front];
return 0;
}
3.6 모든 데이터를 삭제하는 함수 Clear
- 현재 큐의 모든 데이터를 삭제하는 함수
//모든 데이터 삭제
void Clear(IntQueue *q)
{
q->num=q->front=q->rear=0;
}
3.7 최대 용량을 확인하는 함수 Capacity
- 큐의 최대 용량을 반환하는 함수
- 멤버 max값을 그대로 반환
//큐의 최대 용량
int Capacity(const IntQueue *q)
{
return q->max;
}
3.8 데이터의 개수를 확인하는 함수 Size
- 현재 큐의 데이터 개수 반환
- 멤버 num값을 그대로 반환
//큐에 쌓여있는 데이터 개수
int Size(const IntQueue *q)
{
return q->num;
}
3.9 큐가 비어있는지 판단하는 함수 IsEmtpy
- 큐가 비어있는지 판단
- 비어 있으면 1, 그렇지 않으면 0
//큐가 비어있나요?
int IsEmpty(const IntQueue *q)
{
return q->num<=0;
}
3.10 큐가 가득찼는지 판단하는 함수 IsFull
- 큐가 가득 찼는지 판단
- 가득 찼으면 1, 그렇지 않으면 0
//큐가 가득 찼나요?
int IsFull(const IntQueue *q)
{
return q->num>=q->max;
}
3.11 검색함수 Search
- 큐의 배열에서 x와 같은 데이터가 저장되어 있는 인덱스 반환
- 검색 성공시 찾은 요소의 인덱스 반환
- 검색 실패시 -1 반환
- 검색의 시작 지점은 큐의 논리적인 첫 요소
- 현재 검색하는 위치의 인덱스
(i+q->front)%q->max
//큐에서 검 색
int Search(const IntQueue *q, int x)
{
for(int i=0; i<q->num; i++)
{
int idx;
if(q->que[idx=(i+q->front)%q->max]==x)
return idx;
}
return -1;
}
3.12 모든 데이터를 출력하는 함수 Print
- 큐의 모든 데이터를 처음부터 끝까지 순서대로 출력
//모든 데이터 출력
void Print(const IntQueue *q)
{
for(int i=0; i<q->num; i++)
printf("%d",q->que[(i+q->front)%q->max]);
putchar('\n');
}3.13 종료함수 Terminate
- 메모리 공간에 할당한 배열(큐) 해제
//큐의 종료
void Terminate(IntQueue *q)
{
if(q->que!= NULL)
free(q->que); //메모리 공간에 할당한 배열 해제
q->max=q->num=q->front=q->rear=0;
}
4. 큐를 사용하는 프로그램
#include <stdio.h>
#include <stdlib.h>
//큐를 구현하는 구조체
typedef struct {
int max; //큐의 최대 용량
int num; //현재의 요소 개수
int front; //프런트
int rear; //리어
int *que; //큐의 맨 앞 요소에 대한 포인터
}IntQueue;
//큐 초기화
int Initialize(IntQueue *q, int max)
{
q->num=q->front=q->rear=0;
if((q->que=(int*)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)
return -1; //큐가 가득 참
else {
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--;
*x = q->que[q->front++];
if(q->front==q->max)
q->front=0;
return 0;
}
}
//큐에서 데이터를 피크
int Peek(const IntQueue *q, int *x)
{
if(q->num<=0) //큐는 비어있음
return -1;
*x=q->que[q->front];
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;
}
//큐에서 검 색
int Search(const IntQueue *q, int x)
{
for(int i=0; i<q->num; i++)
{
int idx;
if(q->que[idx=(i+q->front)%q->max]==x)
return idx;
}
return -1;
}
//모든 데이터 출력
void Print(const IntQueue *q)
{
for(int i=0; i<q->num; i++)
printf("%d",q->que[(i+q->front)%q->max]);
putchar('\n');
}
//큐의 종료
void Terminate(IntQueue *q)
{
if(q->que!= NULL)
free(q->que); //메모리 공간에 할당한 배열 해제
q->max=q->num=q->front=q->rear=0;
}
int main()
{
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)출력 (0)종료:");
scanf("%d",&m);
if(m==0) break;
switch(m) {
case 1:
printf("데이터:"); scanf("%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);
break;
}
}
Terminate(&que);
return 0;
}
'C언어 > 자료구조' 카테고리의 다른 글
| 5-2 재귀 알고리즘 분석 (0) | 2023.07.27 |
|---|---|
| 5-1 재귀의 기본 (0) | 2023.07.27 |
| 4-1 스택이란? (0) | 2023.07.26 |
| 함수 포인터 (0) | 2023.07.25 |
| 3-3장 이진 검색 (0) | 2023.07.25 |
