자료구조(5)_Queue

Queue ?

- 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out ) 구조로 저장하는 형식의 자료구조이다. 

- 예를들어 , 놀이공원에 티켓을 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며 먼저 줄을 선 사람이 티켓을 먼저 사서 나가는 그림을 생각하면 된다. 

- 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다 (스택은 LIFO 구조)

- 프린터의 출력 처리나 윈도우 시스템의 메시지 처리, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용된다. 

- 큐는 put (insert) 와 get (delete)을 이용하여 구현된다. pust은 큐에 자료를 넣는 것, get은 큐에서 자료를 꺼내는 것을 의미한다. 

Queue의 구조

*Enqueue() : 데이터를 입력하는 함수

*Dequeue() : 데이터를 출력하는 함수

 

- Front (head) 와 rear (tail)는 데이터의 위치를 가리킨다 Front는 데이터를 get할 수 있는 위치를 가리키고, rear는 데이터를 put할 수 있는 위치를 의미한다. 또 , 큐가 꽉 차서 더이상 데이터를 넣을 수 없을 경우를 오버플로우 ( Overflow)라 하고 , 큐가 비어 있어 자료를 꺼낼 수 없을 경우를 언더플로우(Underflow)라고 한다. 

 

큐의 종류

- 선형 큐 : 막대 모양으로 된 큐이다. 크기가 제한되어 있고 사용하려면 모든 데이터를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 존재한다. 

데이터 : A B C D

- 환형 큐 : 선형 큐의 문제점을 보완한 것이 환형 큐이다. Front가 큐 끝에 닿으면 큐의 맨 앞으로 자료를 보내 원형으로 연결하는 방식이다. 

데이터 : A B C D E

- 링크드 큐 : 연결 리스트로 구현한 큐는 연결 리스트를 사용한 것으로 , 큐의 길이를 쉽게 늘릴 수 있어서 오버플로우가 발생하지 않는 것이 특징이다. 필요에 따라 환형으로 만들 수 있고 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.