[자료구조] 큐(Queue)

큐(Queue)

- 스택과 다르게 선입선출(FIFO) 구조를 가진다

- 쉽게 말해 데이터를 저장하는 입구와 데이터를 삭제(출력)하는 출구가 다른 저장 방식 

- 예를 들어 번호표를 먼저 뽑은 손님이 먼저 서비스를 받는 상황

- front에서 데이터 삭제가 일어나고 , rear에서 데이터 삽입이 일어남

- 삭제를 Dequeue 라고하고 삽입을 Enqueue 라고 표현함

- peek : 스택 처럼 front에 있는 데이터를 읽음

기능

isEmpty

- 큐가 공백인지 아닌지 확인

isFull

- 큐가 포화상태인지 아닌지 확인

enQueue

- 데이터 삽입

deQueue

- 데이터 삭제

peek

- front 위치에 있는 데이터 읽음

Java 로 구현한 큐(Queue)

메인함수 구현 결과

순환 큐(Circular Queue)

- 큐는 FIFO구조를 가지기 때문에 rear에서 front 방향으로 데이터들이 이동함 

- front에서 Dequeue가 일어나면 차례대로 top-1  번부터 rear 까지 top~rear+1 까지 이동해야 하는 상황이 일어남

- 데이터의 갯수가 많으면 추가적인 연산이 많이 일어나 성능 저하가 발생함

- 이를 해결하기 위해 순환 큐가 등장

- 시작과 끝이 연결되어 있는 큐 (마치 더블 링크드 리스트 처럼)

- 항상 front 는 비어 있어야 함(Dummy공간, 공백/포화 상태를 구별하기 위해)

- Enqueue 명령시 FULL인지 확인하는 절차 필요 FULL이면 Enqueue 불가능

- rear와 front가 같으면 EMPTY / rear 다음이 front 이면 FULL