QUEUE

FIFO(First In First Out)

티켓을 사려고 줄을 서서 기다리는 모습, 고속도로를 통과하는 자동차들과 같이 먼저 들어간 자료가 먼저 나오게 됩니다.

 

Queue의 특징

1.FIFO

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

3. 두개의 입출력 방향을 가지고 있습니다.

 

=>가장 앞에 있는 데이터를 꺼내오기 때문에 그 다음 인덱스의 데이터들을 한 칸씩 모두 이동해야 하는 단점이 ㅇㅆ다.

Queue의 사용처

컴퓨터와 연결된 프린터의 인쇄

컴퓨터 장치들 사이에어 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간의 차이를 극복하기위해 임시 기억장치의 자료구조로 Queue를 사용. 이것으 통틀어 버퍼(buffer)라고 한다.

 

 

---

++원형 큐(Circular Queue)

원형 큐는 선형큐의 문제점을 보완하기 위한 자료구조. 
인덱스 변수가 front, rear 두개 존재.

원형 큐에 데이터 추가하기

데이터가 하나 추가되면 front는 변함없고, rear의 값이 늘어난다.

front=0 rear=0 => front=0, rear=1

 

원형 큐에 데이터 삭제하기

데이터가 하나 삭제되면 front가 하나 추가되고, rear의 값은 변함없다.

front=0, rear=3 => front=1, rear=3

 

원형 큐에 데이터가 최대로 저장된 경우

이 경우는 front와 rear의 인덱스 차이가 한 칸만큼 날때이다.

if(남은 한칸에 데이터를 저장) { rear === front}

하지만 front === rear 일경우, 원형 큐가 비어 있는 것으로 간주하기 때문에 빈건지 찬건지 구분이 불가능해진다.

※나머지 연산자(%) 활용하기: 데이터 추가, 삭제
max_len = 8 일때, 데이터 세개를 빼고 하나를 추가하는 상황이라면?
front = 0, rear = 7 => front = 3, rear = 7 => ??
rear = (rear+1) % max_len;

데이터의 개수를 구하는 방법

front < rear 일 때

count = rear - front;

front > rear 일 때

count = (rear - front) + MAX_LEN;

모든 상황을 만족 시킬 수 있는 수식

count = ((rear - front + 1) + MAX_LEN) % MAX_LEN;