비실이의 개발 성장기

[자료구조] Queue 본문

Study memo

[자료구조] Queue

DubbingLee 2018. 6. 1. 13:56



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
PaaS, SaaS, IaaS 란?  (0) 2017.06.06
1 Comments
댓글쓰기 폼