1. 큐
1) 큐의 모델 : 기다리는 줄. 대기라인
2) 가장먼저 넣은 것이 가장 먼저 나온다.(FIFO : First in First out)
3) 삽입 : 리스트의 맨 끝 / 삭제: 리스트의 맨 앞
>> 양쪽 끝이 모두 사용된다.
4) 작업 : Add(큐 추가), Remove(큐 삭제), init_que(큐 초기화)...
5) 큐 작업시 필요한 포인터 : Front ( 큐의 맨 앞을 가르킨다.) Rear ( 큐의 맨 뒤를 가르킨다.)
ex)
Add
typedef struct node{
int id;
struct node *next
}Node;
Node *front, *rear;
int count = 0;
void Add(int n){
Node *new = malloc(sizeof(Node)); //동적 할당
new -> id = n; //값 대입
if ( count == 0 ) { //큐가 초기화 되있다면
front = rear = new; //front와 rear가 새로운 것을 가르키게함.
}else{ //그렇지 않다면
rear -> next = new; //현재 노드 다음에 새로운 것을 붙이고
rear = new; //rear 만 새로운 것을 가르키게함
}
new -> next = 0;
}...............
6) front를 사용하지 않고 원형 연결리스트를 사용한다면 , Rear로 Front위치에 접근이 가능하다.
> 삽입과 삭제에 유용하다. 큐의 크기가 정해져 있어야한다.
> 큐가 비어있다가 새로운 노드가 추가되면 자기 자신을 가르키는 포인터가 된다. ( Self - pointing Node!! )
7) 큐를 배열로 구현시...
> 큐가 점점 오른쪽으로 밀리는 표류 현상이 나타난다.
> 해결안 : 왼쪽이동, rear감소
>> 시간적 소비가 크다. 불편하다.
> 원형배열을 사용한다. : rear값을 한없이 증가 시키지 않고 Max가 되면 초기화 되어 배열을 순회한다.
>>큐의 empty상태 chack가 중요함!!
8) 큐 응용
> 스택과 함께 사용하여 회문을 검색할수 있다.
> 너비 우선 탐색이 가능하다
> 덱 : 키보드 입력 버퍼 의 구현
> 각종 대기열의 모습