연결 리스트 기반 큐(List Base Queue) 개념

[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]

큐(Queue)는 선입선출 기반 자료구조이다.

즉, 스택과 달리 먼저 들어온것이 가장 먼저 나가는 구조이다.

1 2 3 4 5로 들어온 입력값은 1 2 3 4 5로 나간다.

그리고 연결 리스트 기반 큐는 노드를 나타내는 구조체와, 노드를 가리키는 Front,Rear를 가진 구조체로 표현된다.

이렇게 1~10까지 입력을 하면 각 노드에 1~10값이 들어가고 큐에서 이제 뽑아내는 과정을 갈때

F가 먼저 한칸앞으로 간뒤 그다음 값을 도출한다. (도출하며 노드를 소멸시킨다.)

물론, 처음 1만 가지고있을땐 F와 R은 같은 1을 가리키고있고, 입력할때에는 F는 1에고정, R이 1 -> 10까지 이동한다.

delNode = pq->front; // delNode는 pq의 front가 가리키는 값을 가리킨다.
retData = delNode->data; // retData는 delNode의 data값
pq->front = pq->front->next; // pq의 front는 pq의 front가 가리키는 그 노드중 그 노드의 next가 가리키는 것을 가리키도록 한다. 
 
free(delNode);
return retData;

위의 그림과 함께 코드를 살펴볼때,

이 과정이 Dequeue함수의 과정인데 delNode는 포인터값이고 retData는 int형 자료형이다.

delNode는 F의 위치를 받아내고, retData는 delNode가 가리키는 data값을 받아온다.(아직까진 pq->front->data와 같다.)

그리고 난뒤 pq->front = pq->front->next;에 의해 F가 한칸 앞으로 이동하고

free(delNode);에 의해 이전 1이들어있던 노드는 소멸된다.

그다음 retData는 1을 반환하게 된다.

※ 마지막에 F도 10을 가리키고 R도 10을 가리키게 될때는 위의 그림처럼 행동한다면 F는 NULL값을 가지게되고 R은 쓰레기값을 가리키게된다. 

이런 상황이 오면 큐가 오류를 범할것같지만 상관이없는것이 소스코드를 보면 알다시피

 QIsEmpty에서 F가 NULL인지만 체크하기때문에 R은 쓰레기값을 가리키고있어도 상관없다.