자료구조 (data structure) / 큐 queue 정리

큐 (Queue) 

오늘은 자료구조 중 queue, 큐에 대해 정리를 해보려고 한다

 

퀄리티는 별로지만 설명을 위해 직접 그린 자료를 첨부한다.

queue는 First in First out, FIFO구조로 데이터를 저장한다.

enqueue : 자료의 마지막에 데이터를 추가한다.

dequeue : 자료의 첫번째 데이터를 삭제한다.

 

queue를 간단하게 설명하자면, 놀이공원에서 기구를 타기 위한 줄을 예로 들 수 있을 것 같다.

기구를 타기 위해 줄을 선다고 가정하면, 뻔뻔한 사람이라 새치기를 할 배짱이 있는 게 아니라면 당연하게 현재 줄의 맨 뒤로 가야만 할 것이다.

그리고 그 줄의 제일 앞에 있는 사람이 놀이기구를 타기 위해 가장 먼저 줄에서 탈출 할 수 있는 사람이다.

큐에 대한 간략한 설명은 벌써 끝이 났다.

 

실생활 사용 예시

웹 브라우저에서 뒤로가기를 눌렀을 때 가장 나중에 열린 페이지부터 다시 보여준다던지, 실행취소 (undo)의 상황을 queue를 통해 이용하고 있다고 생각하면 쉬울 것이다.

 

시간 복잡도

자료 추가 : O(1)

자료 삭제 : O(1)

자료 검색 : O(n)

자료 추가 / 삭제는 각 데이터의 양 쪽 끝을 기준으로 추가와 삭제를 진행하기 때문에 O(1)의 시간복잡도만이 발생하게 되고, 자료 검색의 경우에는 자료를 찾기 위해 순회를 필수적으로 진행을 해야하기 때문에 O(n)의 시간 복잡도가 발생한다.