[자료구조] 큐 (Queue)

선형 자료구조에는 앞서 정리했던 배열, 연결 리스트, 스택 그리고 큐가 있다.
이번에는 큐(Queue)에 대해 정리해보자.

큐

큐는 스택과 비슷하지만 조금은 다르다. 스택은 위에서부터 수직으로 쌓는 느낌이였다면, 큐는 수평으로 넣는 느낌이다.
즉, LILO(Last in Last out), FIFO(First in First out)의 순서를 따라간다.

---

특징

1. 데이터를 받는 순서대로 정렬해서 저장한다.
2. 가장 앞부분을 Front / Head, 뒷부분을 Rear / Tail라고 한다.
3. 한쪽 끝에서는 삽입, 다른 한쪽에서는 삭제만 수행한다.

---

시간복잡도

1. 접근(Access) : 들어간 순서에 따라서 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다.
2. 삽입(insert) 및 삭제(delete) : 앞쪽에 삽입하거나 먼저 들어갔었던 데이터를 삭제할 수 밖에 없기 때문에 O(1)의 시간 복잡도가 발생한다.
3. 검색(search) : 접근과 마찬가지로 O(n)의 시간 복잡도가 발생한다.

---

큐의 구현

큐는 스택과 마찬가지로 배열을 사용하거나, 연결 리스트를 사용해서 구현할 수 있다.


1. 배열 : 구현하기 쉽다. 정적인 크기를 갖는다.
2. 연결리스트 : 크기가 동적이지만, 포인터를 위해 추가 메모리 공간이 필요하다.