- 제일 먼저 들어간 데이터가 제일 먼저 나오는 자료 구조
- 밀려드는 데이터를 보관할 장소, 큐
- 큐의 이용 예시 : 버퍼 Buffer
- FIFO(First In, First Out) 선입선출
- 삽입 연산은 후단 / 제거 연산은 전단에서 수행
+ 스택과 큐의 삽입과 제거
스택 삽입 Push / 제거 Pop
큐 삽입 Enqueue / 제거 Dequeue
* 순환 큐
- 큐를 배열로 구현하자니 제거 시 나머지 요소들을 옮기면서 비용이 듦
=> 전단을 가리키는 변수를 도입해, 열 내의 요소를 옮기는 대신 변경된 전단의 위치만 관리
후단을 가리키는 변수를 도입해, 삽입이 일어날 때마다 변경되는 후단의 위치 관리
- 제거 연산을 수행할 수록 큐의 가용 용량도 줄어들기 때문에
배열의 끝과 시작 부분을 이음!!
- 삽입이 이루어질 때마다 후단이 뒤로 후퇴하다가 전단을 만나면 => 가득찬 상태
- 비어있는 상태와 가득차 있는 상태를 구분!!
후단은 실제 후단에 1을 더한 값
=> 큐 배열을 생성할 때 실제의 용량보다 1만큼 더 크게 만들어 전단과 후단 사이를 비움
- 비어 있을 때 : 전단과 후단이 같은 곳을 가리킴
- 꽉 차 있을 때 : 후단이 전단보다 1 작은 값을 가짐
노드
typdedef int ElementType;
typedef struct tagNode
{
ElementType Data;
} Node;
순환 큐
typedef struct tagCircularQueue
{
int Capacity; //용량
int Front; //전단의 인덱스
int Rear; //후단의 인덱스 ---배열 내 인덱스
Node* Nodes; //노드 배열
} CircularQueue;
Rear는 실제의 후단보다 1 더 큰 값
배열의 크기는 실제 데이터가 담길 공간보다 1 큼
: 순환 큐가 공백 상태인지 포화 상태인지 구분하기 위한 더미노드 필요!
+ 쉽게 생각해 Queue -> Rear는 다음에 데이터를 저장할 곳을 미리 가리키고 있음ㅋㅋ
● 링크드 큐
- 각 노드는 앞 노드에 대한 포인터를 이용해 구성되어 있어
삽입은 새 노드의 포인터에 후단 연결
제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들임
+ 링크트 큐와 순환 큐의 비교
성능은 링크드 큐가 더 빠름 : 노드의 생성, 삭제를 위해 malloc() 필요 x
큐의 크기가 예측 가능하고 고성능이 필요한 버퍼는 순환 큐가 더 적절
노드
typedef Struct tagNode
{
char* Data;
struct tagNode; NextNode;
} Node;
링크드 큐
typedef struct tagLinkedQueue
{
Node* Front;
Node* Rear;
int Count;
} LinkedQueue;
출처 : 뇌를 자극하는 알고리즘 (한빛미디어)