[자료구조] 큐

오늘은 큐에 대해 배웠던 내용들을 정리해보려고 한다.

 

큐?

큐는 선입선출(FIFO) 방식을 따르는 자료구조이다. / First In First Out

즉 처음 들어온 데이터가 제일 먼저 나가게 된다.

스택에 PUSH 와 POP 이 있다면 큐에는 Enqueue 와 Dequeue 가 있다.

 

큐의 대표적인 메소드

Java 에서는 기본적으로 Queue 를 제공해준다. 

같이 제공되는 메소드들을 정리해보았다.

 

add()	큐에 데이터를 추가 / 실패 시 예외오류 발생
offer()	큐에 데이터를 추가 / 실패 시 false 리턴
remove()	큐에서 데이터를 삭제 / 실패 시 예외오류 발생
poll()	큐에서 데이터를 삭제 / 해당 값을 리턴 없으면 Null 리턴
clear()	큐의 모든 값들을 제거
peek()	큐에서 가장 먼저 들어간 값을 리턴
isEmpty()	큐가 비었는지 확인한 값을 리턴
size()	큐의 크기를 리턴

 

 

큐의 종류

크게 Linked Queue 와 순환 큐 가 있다.

 

링크드 큐의 경우 일반적인 큐를 의미한다.

순환 큐는 어떻게 보면 순환연결리스트 와 비슷하다.

 

큐는 기본적으로 Front 와 Rear 값을 각각 가지고 있다. 

따라서 값이 추가 삭제 되는 경우에는 해당 값들이 변경되어 인덱스를 알려준다.

 

 

이런 상황에서 6이라는 데이터가 삽입이 된다면

 

이렇게 Rear 값이 6을 가리키게 된다.

반대로 큐에서 데이터 하나가 삭제가 된다면

 

 

선입선출이므로 가장 앞에 들어온 값이 삭제 되므로 1이 삭제되었고

Front 값은 다음 값인 2를 가리키게 된다.

 

그렇다면 순환연결리스트 처럼 시작과 끝을 연결하면 어떻게 될까

그러한 형식의 큐를 순환형 큐 혹은 원형 큐라고 부른다.

 

 

일반적으로 큐가 포화 상태가 아니면 Front 값과 Rear 값은 같은 위치를 가리키게 된다.

그러나 포화 상태가 되면 Rear 값은 Front 값 - 1 의 값을 가지게 된다.

 

순환큐는 보통 미리 크기를 정해두고 사용해야 하는 경우에 사용하게 된다.