Queue

Queue의 정의

---

큐(Queue)는 줄을 서서 기다리다, 대기행렬이라는 뜻을 가지고 있다.

Queue의 구조

---

• 자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터가 먼저 나오는 FIFO 혹은 LILO을 특징으로 가지고 있다. 입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근이 가능하다.

• Queue에 데이터를 넣는 것을 enqueue, 데이터를 꺼내는 것을 dequeue라고 한다.

• 자료구조 Queue는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.

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의 예시

---

위 예시처럼 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 장치 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼라고 하며 아래 이미지는 버퍼링의 개념을 보여주고 있다.

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생한다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖고 있다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용한다.