[자료구조] Queue

Queue 란?

영어 단어 queue는 `차례를 기다리는 사람이나 승용차의 열` 이라는 뜻을 가지고 있다.

자료구조에서의 Queue도 데이터를 순서대로 저장 공간에 넣은 뒤, 넣은 순서대로 데이터를

꺼내어 사용하는 방식을 말한다.

자료구조의 Stack 이 `가장 마지막에 저장한 데이터가 가장 먼저 처리되는 방식 (LIFO)` 이라면,

Queue 는 `가장 처음 저장한 데이터가 가장 먼저 처리되는 선입선출 방식 (FIFO)` 를 가진다.

Queue 에는 공간에 들어있는 데이터 중, 첫번째 데이터를 가리키는 `Front` 와 가장 마지막 데이터를 가리키는 `Rear` 두개가 존재한다.

Queue 에 데이터를 삽입하는 동작을 `Enqueue`, 삭제하는 동작을 `Dequeue` 라고 부른다.

Queue 의 종류 

Queue 종류는 선형 과 환형 방식이 존재한다.

선형 Queue

<5개의 공간을 가진 선형 Queue>

위 그림에서 데이터 삭제 명령을 하면 Front가 가리키고 있는 '바나나' 가 삭제되며, Front는 그 다음에 있는 '사과' 를 가리키게 된다.

선형 Queue 에 새로운 데이터 두개를 삽입하면 아래와 같이 Rear 위치가 바뀌게 된다.

위 그림을 보면 Rear 는 선형 Queue 의 가장 마지막 공간을 가리키고 있다. 

이 상태에서 데이터 삽입 명령을 하게 되면 선형 Queue 의 가장 왼쪽에 빈 공간이 있음에도 불구하고 Overflow 가 발생하게 된다.

새로운 데이터를 추가하기 위해서는 선형 Queue 에 있는 모든 데이터를 왼쪽으로 한칸씩 이동시켜야 하는 단점이 있다.

'Study memo' 카테고리의 다른 글

[자료구조] Queue  (1)	2018.06.01
[자료구조] 선형 리스트 - 2  (0)	2018.05.19
[자료구조] 선형 리스트 - 1  (0)	2018.05.12