큐

스택이랑은 반대로 먼저 들어간것이 먼저 나오는 자료구조.
FIFO - Fist In First Out.

push와 pop 대신 EnQueue와 DeQueue를 사용.
push가 맨 앞에 넣기라면, EnQueue는 맨 뒤에 넣기.
pop과 DeQueue는 모두 맨 앞에서 제거하기.

어레이로 구현

원형

스택에서는 들어가는 쪽과 꺼내는 쪽의 방향이 똑같다.
하지만 큐는 들어가는건 뒤에서 들어가고, 꺼낼때는 앞에서 꺼낸다. 방향이 다르다.
그래서 일반 어레이로 큐를 구현하면, 배열의 앞 공간이 낭비될 수 있다. 길이 5의 어레이 [1,2,3,4,5]에서 1과 2가 빠지면 [ , ,3,4,5]가 된다.
인큐는 뒤에서부터 넣기때문에, 뒤에 공간이 없기 때문에 더이상 넣을 수 없게 된다(앞에 두 자리가 비어있음에도 불구하고).

그래서 (개념적으로)선형이 아닌 원형인 어레이를 사용한다.

이걸 구현하는 방법은 front, rear 포인터를 사용하는 것이다.

처음에 어레이를 만들때 front,rear 모두 -1으로 할당한다. (비어있음을 나타내기 위해서)

인큐

원리는 간단하다. 항상 rear의 순서에 값을 넣는것.arr[rear] = var.

1. 일단 큐가 꽉 차있는지 확인한다. (방법은 밑에서)
2. rear = rear + 1 (밑에서 다시 확인)
3. arr[rear] 자리에 값을 삽입

디큐

제거할때는 반대로 항상 front의 순서에서 값을 제거하는것.

1. 일단 큐가 비어있는지 확인한다. (방법은 밑에서)
2. front = front +1; (밑에서 다시 확인)
3. arr[front]에 있는 값을 반환.

큐가 꽉 차있는지, 비어있는지 확인 (모듈러)

보통은 rear - front를 하면 어레이 안에 몇개의 값이 있는지 확인할 수있겠지만,
만약에 한바퀴 이상 돌아가서 rear < front 인 상황에선 어떻게 할까?

[5, ,2,3,4] 꽉 차있는 상황에서 rear가 0이고 front가 2이라고 가정.
이제 다음 차례니까 rear++가 돼서 rear는 1이 되고, 여기에 어레이의 크기인 5를 더해서 6-2 = 4 니까 비어있는 자리가 하나 있는걸 알 수 있다. 즉 rear % arr.length를 해서 거기서 front만큼 빼주면 되는것.
정리하자면 if((rear+1) % arr.length - front==0) 의 조건이 참이면 큐가 꽉 차있는지 확인할 수 있다.

그래서 사실 위에서 인큐(rear 증가)과 디큐(front 증가)과정에서 rear,front를 증가시킬 때 모듈러 계산을 넣어줘야 한다.
rear = (rear + 1) % arr.length
front = (front + 1) % arr.length

비어있는지 확인은 어떻게 할까?
비어있다는건 front값(마지막으로 디큐한 후의 인덱스)이 rear(마지막으로 인큐한 후의 인덱스)가 같다는 것과 같다.
비어있는지 확인은 디큐하기 전에 하는것이니까 [ , , ,1, ]를 디큐한다고 가정해보자.
마지막 인큐한 후의 rear는 3일것이고,
마지막 디큐한 후의 front는 2일것이다.
rear != front이니 디큐 과정을 진행할 수 있다.
(front + 1 ) % 5를 하면 3이 된다. 그리고 1을 반환하고 제거.

이제 다시 또 디큐를 시도해보면 front == rear 불가능하고 실제로 어레이도 비어있다.

이전 시간에는 일반 어레이로 원형 어레이를 만들어 큐를 구현했다.
원형 어레이는 front와 rear 포인터를 가지고 개념적으로 구현한 어레이다.
지울때(디큐)마다 front 포인터의 값이 증가하고 추가할 때(인큐) 마다 rear값이 증가한다.

동적 배열로 구현

정적 배열로 구현한 큐에서 (rear + 1) % arr.length === front일때 큐가 다 찼다는걸 알 수 있다.
원형 어레이에서 빈 공간을 추가하려면 어떻게 해야할까?
일반 선형 배열에서는 그냥 새로운 2배 크기의 배열을 만들고 앞에서부터 하나씩 복사를 하면 됐었는데.

front > rear인 경우 (반대로 rear > front인 경우는 애초에 문제가 없다)

1. 새로운 2배 크기의 배열을 만들고
2. 0부터 rear까지 size(복사 전 원래 배열의 크기)+i 의 위치에 복사.
3. rear = rear + size 로 rear 포인터를 배열 끝으로.
   이렇게 하면 [c,d,e,a,b] rear=2 front3에서 [c,d,e,a,b,c,d,e, , ] 가 된다.
   앞에 있는 c,d,e는 front 앞에 있으니 사실상 지워진것 취급이 된다 (다음에 인큐를 할 때 덮어씌워질 테니까).

연결 리스트로 구현

마찬가지로 포인터가 두 개 필요하다. front와 rear.

삽입

1. 새로운 노드 생성, 값 입력
2. 새로운 노드의 next포인터에 null 입력
3. 큐가 비어있다면 (rear===null)front와 rear 모두 이 노드를 가리키게 한다.
4. 큐가 비어있지 않다면 rear가 새로운 노드를 가리키게 한다.

삭제

1. 큐가 비어있는지 확인 (rear===null)
2. temp 임시변수에 front 값을 넣어준다.
3. 큐의 front 포인터를 맨 앞 노드의 next값으로 변경.
4. front가 null이라면, 즉 큐가 비어있게 된다면 rear도 null로 설정.
   • 그렇지 않으면 다음에 인큐를 할 때 엄한 노드를 찾게되고 오류가 발생한다.
5. free(temp)