큐 (QUEUE)
큐도 역시 스택과 마찬가지로 데이터를 일시적으로 쌓아놓은 자료구조이다.
•
FIFO (First In First Out)
이라는 점에서 스택과 다르다.
EX)
•
은행 창구에서 차례를 기다리는 대기열
•
마트 계산 대기열
•
인큐 (Enqueue)
◦
큐에 데이터를 넣는 작업
•
리어 (Rear)
◦
데이터를 넣는 쪽
•
디큐 (Dequeue)
◦
데이터를 큐에서 꺼내는 작업
•
프런트 (Front)
◦
데이터를 꺼내는 쪽
배열로 큐 만들기
스택과 마찬가지로 큐는 배열을 사용하여 구현할 수 있다.
큐 구현
typedef struct {
int max; // 큐의 용량
int num; // 현재 데이터 수
int *que; // 큐의 첫 요소에 대한 포인터
} ArrayIntQueue;
C
복사
링 버퍼로 큐 만들기
•
배열 요소를 앞쪽으로 옮기지 않는 큐 → 링 버퍼 (Ring Buffer)
•
배열의 처음과 끝이 연결되어있다
•
첫번째와 마지마가 요소를 식별하기 위해 front와 rear 변수로 구분한다
Front : 맨 처음 요소의 인덱스
Rear : 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정)
→ 이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 앞에서 발생한 요소 이동문제를 해결할 수 있다
→ 물론 처리의 복잡도는 O(1) 이다
링 버퍼로 큐를 구현
#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(const 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 Print(const IntQueue *q);
// 큐 종료
void Terminate(IntQueue *q);
#endif
C
복사
큐 구조체
•
5개의 멤버로 구성된다
1.
큐로 사용할 배열 (que)
•
인큐하는 데이터를 저장하기 위한 큐로, 사용할 배열의 첫 번째 요소에 대한 포인터이다
2.
큐의 최대 용량 (max)
•
큐의 최대 용량을 저장하는 멤버로, 이 값은 배열 que에 저장할 수 있는 최대 요소의 개수와 같다
3.
Front
•
인큐하는 데이터 가운데 첫 번재 요소의 인덱스를 저장하는 멤버이다
4.
Rear
•
인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 멤버이다
5.
Num
•
큐에 쌓아 놓은 데이터 수를 나타내는 멤버이다.
•
front와 rear의 값이 같은 경우, 큐가 비어있은지, 가득찼는지 구별할 수 없는 상황을 피하기 위해 필요하다
•
큐가 비어있을 때 num은 0이고, 가득찼을 때는 num과 max의 값이 같다
num 과 max 가 없다면 front와 rear 값만으로는 두 상태를 구분할 수가 없다
초기화 함수 Initialize
•
Initialize 함수는 큐를 구현하기 위한 배열의 메모리 공간 확보 등의 준비 작업을 하는 함수이다
•
큐를 처음 만들면 큐는 비어 있으므로(데이터가 하나도 없는 상태) num, front, rear 값을 모두 0으로 한다
•
또 매개변수 max로 받은 ‘큐의 최대 용량'을 멤버 max에 저장한다
•
그리고 저장할 수 있는 요소의 개수가 max인 배열 que의 메모리 공간을 확보한다
// 큐 초기화
int Initialize(IntQueue *q, int max) {
q->num = q->front = q->rear = 0;
if ((q->que = calloc(max, sizeof(int))) == NULL) { // 저장할 수 있는 요소의 개수가
// max인 배열 que의 메모리 공간을 확보한다
q->max = 0; // 배열 생성에 실패
return -1;
}
q->max = max; // 매개변수 max로 받은 '큐의 최대 용량'을 멤버 max에 저장한다
return 0;
}
C
복사
배열을 위한 메모리 공간을 확보하는데 실패하면 max의 값을 0으로 해야하는데, 이는 존재하지 않는 배열 stk에 다른 함수의 접근을 막기 위해서이다.
인큐 함수 Enque
•
Enque 함수는 큐에 데이터를 인큐하는 함수이다
•
인큐에 성공하면 0을 반환하지만, 큐가 가득차서 인큐할 수 없으면(num ≥ max) -1을 반환한다
•
rear 값과 max이 같아지는 문제를 해결하기 위해서, rear값을 1만큼 증가했을 때, 큐의 최대 용량의 값인 max와 같아질 경우, rear를 배열의 처음인 0으로 변경한다.
// 큐에 데이터를 인큐
int Enque(IntQueue *q, int x) {
if (q->num >= q->max) // 큐가 가득 찼다면
return -1;
else { // 큐가 가득차지 않았다면
q->num++;
q->que[q->rear++] = x; //num과 rear을 1증가
if (q->rear == q->max) //만약 rear과 max가 같아진다면
q->rear = 0; // rear을 0으로 변경해준다
return 0;
}
}
C
복사
디큐 함수 Deque
•
Deque 함수는 큐에서 데이터를 디큐하는 함수이다
•
디큐에 성공하면 0을 반환하지만, 큐가 텅 비어 디큐할 수 없으면(num ≤ 0) -1을 반환한다
•
인덱스 초과 문제 발생시 (front값과 큐의 용량인 max와 같아진다면), front값을 배열의 처음인 0으로 변경해야한다.
// 큐에서 데이터를 디큐
int Deque(IntQueue *q, int *x) {
if (q->num <= 0) // 큐가 텅 비어 있다면
return -1;
else { // 큐가 텅 비어 있지 않다면
q->num--;
*x = q->que[q->front++]; //num을 1줄이고 front을 1증가
if (q->front == q->max) //만약 front와 max가 같아진다면
q->front = 0; //front를 0으로 변경
return 0;
}
}
C
복사
피크 함수 Peek
•
Peek 함수는 맨 앞의 데이터(디큐에서 꺼낼 데이터)를 ‘몰래 엿보는' 함수로, que[front]의 값을 출력만 한다.
•
데이터를 꺼내지 않아 front, rear, num의 값이 변하지 않는다
•
피크에 성공하면 0, 실패하면 -1 을 반환한다
// 큐에서 데이터를 피크
int Peek(const IntQueue *q, int *x) {
if (q->num <= 0) // 큐는 비어있다면
return -1;
*x = q->que[q->front]; // 맨 앞 데이터인 que[front]값만 출력
return 0;
}
C
복사
모든 데이터를 삭제하는 함수 Clear
•
Clear 함수는 현재 큐의 모든 데이터를 삭제하는 함수이다
인큐, 디큐는 num, front, rear 값을 바탕으로 값을 0으로 바꾼다.
실제 큐의 배열 요소의 값을 바꿀 필요가 없다.
// 모든 데이터 삭제
void Clear(IntQueue *q) {
q->num = q->front = q->rear = 0; // num, front, rear => 데이터 삭제
}
C
복사
최대 용량을 확인하는 함수 Capacity
•
Capacity 함수는 큐의 최대 용량을 반환하는 함수이다 (멤버 max 값을 그대로 반환)
// 큐의 최대 용량
int Capacity(const IntQueue *q) {
return q->max;
}
C
복사
데이터 개수를 확인하는 함수 Size
•
Size 함수는 현재 큐의 데이터 개수를 반환하는 함수이다 (멤버 num 값을 그대로 반환)
// 큐에 쌓여있는 데이터 개수
int Size(cont IntQueue *q) {
return q->num;
}
C
복사
큐가 비어있는지 판단하는 함수 IsEmpty
•
IsEmpty 함수는 큐가 비어있는지 판단하는 함수이다
•
비어있으면 1, 그렇지 않으면 0을 반환한다
// 큐가 비어있나
int IsEmpty(const IntQueue *q) {
return q->num <= 0;
}
C
복사
큐가 가득찼는지 판단하는 함수 IsFull
•
IsFull 함수는 큐가 가득 찼는지 판단하는 함수이다
•
가득 찼으면 1, 그렇지 않으면 0을 반환한다
// 큐가 가득차있나
int IsFull(const IntQueue *q) {
return q->num >= a->max;
}
C
복사
검색 함수 Search
•
Search 함수는 큐의 배열에서 x와 같은 데이터가 저장되어 있는 인덱스를 반환하는 함수이다
•
검색에 성공하면 찾은 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다
•
처음부터 선형 검색을 수행한다, 검색의 시작 지점은 큐의 첫 요소이다
•
현재 검색하는 위치의 인덱스를 구하는 식은 (i + q→front) % q→max 이다
// 큐에서 검색
int Search(const IntQueue *q, int 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; // 검색 실패
}
C
복사
모든 데이터를 출력하는 함수 Print
•
Print 함수는 큐의 모든 데이터를 처음부터 끝까지 순서대로 출력하는 함수이다
◦
현재 검색하는 위치의 인덱스 계산 방법은 Search 함수와 같다
// 모든 데이터 출력
void Print(const IntQueue *q) {
for(int i = 0; i < q->num; i++)
printf("%d ", q->que[(i + q->front) % q->max]);
putchar('\n');
}
C
복사
종료 함수 Terminate
•
Terminate 함수는 메모리 공간에 할당한 배열(큐)을 해제하는 함수이다
void Terminate(IntQueue *q) {
if (q->que != NULL)
free(q->que); // 메모리 공간에 할당한 배열 해제
q->max = q->num = q->front = q->rear = 0;
}
C
복사
IntQueue.c
#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"
// 큐 초기화
int Initialize(IntQueue *q, int max) {
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) // 큐가 가득 찼다면
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]; // 맨 앞 데이터인 que[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) {
int i, idx;
for (i = 0; i < q->num; i++) {
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;
}
C
복사
예제
#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"
int main() {
IntQueue que;
if (Initialize(&que, 64) == -1) {
puts("Fail to create for Queue");
return 1;
}
while(1) {
int m, x;
printf("Current Data's Count : %d / %d \n", Size(&que), Capacity(&que));
printf("(1)Enqueue (2)Dequeue (3)Peek (4)Print (0)Terminate : ");
scanf("%d", &m);
if(m == 0) break;
switch(m) {
case 1 :
printf("Data : ");
scanf("%d", &x);
if (Enque(&que, x) == -1)
puts("\aError : Fail to Enqueue.");
break;
case 2 :
if (Deque(&que, &x) == -1)
puts("\aError : Fail to Dequeue.");
else
printf("Dequeue Data is %d\n", x);
break;
case 3 :
if (Peek(&que, &x) == -1)
puts("\aError : Fail to Peek.");
else
printf("Peek Data is %d\n", x);
break;
case 4 :
Print(&que);
break;
}
}
Terminate(&que);
return 0;
}
C
복사