들어가기 앞서
큐는 스택과는 다른데요 생각보단 쉽습니다.
스택이 뭔지 모른다면 이전 게시물들을 보고 와주세요.
또한 연결 리스트 및 노드 개념이 필요하다면 더더욱 읽고 와주시오.
스택(Stack), c언어 구현 코드, 배열 기반 스택, 자료구조
들어가기 앞서 이제 리스트들을 거쳐서 Stack으로 왔어요.스택은 리스트보다 이해가 잘 될 것이라고 생각합니다. 노드를 포인터를 이용하여 연결하는 것이 기억안난다면? 혹은 기초적인 것이
8ehrmin.tistory.com
https://8ehrmin.tistory.com/5?category=1210683
연결 리스트(Linked List), C언어 구현, 코드(너 ㅋ 이해하고 싶어?)
들어가기 앞서 Linked List 즉 연결 리스트는, C언어를 사용한 자료 구조중에서도 가장 기초라고 생각합니다.이 아무것도 보르는 바보 C언어(C99)를 사용하여 백준을 풀때 가장 많이 사용했었쥬..
8ehrmin.tistory.com
큐(뀨)Queue
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다 (위키백과)
스택과는 달리 먼저 넣은애가 먼저 나오는 구조 FIFO, LILO 구조를 가지고 있는데요.
그러려면 입출구가 각각 있겠죠?
스택은 입출구가 한개씩도 아니라 그냥 하나여서 처음으로 들어온 애들은 나가기도 벅찼잖아요.
따라서 다음 그림과 같은 구조를 가지게 됩니다.
출구와 입구에 있는 요소 이름이 있는데요, 각각
front : 큐의 가장 앞 요소(가장 먼저 들어온 요소)
rear : 가장 마지막에 있는 요소 (가장 늦게 들어온 요소)
그럼 각각 front는 화남이가, rear는 삐죽이가 되겠네요.
Queue 삽입과 삭제 연산
삽입 연산 : rear에 노드를 덧 붙여, 새로운 rear를 만드는 연산
말 그대로네요 그림으로 볼까요?
제거 연산 : front 노드를 없애서, front 노드 뒤에있는 노드를 새로운 front 노드로 만드는 연산
제거하고보니
들어온지 오래 되었던, 화남이(front)가 제거 되고,
뒤에있던 히죽이가 새로운 front가 되었습니다.
순환 Queue
아무래도 front와 rear의 자리(인덱스)가 고정 된다면, 문제가 있습니다.
0번 index에 front 그리고 3번 인덱스에 rear을 가지는 배열이 있다고 예시를 들겠습니다.
그렇다면 제거 연산이 되었다면, 1번 인덱스에 있는 요소가 이동하여 새로운 front자리를 채워야할 것 입니다.
요소가 적다면 많은 연산이 필요하지 않지만, 요소가 100개인 상태에서 1개만 삭제되더라도, 99번은 움직여야 합니다.
또한 큐의 가용 용량도 줄어듭니다.
현재 8개의 공간을 사용할 수 있었고 4개의 요소에서 1개를 제거했습니다.
이 때 사용할 수 있는 용량은 총 4여야 합니다.
하지만, rear을 가리키는 포인터로 인하여 사용할 수 없게 되었습니다.
이게 반복될 수록 계속 줄어들겠죠.
따라서 이를 해결하기 위하여 시작과 끝을 연결한 순환큐가 나오게 됩니다.
순환 큐 (Circular Queue): 시작과 끝을 연결하여 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐
삽입 혹은 제거 연산이 될 때 마다, rear 혹은 front가 가리키는 포인터를 수정하여 노드를 관리합니다.
삽입이 계속되어 포화상태가 되었을 경우, 시작과 끝이 만나는 구조입니다.
하지만 이렇게 되어도 문제는 발생합니다.
바로 공색 상태와 포화 상태일 때 front및 rear은 같은 곳을 가리키고 있기 때문입니다.
이 문제를 해결하기 위한 가장 쉬운 방법은, 큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어 rear이 있을 자리를 만들어 주는거죠.
Queue 구조체
이전에한 설명에서 무엇 무엇이 필요할까요?
일단 배열을 기반으로 했을 때 필요했던 capacity가 있을 것 입니다.
또한 이 배열에서 몇번째 인덱스에 front와 rear이 있는지에 대한 정수형 변수가 필요하겠죠?
또한 해당 노드들이 저장된 주소도 필요할 것 입니다.
typedef int elementType;
typedef struct tagNode
{
elementType data;
}Node;
typedef struct circularQueue
{
int capacity;
int front;
int rear;
Node* nodes;
}circularQueue;
Queue 생성 및 소멸 연산
rear을 위하여 capacity보다 +1인 상태로 Nodes의 메모리를 할당해 줍시다.
해당 조건을 제외한 나머지는 이전에 설명한 내용과 동일합니다.
연결 리스트(Linked List), C언어 구현, 코드(너 ㅋ 이해하고 싶어?)
들어가기 앞서 Linked List 즉 연결 리스트는, C언어를 사용한 자료 구조중에서도 가장 기초라고 생각합니다.이 아무것도 보르는 바보 C언어(C99)를 사용하여 백준을 풀때 가장 많이 사용했었쥬..
8ehrmin.tistory.com
void createQueue(circularQueue** queue, int capacity)
{
(*queue) = (circularQueue*)malloc(sizeof(circularQueue));
(*queue)->nodes = (Node*)malloc(sizeof(Node) * (capacity + 1));
(*queue)->capacity = capacity;
(*queue)->front = 0;
(*queue)->rear = 0;
}
void destroyQueue(circularQueue* queue)
{
free(queue->nodes);
free(queue);
}Queue 삽입 연산
void enqueue(circularQueue* queue, elementType data)
{
int position = 0;
if (queue->rear == queue->capacity)
{
position = queue->rear;
queue->rear = 0;
}
else
{
position = queue->rear++;
}
queue->nodes[position].data = data;
}하나 알고 가야 하는 점은, 실제로 queue에서 rear은, 실제 rear 위치 값에 1을 더한 값 입니다.
왜냐하면 아까 사용자가 지정한 capacity에 공백을 더하여 순환큐의 문제점을 해결한바 있습니다.
따라서 rear은 계속 공백을 바라보고 있고, 실제 rear의 값은 그 이전값이 될 것 입니다.
잊었을지도 모르지만, front와 rear은 둘다 배열의 특정 인덱스 안 요소이기 때문이죠.
if문 조건문을 봅시다.
rear이 capacity와 같을 시, 0으로 초기화 해주는 이유는.
한바퀴 돌았으니 다시 0으로 가야하죠? 하루 24시가 25시가 되면 안되는 것과 같죠.
else문을 봅시다.
단순히 capacity 내의 인덱스 번호라면 ++ 연산자를 사용하여 증감해줍니다.
Queue 제거 연산
제거는 항상, 가장 앞에 있는 애 즉 가장 먼저 들어온 front가 제거되겠죠?
elementType dequeue(circularQueue* queue)
{
int position = queue->front;
if (queue->front == queue->capacity)
{
queue->front = 0;
}
else
{
queue->front++;
}
return queue->nodes[position].data;
}
공백을 제외한 이전 설명과 동일합니다.
queue의 full, empty 확인
먼저 포화상태인 full은 두가지의 경우가 있습니다.
각각 인덱스 번호의 차이인데요, 인덱스 번호가 front가 더 크냐, rear이 더 크냐로 볼 수 있습니다.
먼저 rear이 더 큰경우를 보겠습니다.
요소가 삽입될 수록, rear는 ++되면서 뒤로 가는데요, 이 때 클 경우 다음과 같은 조건으로 full인지 검사합니다.
rear - front == capacity
현재 상황으로 수를 넣어가며 생각 해 봅시다.
3 - 0은 6(배열은 7이지만, rear을 위한 공백을 포함하지 않아서 -1)과 같지 않기 때문에 포화상태가 아닙니다.
그럼 좀 더 넣어보겠습니다.
어떤가요?
꽉찼습니다.
다시 수를 넣어 계산하면,
6 - 0 == 6
포화상태가 되었습니다.
이제 다른 경우를 볼까요.
이 경우는 front의 인덱스 번호가 더 적네요.
이 때 full인지 확인하려면? 다음과 같은 조건을 비교합니다.
rear + 1 == front
2 + 1 == 3
그럼이제 empty는 어떻게 구별할까요?
그건 서로 같을 때 empty라고 정의합니다.
이제 코드를 보겠습니다.
int isEmptyQueue(circularQueue* queue)
{
return (queue->front == queue->rear);
}
int isFullQueue(circularQueue* queue)
{
printf("\n==풀 인가요==\n");
if (queue->front < queue->rear)
{
return queue->rear - queue->front == queue->capacity;
}
else
{
return queue->rear + 1 == queue->front;
}
}
Queue 배열 기반 예제 프로그램
#include<stdio.h>
#include<stdlib.h>
typedef int elementType;
typedef struct tagNode
{
elementType data;
}Node;
typedef struct circularQueue
{
int capacity;
int front;
int rear;
Node* nodes;
}circularQueue;
void createQueue(circularQueue** queue, int capacity)
{
(*queue) = (circularQueue*)malloc(sizeof(circularQueue));
(*queue)->nodes = (Node*)malloc(sizeof(Node) * (capacity + 1));
(*queue)->capacity = capacity;
(*queue)->front = 0;
(*queue)->rear = 0;
}
void destroyQueue(circularQueue* queue)
{
free(queue->nodes);
free(queue);
}
void enqueue(circularQueue* queue, elementType data)
{
int position = 0;
if (queue->rear == queue->capacity)
{
position = queue->rear;
queue->rear = 0;
}
else
{
position = queue->rear++;
}
queue->nodes[position].data = data;
}
elementType dequeue(circularQueue* queue)
{
int position = queue->front;
if (queue->front == queue->capacity)
{
queue->front = 0;
}
else
{
queue->front++;
}
return queue->nodes[position].data;
}
int isEmptyQueue(circularQueue* queue)
{
return (queue->front == queue->rear);
}
int isFullQueue(circularQueue* queue)
{
printf("\n==풀 인가요==\n");
if (queue->front < queue->rear)
{
return queue->rear - queue->front == queue->capacity;
}
else
{
return queue->rear + 1 == queue->front;
}
}
int getSizeQueue(circularQueue* queue)
{
if (queue->front <= queue->rear)
{
return queue->rear - queue->front;
}
else
{
return queue->rear + (queue->capacity - queue->front) + 1;
}
}
void circularQueueexe()
{
int i;
circularQueue* queue;
createQueue(&queue, 10);
for (int i = 1; i < 5; i++)
{
enqueue(queue, i);
}
int j = 0;
while (j < 3)
{
printf("dequ : [%d]\n", dequeue(queue));
printf("front : %d, rear : %d\n\n", queue->front, queue->rear);
j++;
}
i = 100;
while (isFullQueue(queue) == 0)
{
enqueue(queue, i++);
}
printf("용량 : %d\n", queue->capacity);
printf("사이즈 : %d\n", getSizeQueue(queue));
while (isEmptyQueue(queue) == 0)
{
printf("dequ : [%d]\n", dequeue(queue));
printf("front : %d, rear : %d\n\n", queue->front, queue->rear);
}
destroyQueue(queue);
}마치며
틀린 점이 있다면 알려주세요
이해 안가는 부분이 있다면 장문으로 물어도 좋으니 언제든 물어봐주시길 바랍니다.
참고
이것이 자료구조 알고리즘이다 with C언어