선형 구조 - Queue

Queue

- 톨게이트를 Queue 자료 구조, 자동차는 데이터(data)로 비유

- 먼저 진입한 자동차가 가장 먼저 톨게이트를 통화하는 것처럼 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지 톨레이트를 빠져  나갈 수 없다

 

 

Queue의 구조

- Stack과 반대되는 개념으로 먼저 들어간 데이터가 먼자 나오는 FIFO(First In First Out) 혹은  LILO(Last In Last Out)의 특징;선입선출

- 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 구조

- 입력과 출력의 방향이 고정되어 있으며 두 곳으로 접근이 가능

- Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 함

- 데이터가 입력된 순서대로 처리 될 때 주료 사용

 

 

Queue의 특징

1. FIFO(First In First Out)

- 먼저 들어간 데이터가 가장 제일 처음 나오는 선입선출의 구조를 가지고 있음

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

						queue.enqueue(데이터)
출력 방향 <---------------------------< 입력 방향
				     1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

						queue.dequeue(데이터)
출력 방향 <---------------------------< 입력 방향

				<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

 

2. 데이터는 하나씩 넣고 뺄 수 있음

- Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고 뺌

- 한꺼번에 여러 개를 넣거나 뺄 수 없음

 

3. 두 개의 입출력 방향을 가지고 있음

- Queue 자료구조는 데이터의 입력, 출력 방향이 다름

- 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없음

 

 

Queue의 실사용 예제

컴퓨터와 연결된 프린터로 여러 문서를 순서대로 인쇄할 때

- 1 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업(임시 기억 장치)의 Queue에 들어감

- 2 프린터는 인쇄 작업  Queue에 들어온 문서를 순서대로 인쇄함

 

- 위 예시처럼 컴퓨터 장치들 사이에서 데이터를 주고 받을 때 각 장치 사이에 존재하는 속도 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용

- 이것을 통틀어 버퍼(Buffer)라고 함

 

- 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생함

- 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖음

- 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용

 

컴퓨터와 프린터 사이의 데이터 통신 정리

- 일반적으로 프린터는 속도가 느림

- CPU는 프린터와 비교하여 데이터를 처리하는 속도가 빠름

- 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업 수행

-  프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄

 

유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때 다운로드 된 데이터가 영샹을 재생하기 충분하지 않은 경우, 동영상을 정상적으로 재생하기 위해  Queue에 모아 두었다가 동영상을 재생하기 충분한 양의 데이터가 모였을 때 동영상 재생