알고리즘 기초 02) 큐 (Queue) 자료 구조

개념

First In First Out (FIFO) 구조를 따르는 자료구조. 즉, 삽입하는 쪽과 삭제하는 쪽이 서로 반대에 위치 해 있다.

삽입하는 쪽 : rear   삭제하는 쪽 : front 라고 표현함.

 

삽입 연산을 enqueue, 삭제 연산을 dequeue라고 부름.

overflow : queue의 용량이 다 차서 더 이상 enqueue할 수 없는 상태

underflow : queue에 data가 없어서 dequeue할 data가 없는 상태

 

 

대표적인 사용처 : CPU scheduling, data buffer, 대기 행렬 정리, 인쇄 작업 대기 목록, 자원을 공유하는 대부분의 경우 등

 

단점 : 데이터 삽입 후 계속 항목을 삭제 하다보면, 어느 순간 rear pointer와 front pointer가 만나게 되어 empty queue가 됨에도 불구하고 overflow 현상이 발생하여 메모리 낭비가 발생할 수 있다.

 

연산

insert, enqueue, offer, push : queue의 rear에 새로운 요소를 추가한다.

remove, dequeue, poll, pop : queue의 front에 있는 요소를 queue에서 반환하고 삭제한다.

peek, element, front : queue의 front에 있는 요소를 queue에서 삭제하지 않고 반환한다.

IsEmpty : queue의 empty 여부를 출력한다.

 

구현

'구현'을 클릭하면 파이썬을 이용하여 간단히 구현한 queue를 볼 수 있다.