[바킹독의 실전 알고리즘] 0x06강 - 큐

 

정의와 성질

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다.

스택에서는 먼저 들어간 원소가 나중에 나왔는데, 큐에서는 먼저 들어간 원소가 먼저 나오게 된다.

스택을 FILO(First In Last Out)라고 한 것과 비슷하게 큐를 FIFO(First In First Out)라고 하기도 한다.

 

큐의 성질

• 원소 추가/제거의 시간 복잡도는 O(1)이다.
• 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다.
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다.

 

기능과 구현

배열 형태로 선형 큐를 구현해 보았다.

 

STL queue

큐가 비어있을 때 front, back, pop을 호출하면 런타임 에러가 발생할 수 있으므로 주의해야 한다.

 

 

출처: 바킹독님 블로그