Linear Queue 선형 큐

Linear Queue 선형 큐란?

- FIFO(First In First Out) 구조, 선입선출, 선형 데이터 구조

- 데이터를 받는 순서대로 저장하고 받은 순서대로 출력

- 배열, 연결리스트로 구현하는 방법 존재

- c++ STL에서 #include<queue> 추가하여 사용가능

 

시간 복잡도

삽입, 삭제의 시간 복잡도는 O(1)

 

장점

- 데이터 접근, 삽입, 삭제가 빠르다.

 

단점

- 스택의 앞쪽에만 접근 가능, 탐색 불가능

- front와 rear이 증가되는 방식으로 front 앞의 공간이 있어도 삽입 불가 (원형큐로 해결가능) 

 

사용

- BFS 알고리즘

- 순서대로 처리하는 작업이 필요할 때

 

front == 큐의 앞쪽 (데이터가 없다)

rear == 큐의 뒤쪽 (마지막에 들어온 데이터)

삽입된 순서 : A -> B -> C -> D

출력시 순서 : A -> B -> C -> D