큐(queue)

* 큐(queue) 란 ?

- FIFO(First In Fisrt Out)

- 편하게 생각해보면 맛집에 줄 서있는 사람들을 떠올리면 될것이다.

  (먼저 줄을 선 사람 순서대로 식당에 들어간다.)

- 그외에 번호표, 버퍼(buffer) 도 같은 개념이라고 보시면 되겠네요 !

 

 

* 큐의 연산

- 삽입, 삭제, 비어있는지 확인, 맨 앞 (front) 확인,끝(rear) 확인 크기 등의 연산이 있다.

 

- 객체 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : enqueue(x)

           dequeue()

           front()              

           rear()

           peek() -> front에 위치한 데이터 확인

           empty()

 

- 시간 복잡도: (배열을 통한 구현으로 생각해보겠습니다.)

                   enqueue의 경우 배열 맨 끝에 추가하면 됩니다. O(1)

                   dequeue의 경우 배열의 앞에서 빼고 다른 요소들을 모두 하나씩 당기는 방식으로 구현할 경우 O(n)

                                         (이경우 front는 무조건 index가 0일 것이므로 따로 index변수를 관리 할 필요가 없겠죠)

                                         배열의 앞에서 빼고 front index를 따로 관리하여 +1만 해주는 경우 O(1) - 효율적

                   그 외 front(), rear(), peek() 등의 연산들은 index를 관리해줄 경우 모두 O(1) 타임 이겠죠?

 

* 큐 구현상의 문제점

                   만약 index를( 따로 front와 rear 를 가리키는) 관리해주는 방식으로  (효율적)

                   그럴 경우 배열의 크기는 정해져 있다는 것을 생각 해보면 계속 enqueue와 dequeue 작업을 수행하면

                   계속 뒤로 밀려지게 되다가 결국 배열의 크기를 넘어 가게 되면 오류가 발생하게 될 것 입니다.

                   이 때는 환형 배열을 이용 하면 이 방식의 문제를 해결할 수 있습니다.

                   만약 자료가 많아서 배열을 모두 채울경우 배열의 크기를 두배로 늘려서 다시 모든 요소들을 새로운

                   큰 크기의 배열로 옮겨주고 수행해야 하는 경우 enqueue 는 O(n) 타임이 걸릴 것입니다.

                   만약 연결리스트(링크드 리스트)로 구현할 경우 이러한 문제는 해결 할 수 있을것입니다.

                   하지만 링크드 리스트로 구현할 경우 코드상의 즉 런타임시간에 동적할당을 자주 해야 할것이고

                   이로인해 성능이 배열을 통해 구현한 순환큐 보다는 성능이 떨어질 수도 있습니다.

                   그러므로 만약 큐(자료)의 크기가 어느정도 예측이 가능할 경우 배열을 통한 순환큐가 

                   더 적절한 상황이 나타날 수 있습니다.

 

 

* 큐 활용의 예

(큐의 특성을 생각해본다면 매우 많겠죠???)

- 프린트기

- 너비우선탐색(bfs)

- 은행업무

- 그외 등등

 

* 큐의 구현

< 배열 이용한 구현>