큐는 무엇인가?

1.큐의 정의

• 자료구조의 규칙 중 하나로 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식
• FIFO(First In First Out)
  파이포는 양 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 제일 처음에 들어온 데이터가 제일 빨리 처리되어 나가는 방식
  예시) 카페에서는 줄을 서서 먼저 온 사람의 주문을 처리하고 그 사람이 나간다. + 이메일 다중 전달, 게임 대기창, 알림, 푸시기능,티켓팅 사이트 등
• 큐에 새로운 요소가 들어올 시
  맨 뒤에 데이터가 들어가게되며,읽거나 삭제할 수 있는 행위는 큐의 맨 앞에 있는 요소에 의해 제한된다.

2.큐를 대표적으로 구현하는 방법

• 대표적으로는 정적인 어레이(Fixed Array)와 동적인 어레이(Linked List)가 있다.

  ㄱ.정적인 어레이(Fixed Array)를 이용해 큐를 구현하는 경우
  장점 : 구현이 쉽다
  단점 : 큐의 크기가 고정되어있다.(넘치면 오버플로우)
  또한 이 경우는 큐의 맨앞 인덱스나 위치를 담는 first라는 변수, 새 요소를 추가할 수 있는 정적 배열에서 다음으로 사용 가능한 슬롯의 인덱스나 위치를 담는 next라는 변수를 사용한다.

  ㄴ.동적인 어레이(Linked List)를 이용해 큐를 구현하는 경우
  장점 : 구현이 전자에 비해 더 어려움
  단점 : 큐의 크기를 자동으로 조절할 수 있다.
  이 경우는 큐의 맨앞 인덱스나 위치를 head, 새 요소를 추가할 수 있는 동적 배열 마지막 인덱스 또는 위치를 나타내는 tail이라는 변수를 사용한다.

3.큐의 대표적인 함수들

• Enqueue(인큐) : 큐에 값을 집어넣은 함수
• Dequeue(데큐) : 큐에서 값을 빼내는 함수
• Size : 큐의 크기를 확인하는 함수
• Empty : 큐가 비어있는지 확인하는 함수

4.큐의 동작 시뮬레이션

ㄱ.스탠다드한 정적배열시 기준
a.데이터가 없을때 : first와 next가 같은 곳을 가리킴(첫번째)
b.enqueue(queue에 A를 넣음)로 데이터가 하나 들어왔을때 : first가 맨 앞 데이터 A가 있는곳을 가리키고 next는 다음에 데이터가 들어올 위치를 가리키게됨
c.enqueue(queue에 B를 넣음)로 데이터가 추가로 들어왔을때 : 큐는 맨 처음에 있는애를 기억해야되기때문에 first가 맨 앞 데이터 A가 있는곳을 가리키고 next는 B를 쓰고 다음에 데이터가 들어올 위치를 가리키게됨
d.dequeue로 데이터를 뺄 때 : 삭제는 맨앞부터 되는거니깐 A가 삭제됨 그러면서 first는 한 칸 이동하면서 B를 가리키게되고 next는 그 자리를 유지한다.

5.큐의 다른 형식

• Circular Queue(환형 큐)
  정적인 어레이가 원형띠 모양이라고 생각하면된다.데이터의 입출력이 원형의 행동양식으로 이루어짐
• Priority Queue(우선순위 큐)
  큐의 규칙인 FIFO가 적용되지않아 맨 앞이 먼저 처리되는게 아닌 중요성이 있는 데이터 우선순위순으로 배열이 재배치되어 처리하게된다.

         출처 : 유튜브 Gunny's Algorithm Together

6.코딩해서 큐 구현해보기

#include<stdio.h>
#include<stdlib.h>

#define MAX 5

typedef struct Queue {
	int front; //앞 쪽 index
	int rear;  //뒤 쪽 index
	int data[MAX];
} Queue;

void init(Queue* q)
{
	q->front = q->rear = -1;
}

int is_full(Queue *q){
	if (q->rear == MAX - 1)
		return 1;
	return 0;
}

int is_empty(Queue *q){
	if (q->front == q->rear)
		return 1;
	return 0;
}

void enqueue(Queue* q, int item)
{
	if(is_full(q))
	{
		printf("Error Queue is full");
		exit(1);
	}
	q->data[++(q->rear)] = item;
}

int dequeue(Queue* q) {
	if (is_empty(q))
	{
		printf("Error Queue is empty");
		exit(1);
	}
	return q->data[++(q->front)];     
}

int main()
{
	Queue q;
	init(&q);

	enqueue(&q, 3);
	enqueue(&q, 2);
	enqueue(&q, 1);

	printf("%d\n", dequeue(&q));
	printf("%d\n", dequeue(&q));
	printf("%d\n", dequeue(&q));


	return 0;
}

• 메인함수에서 호출문에 들어가는 인자 중 포인터로 받는건 반드시 인자에 &를 붙여 주소값을 보내주게 만들어야된다!

• 이해 안된 부분 공부

  return q->data[++(q->front)]

chat GPT를 활용하여 내가 이해안되는 부분에 대해 질문했다.

1.이 코드를 자세히 설명해줘.
답변
"이 코드는 앞 요소의 값을 반환한 다음 앞 인덱스를 대기열의 다음 요소로 이동하여 대기열에서 요소를 제거합니다. 대기열에서 첫 번째 요소를 효과적으로 제거하고 해당 값을 반환합니다.

• 내가 이해한 결과
  -> 즉 dequeue를 첫번째 호출했을 때 인덱스는 -1인 상태였으니 0으로 이동하고 front도 0을 가리킨다.그리고 이때 front가 가리키는 데이터 '3'이 반환된다.

• 두번째 호출 시 인덱스와 front는 0에서 1을 향하게되고 데이터 '2'를 반환한다.
• 세번째 호출 시 인덱스와 front는 1에서 2를 향하게되고 데이터 '1'을 반환한다.

2.사전증가연산으로 다음 인덱스로 이동하면 이전 인덱스와 그 안의 요소가 자동으로 삭제되는거야?
답변
"아닙니다.주어진 dequeue 코드에서 queue의 다음 요소로 이동하기 위해 앞 인덱스가 증가할 때 이전 요소는 자동으로 삭제되지 않습니다.대기열을 나타내는 배열의 데이터는 대기열에서 빼기 작업 중에 수정되지 않습니다. 앞 인덱스는 단순히 다음 요소를 가리키도록 이동되어 대기열의 논리적 보기에서 앞 요소를 효과적으로 "제거"하지만 배열의 실제 데이터는 변경되지 않은 상태로 유지됩니다.
dequeue 연산은 큐의 앞에 요소를 제거합니다. 대기열에서 빼낸 요소의 데이터는 여전히 배열에 존재하지만 전면 인덱스가 앞으로 이동했기 때문에 더 이상 활성 대기열의 일부로 간주되지 않습니다.

• 내가 이해한 결과
  데이터가 사라지는게 아니라 배열에 남아있긴하지만 요소가 활성화되지않는거구나

3.그렇다면 dequeue로 앞 요소가 사라졌을때 앞 요소의 데이터는 사라지는게 아니라 배열에 존재하지만 전면 인덱스가 앞으로 이동했기 때문에 더 이상 활성 대기열의 일부로 간주되지 않는다고하면 그럼 dequeue라는 함수는 queue의 앞 요소만 제거하는 함수가 맞아?

• 답변
  맞습니다. dequeue 함수는 큐의 앞 요소만을 제거하는 함수입니다. 큐에서 데이터를 dequeue하면, 해당 데이터는 배열에 여전히 존재하지만, 논리적으로 큐의 일부로 간주되지 않게 됩니다. 즉, dequeue 연산은 배열의 데이터를 삭제하는 것이 아니라, 큐의 front 인덱스를 증가시켜서 큐에서 논리적으로 더 이상 해당 데이터를 포함하지 않도록 만드는 것입니다.

4.queue는 배열을 가지고 있는 구조체 변수의 주소와 front와 rear 를이용해서 배열의 일부분만 활성화를 해서 데이터를 다루는 자료구조인게 맞아?

• 답변
  일반적으로 큐는 배열로 구현되며, front와 rear 변수는 배열에서 데이터를 추가하거나 제거할 위치를 가리킵니다. front는 큐의 가장 앞을 가리키고, rear는 큐의 가장 뒤를 가리킵니다. 큐의 데이터는 front와 rear 사이에 위치하며, front와 rear 사이에 있는 부분만이 활성화된 큐의 요소들입니다. 새로운 데이터가 enqueue되면 rear가 증가하고, dequeue되면 front가 증가하여 활성화된 큐의 범위를 조절합니다. 이를 통해 큐는 FIFO(First-In-First-Out) 원칙을 따르는 데이터 구조로 동작합니다.
  -> 그래서 front가 증가되는 코드를 썼었구나

7.큐의 문제점
위 예제와 같이 데이터를 계속 넣고 빼게되면 결국 배열의 인덱스가 초과하게된다.그래서 예제에서 5개를 넣고 모두 dequeue를 하게된다면 그 큐는 더이상 사용할 수 없다.-> 그래서 원형큐가 나오게된다.

해결방법 : 원형큐를 쓰기

                                       출처 : 유튜브(Hard Code 하드코드)