Chap 04.큐(Queue)

먼저 들어간 것이 먼저 나오는

First In First Out   =   FIFO
ex) 줄서기

---

typedef struct_lQueue
{
	Node* front;
	Node* rear;
}LQueue;	//연결리스트

typedef struct _cQueue
{
	int front;
	int rear;
	Data queArr[QUE_LEN];
}CQueue;	//배열

rear - 입구를 나타내는 인덱스/노드
front - 출구를 나타내는 인덱스/노드

데이터 저장(enqueue) 하면 rear 이 이동
데이터 삭제(dequeue) 하면 front 가 이동

---

● 큐(배열)의 문제점

비어있는 배열이 있지만, R이 오른쪽으로 이동할 수가 없다.
따라서, 이런 단점을 보완하기 위해 '원형 큐'가 도입되었다.

 

---

● 원형 큐의 문제점

R + 1 == F    ==> 원형 큐가 꽉참
R + 1 == F    ==> 원형 큐가 텅빔
즉, 큐가 꽉차면서 텅비었다? 텅빈것과 꽉 찬것이 구분이 안된다는 문제점 발생

----------------------------------------------------해결법-------------------------------------------------------

원형 큐가 초기화될때 F와 R이 같은 index(0)를 가리키게함.
데이터가 저장될때 R은 index를 1 증가한 후 저장한다.

즉, 원형 큐의 0 index를 버린다.

---

 

출처 : 윤성우의 열혈 자료구조