Queue, 원형 Queue와 배열기반 Queue

 

 

 

개념

 자료가 앞에서 삽입되고 앞에서 먼저 삭제가 되는 선형 리스트. FIFO(First In First Out) 구조이다. 가장 먼저 삽입 된 자료가 가장 먼저 삭제되는 형태이다.

Queue의 멤버

• rear : 현재 맨 뒤 요소를 말한다. 새로운 요소가 맨 뒤 요소가 된다.
• front : 현재 맨 앞 요소이다.
• addq : 자료를 삽입하는 함수
• deleteq : 자료를 삭제하는 함수

Queue 예시

큐의 문제점, 대안

 큐를 삽입시 rear가 증가하고 front 역시 증가한다. 큐가 꽉 찰 경우 front와 rear를 조정해야 하는 소요가 발생한다. 원형 큐를 만들면 계속 순환하기에 조정할 필요가 없어진다.

원형 큐

 원형 큐는 front와 rear가 계속 돌고 돌기 때문에 원형 큐라 한다. 마치 큐가 원형으로 되어있는 것처럼 묘사가 가능하여 원형 큐라 한다. 원형 큐를 만드는 방법은 기존에서 그리 어렵지 않다. 연결 리스트로 구현한다면 처음과 끝 노드를 연결해주면 되고 (연결 리스트는 굳이 원형 큐를 만들 필요가 그렇게 없다. 애초에 front rear를 조정할 필요가 없기 때문, 그래도 굳이 만든다면 가정 아래 예시이다. 오히려 연결 리스트는 원형 큐가 손해이다.) 배열 기반 큐는 rear+1을 max_size로 나누면 된다. front 역시 똑같다.

rear=(rear+1)%Max_size
front=(front+1)%Max_size

큐의 활용

• Buffer
• 스케줄링
• 프린터 스풀링

 큐의 기본 개념으로 프린터의 스풀링, 순서대로 처리하는 스케줄링 버퍼와 같은 곳에 활용 할 수 있다. 원형큐가 대부분 쓰이며 표준입출력(stdio), 장치드라이버등 여러곳에서 쓰인다.