큐(Queue)

큐(Queue)

큐는 데이터의 제거는 가장 앞에서 수행되며, 데이터의 삽입은 가장 뒤에서 수행되는 제한된 리스트 구조

가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO- first in first out)형태의 자료구조이다.

가장 오래전에 입력된 데이터를 front라고 하며

가장 최근에 입력된 데이터를 rear라고 한다.

삭제는 front에서 이루어지고

삽입은 rear에서 이루어 진다.

삽입 - insert

: 리스트 끝 부분을 가리키는 rear에서 발생하며

데이터가 삽입 될때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

삭제(추출) - remove

: front가 가리키고 있는 데이터를 꺼낸 후 front값을 하나 증가 시키도록 구현한다.

front값이 rear를 추월하게 되면 더 이상 제거할 데이터가 없는 상태

즉 자료가 하나도 없는 상태

읽기 - peek

큐에서 front가 가리키는 데이터를 읽는 작업

배열을 이용한 큐 구현

배열을 이용하여 큐를 구현할때의 단점은

그 크기가 고정되어있다는 점과

데이터의 삽입과 삭제가 반복 될수록 rear와 front가 계속 증가되므로 이미 꺼낸 데이터가 들어있던 배열의 인덱스를 다시 활용할수없다.

연결리스트를 이용한 큐

데이터가 저장될 큐의 크기를 미리 지정하지 않아도 되며

front보다 작은 인덱스공간(삭제한공간)을 낭비하지 않아도 된다.

원형 큐(Circular Queue)

: 큐의 맨끝과 맨처음이 연결된 형태의 구조

우선순위큐

: 데이터의 우선순위에 따라 우선순위가 높은 데이터부터 꺼내도록 만들어진 큐

덱

리스트의 양쪽 끝 모두에서 데이터를 삽입,삭제할 수 있도록 만들어진 특별한 형태의 자료구조