#7 큐(Queue) - 개념(FIFO : First In First Out)

- 큐(Queue)도 Stack과 같이 단순한 규칙을 가지고 있는 리스트이다.

- 규칙 : FIFO(First In First Out)

- 즉, 먼저 들어간 데이터가 가장 먼저 나온다는 의미로서 먼저 들어간게 가장 나중에 나오는 Stack과는 반대의 개념이다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- Queue는 운영체제에서도 사용된다.

- 운영체제가 프로세스의 작업 요청을 들어온 순서대로 Queue에 넣고 이를 CPU가 순서대로 꺼내서 처리한다.

- 이를 운영체제에서는 FIFO 스케줄링이라고 한다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 일상생활에서 마트 계산대, 놀이공원 줄 등도 모두 Queue의 개념으로 볼 수 있다.

---

● 연결리스트로 Queue 구현하기

- 연결리스트의 맨 첫 번째 node를 head 라고 했을 때 숫자 1, 2, 3, 4 를 순서대로 연결리스트에 삽입하면 아래와 같다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 위와 같은 구조에서 숫자 1이 가장 먼저 나오려면(= 삭제하려면) 어디서부터 노드(데이터)를 제거해야 할까?

- 간단하다. FIFO 구조상 바로 뒤에서부터 데이터를 제거하면 된다.(이것이 Queue의 전부이다.)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

---

- 하지만 항상 말만 간단하지 이것을 구현하려면 여러가지 고려해야할 것이 많다.

- 연결리스트의 맨 첫 번째 node를 head 라고 했을 때 이 개념을 이용한 데이터 삽입은 매우 간단하다.

- 연결리스트의 가장 첫 번째에 원하는 데이터를 넣어주기만 하면 되기 때문이다.

- 즉, 현재의 연결리스트 개념은 앞의 노드가 바로 뒤의 노드를 가리키는 단방향 연결리스트인 것이다.

- 이러한 구조에서는 데이터를 뒤에서부터 제거하기가 힘들다.

 

why?

- 가장 뒤에있는 노드를 찾기 위해서는 가장 앞에있는 head 부터 시작해서 다음, 그 다음, 그 다음 다음.... 노드를 찾는 식으로 맨 뒤의 노드를 찾아야 하기 때문이다.

- 즉, 삽입은 O(1)이지만 삭제는 O(n)의 성능을 갖는 것이다.(너무 느리다.)

- 그렇다면 가장 마지막 노드(= 가장 먼저 들어간 데이터)의 위치를 담은 tail 변수를 추가하면 되지 않을까라는 해법을 생각해볼 수 있다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 그러나 이것도 문제가 된다.

- tail을 이용해 마지막 노드를 삭제한 후 이번에는 마지막 노드 바로 전에 있던 노드를 삭제하고 싶은 경우 이 역시 해당 노드를 찾을 방법이 없기에 위와 동일하게 head 부터 시작해서 다음, 그 다음, 그 다음 다음.... 노드를 찾는 식으로 원하는 노드를 찾아나가야 하기 때문이다.

- 즉, 최초 삭제를 제외하고 동일하게 삽입은 O(1), 삭제는 O(n)의 성능을 갖는 것이다.

- 따라서 현재 노드가 다음 노드 뿐만이 아니라 이전 노드도 가리킬 수 있는 이중 연결리스트로 만들어야 이러한 문제점들을 보완할 수 있다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 이중 연결리스트를 이용해 이전 노드를 참조할 수 있다면 tail 변수를 이용해 현재 노드를 제거한 후 그 이전 노드의 위치를 tail에 새로 할당할 수 있다.

 

※ 정리 : Queue는 연결리스트를 이용해 간단히 구현할 수 있다. 단, 단방향이 아닌 양방향 연결리스트가 필요하다.