자료구조_10.큐

큐의 이해

- 선입 선출(FIFO,First-in First-out)

:가장 먼저 삽입되는 개체가 가장 먼저 삭제되는 구조, 편의점에서 물건 채울때 원리

- 전단(front)은 큐에서 삭제가 일어나는 곳

- 후단(rear)응 큐에서 삽입이 일어나는 곳

스택은 뒤에서부터 나오고 큐는 앞에서부터 나온다

 

 

큐의 연산 - 삽입(Enqueue)

- 비어 있는 큐의 초기 상태에는 Front와 Rear 값 모두 -1로 설정,

- 자료가 삽입될 때마다 Rear가 1씩 증가하며 이동

- 새로운 자료를 삽입하기 위해서는 먼저 Rear 포인터를 증가시키고, 그 위치에 자료를 입력

값을 넣으면 Rear가 증가한다

 

큐의 연산 - 삭제(Dequeue)

- Front 포인터가 1씩 증가하며 자료를 삭제

- 마지막으로 입력된 자료가 삭제되면 Front포인터와 Rear 포인터의 값이 같아짐

값을 빼면 Front값이 증가하면서 빠진다

 

큐의 연산

큐의 단점

- 아래의 사진은 4개의 공간을 가지는 큐 구조에 'A','B','C','D' 4개의 자료를 삽입(Enqueue)하고 2개의 자료를 삭제(Dequeue)한 경우

 

앞에 메모리가 남아있지만 더이상 자료를 넣지 못함

 

원형큐의 이해

- 원형큐는 Rear나 Front가 배열의 끝에 도달하면 회전하도록 하여 메모리 공간을 좀 더 효율적으로 사용할 수 있음

 

- Front와 Rear의 초깃값은 0

- 원형큐는 자료공간이 가득 찬 것과 빈것을 구분하기 위해 Front가 위치한 곳은 자료를 저장할 수 없도록 비워두는 것이 일반적

- Front와 Rear의 값이 같다면 Empty

- Front의 공간은 항상 비워두기 때문에 Rear+1의 위치가 Front와 같게 된다면 Full