[자료구조] 큐(Queue)

• 큐(queue)

- 저장 공간 안에 먼저 입력된 데이터부터 순서대로 출력되는 구조

- 양쪽 반대 방향에서 각각 삽입과 삭제가 이루어짐

- FIFO(First In First Out) 구조

- 연산을 수행하기 위해 자료의 삽입과 삭제를 구분하여

   각각의 위치를 지정할 두개의 포인터가 필요함(front, rear)

 

‣ front 포인터

- 큐의 앞쪽(head)에 위치하여 자료가 출력되는 지점을 가리킴

‣ rear 포인터

- 큐의 뒤쪽에서 자료를 입력하는 곳을 지정해줌

---

• 자료 삽입

- front와 rear의 초기 값은 -1로 설정

- 큐에 새로운 자료를 삽입할 때에는 rear 포인터를 먼저 1 증가

- rear와 큐의 크기가 같아지면 더 이상의 삽입 연산은 불가능함

---

• 자료 삭제

- 큐에서 자료는 입력된 순서에 따라 순서대로 삭제가 이루어짐

- front 포인터가 삭제할 자료로 먼저 이동하여 자료를 삭제함

- 추가 자료의 삽입이 없는 상태에서 자료를 삭제하게 되면

  마지막으로 입력된 자료가 가장 마지막에 삭제됨

- front와 rear 값이 같으면 더 이상 삭제할 자료가 없다는 것을 의미함