큐
스택과 동일하게 데이터를 일시적으로 쌓아놓은 자료 구조로 가장 먼저 넣은 데이터(프런트)를 가장 먼저 꺼내게 된다.
선입 선출(FIFO, First In First Out)
▶ 인큐 : 큐에 데이터를 넣는 작업
▶ 디큐 : 데이터를 꺼내는 작업
▶ 피크 : 맨 앞의 데이터를 확인
데이터를 꺼내는 쪽을 프런트라고 하고, 데이터를 넣는 쪽은 리어라고 한다.
일반적인 큐에서는 디큐 과정에서 프런트에 있는 값이 제일 먼저 빠지므로 두 번째 이후의 요소는 하나 씩 앞쪽으로 이동해야 한다. 이 처리의 복잡도는 O(n)이다.
큐 구조체 (IntQeue)
아래 코드는 큐를 관리하는 구조체로 3개의 멤버와 프런트/리어로 구성된다. 이때 앞서 다룬 스택 포인터는(스택에 저장된 데이터 개수) pst으로 선언했으나 큐에서는 큐에 저장된 데이터의 개수를 num이라는 변수로 선언한다.
typedef struct{
int max; //큐의 용량
int num; //현재 데이터 개수
int front; //프런트
int rear; //리어
int *que; // 배열 포인터 == 큐의 맨 앞 요소에 대한 포인터
} IntQueue;링버퍼를 이용한 큐
링버퍼란 배열 요소를 앞쪽으로 옮기지 않는 큐를 위해 사용하는 자료 구조배열의 처음과 끝이 연결되어 있다고 보는 자료 구조이다.
여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트와 리어이다.
링버퍼를 이용해 큐를 구현하면 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 일반적인 큐에서 불필요한 순서 이동을 배제할 수 있으며 복잡도는 O(1)이다.
· front : 논리적으로의 첫번째 요소
· rear : 논리적으로의 마지막 요소
큐 함수
front와 rear의 상태가 비어 있는 거나 가득 차 있는지 경우 front와 rear의 값이 같아 두 상태를 구분할 수 없다.
따라서 현재 큐에 쌓아놓은 데이터 개수를 구분하기 위해 추가적인 num이라는 멤버가 존재해야 한다.
초기화 함수 [ Initialisze ]
Initialisze 함수는 큐의 변수를 초기화하고 메모리 공간을 확보하는 작업을 수행한다. 기본 알고리즘은 아래와 같다.
· 큐를 처음 만들 때 큐는 비어있으므로 num, front, rear의 값을 모두 0으로 만든다.
· 매개변수 max로 받은 큐의 최대 용량만큼 배열 que을 동적할당한다.
코드는 아래의 [더보기] 란을 확인한다.
int Initialize(IntQueue *Que,int max){
Que->num = Que->front = Que->rear = 0;
//큐의 변수 초기화
/**
현재 데이터 개수, 프런트, 리어를 모두 0으로 저장
대입은 <- 순으로 0 저장됨.
*/
Que->que = (int*) malloc(sizeof(int)*max);
//큐에 사용할 배열을 동적할당: 인자로 받은 큐의 용량만큼 동적할당
if(Que->que == NULL){
//동적할당 실패 시 용량 0 초기화 및 종료
Que->max = 0;
return - 1;
}
//동적할당 성공 시
Que-> max = max;
//큐의 '공식' 용량을 업데이트
return 0;
}인큐 함수 [ Enque ]
Enque 함수는 큐에 데이터를 인큐 하는 함수이다. 인큐에 성공하면 0을, 실패하면(큐가 가득 찬 경우) -1을 반환한다.
인큐 함수에서는 인자로 받은 데이터 값을 배열에 저장하고, 리어값을 증가시켜 다음 큐를 가리키게 한다 이때 주의할 점은, 인큐 과정에서 rear값과 max값이 같아지는 경우이다. rear값과 max값이 같아지면 실제 배열에 없는 공간을 가리키기 때문에 오류가 발생하게 된다.
이러한 오류를 방지하기 위하여 다음과 같은 조건문을 이용하여 rear값과 max값이 같아지는 경우를 방지한다. 리어값이 1 증가했을 때 max와 같아지는 경우 리어값을 0으로 변경한다.
| if(Que->rear == Que ->max) Que->rear = 0; /*rear값을 1만큼 증가할때 큐의 최대 용량의 값인 max와 같아질 경우 rear의 값을 배열의 처음인 0으로 변경한다.*/ |
코드는 아래의 [더보기] 란을 확인한다.
int EnQue(IntQueue *Que,int data){
if(Que->num >= Que->max) return -1;
/**
큐의 현재 데이터 개수가 큐의 최대 용량보다 큰 경우 -1 반환 후 종료
>> 현재 데이터 개수가 최대 용량보다 크거나 작으면 더 이상 데이터 추가할 수 없음.
*/
Que ->num ++;
//큐의 현재 데이터 개수 증가
Que->que[Que->rear ++] = data;
/*큐가 가리키는 현재 인덱스에 데이터를 추가하고 rear(후미 인덱스) 값을 증가한다.*/
return 0;
}인큐 함수 [ Deque ]
Deque 함수는 큐에서 데이터를 디큐 하는 함수이다. 디큐에 성공하면 0을 반환하며 큐가 비어 있어 디큐할 수 없는 경우 -1을 반환한다.
디큐도 인큐와 마찬가지로 인덱스 초과 문제가 발생하며, 디큐하기전의 front값이 배열의 끝이라면 front의 값은 max가 되어 배열 마지막 요소의 인덱스를 초과하게 된다. 이러한 오류를 방지하기 위해 다음 조건문을 이용하여 front와 max의 값이 같아지는 경우를 방지한다.
| if(Que->front == Que->max) Que->front = 0; |
코드는 아래의 [더보기] 란을 확인한다.
int DeQue(IntQueue *Que,int *data){
if(Que->num <=0) return -1;
/**
큐의 현재 데이터 개수가 0과 같거나 작으면 -1 반환 후 종료
>> 현재 데이터 개수가 없으면 데이터를 디큐 할 수 없음
*/
Que->num --;
//현재 데이터 개수를 1 감소
*data = Que->que[Que->front++];
//인자로 받은 data에 현재 인덱스의 값을 저장하고 front를 증가 == 현재 인덱스 데이터를 빼냈기 때문
if(Que->front == Que->max) Que->front = 0;
/**
만약 큐의 front가 큐의 최대 용량보다 같은 경우
>>예를 들어 최대 용량이 10(0~9)인 큐에서 디큐를 9인덱스에서 하게되면 인덱스가 10으로 초과한다.
따라서 front값을 맞춰주기 위해 이 조건문을 사용한다.
*/
return 0;
}확인 함수 [ Peek / Search ]
Peek 함수는 맨 앞의 데이터를 확인하는 함수이다. 이는 꼭대기 값을 저장 후 삭제하지 않는 디큐 함수와 구조가 같다.
데이터를 꺼내지 않아 front, rear, num의 값이 변하지 않으며 성공 시 0, 실패하면 -1을 반환한다.
Search 함수는 임의의 값의 데이터가 스택의 어느 위치에 쌓여있는지 검사하는 함수이다. 검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다. 검색은 꼭대기의 데이터부터 바닥의 데이터로 후입 선출의 순서로 선형으로 진행한다.
코드는 아래의 [더보기] 란을 확인한다.
int Peek(IntQueue *Que,int *data){
if(Que->num <= 0 ) return -1;
/**
큐의 현재 데이터 개수가 0과 같거나 작으면 -1 반환 후 종료
>> 현재 데이터 개수가 없으면 데이터를 피크 할 수 없음
*/
*data = Que->que[Que->front];
//맨 앞의 데이터 == 디큐에서 꺼낼 데이터를 저장
return 0;
}
int Search(IntQueue *Que,int data){
int idx;
for(int i=0;i<Que->num;i++){//현재 데이터 개수 만큼 반복
if(Que->que[idx = (i + Que->front)%Que->max] == data) return idx;
/**
큐가 가리키는 배열의 인덱스를 증가하면 인자로 받은 값과 확인.
(i + Que->front)%Que와 같이 나머지 연산을 사용하는 이유는 front가 0~9일 수 있지만
3~9~2일 수 도 있기 때문!
이때 값을 찾은 인덱스를 반환
*/
}
return - 1;
}
용량 함수 [ isEmpty / isFull / Size / Capacity ]
isEmpty와 isFull은 각각 큐가 비어있으면(데이터 개수가 0 이하) 1을 반환, 큐가 가득 찼으면 1, 아니면 0을 반환한다.
코드는 아래의 [더보기] 란을 확인한다.
Capacity 함수는 스택의 최대 용량을 확인하며 Size 함수는 현재 스택에 쌓여있는 데이터의 개수를 반환하는 함수이다.
코드는 아래의 [더보기] 란을 확인한다.
int IsEmpty(IntQueue *Que){return Que->num <=0;}
/**
큐가 비어있는지 확인
>> 큐의 현재 데이터의 개수가 0보다 작으면 1
*/
int IsFull(IntQueue *Que){return Que->num >= Que->max;}
/**
큐의 저장공간이 가득 찼는지 비교
>> 큐의 현재 데이터의 개수가 최대 용량보다 크면 1반환 아니면 0
*/
int Capacity(IntQueue *Que){return Que->max;}
출력 함수 [ Print ]
print 함수는 큐의 모든 데이터를 처음부터 끝까지 순서대로 출력하는 함수이다.
코드는 아래의 [더보기] 란을 확인한다.
void Print(IntQueue *Que){
for(int i=0;i<Que->num;i++) printf("%d ",Que->que[(i + Que->front)%Que->max]);
// Search와 같은 로직으로 모든 데이터 출력
}삭제함수 [ Clear ]
Clear 함수는 현재 큐의 모든 데이터를 삭제하는 함수이다. 인슈 디큐는 큐 구조체 멤버인 num, front, rear의 값에 따라 저장 인덱스를 불러오므로 실제 큐의 배열의 요소값을 바탕을 바꿀 필요가 없다.
코드는 아래의 [더보기] 란을 확인한다.
void Clear(IntQueue *Que){Que->num = Que->front = Que->rear = 0;}
//모든 큐의 인덱스를 초기화하여 접근을 제거종료 함수 [Terminate ]
Terminate 함수는 메모리 공간에 할당한 배열(큐)을 해제하는 함수이다. free 함수를 이용해 동적할당을 해제하고 모든 멤버의 값을 0으로 초기화한다.
코드는 아래의 [더보기] 란을 확인한다.
void Terminate(IntQueue *Que){
if(Que->que != NULL) free(Que->que);//큐의 배열이 할당되있으면(메모리 공간이 차있으면) 메모리 공간 해제
Que->max = Que->num = Que->front = Que->rear = 0;
//큐의 매개변수를 초기화
}[+] 링버퍼를 이용한 큐 알고리즘
링 버버퍼는 '오래된 데이터를 버리는' 용도로 사용할 수 있다. 요소의 개수가 n인 배열에 계속해서 데이터 값이 들어올 때 배열의 최대 용량인 max를 넘길 시에는 가장 오래된 데이터 자리에 새로운 데이터를 저장하는 방식으로, 입력은 무한히 가능하나 배열에 저장되는 데이터 값은 유한하다.
링버퍼 알고리즘에서는 리어값이 max값을 넘길 경우 다시 [0]로 돌리는 로직을 사용한다.
| Que->que[(Que->rear ++)%Que->max] = data; |
링버퍼를 이용한 인큐 함수는 아래 코드를 참고한다.
int EnQue_Ring(IntQueue *Que,int data){
if(Que->num >= Que->max) return -1;
/**
큐의 현재 데이터 개수가 큐의 최대 용량보다 큰 경우 -1 반환 후 종료
>> 현재 데이터 개수가 최대 용량보다 크거나 작으면 더 이상 데이터 추가할 수 없음.
*/
Que ->num ++;
//큐의 현재 데이터 개수 증가
Que->que[(Que->rear ++)%Que->max] = data;
/**큐가 가리키는 현재 인덱스에 데이터를 추가하고 rear(후미 인덱스) 값을 증가한다.*/
return 0;
}'Datastructure > [7] 큐' 카테고리의 다른 글
| [7] 큐 ⑥ 응용 : 연결리스트를 이용한 데크 구현 (0) | 2024.05.22 |
|---|---|
| [7] 큐 ④ 덱(deque) (0) | 2024.05.22 |
| [7] 큐 ⑤ 응용 : 배열로 구성된 원형 큐 ADT 구현 (1) | 2024.05.22 |
| [7] 큐 ③ 연결리스트 ADT (0) | 2024.05.20 |
| [7] 큐 ② 배열 ADT (0) | 2024.05.20 |
