학습 일자 : 2023.
큐는 FIFO (First In First Out, 선입선출) 형식이기 때문에 앞에서부터 데이터가 빠져 나감.
입력된 순서대로 처리해야 하는 상황에 이용
→ 은행 업무, 작업 대기 열
큐의 문제점
큐는 FIFO이기 때문에 데이터를 꺼낼 때 배열의 앞에서부터 데이터를 꺼내 줘야 함 (리스트도 배열임. 동적배열)
선입 선출로 데이터가 빠져 나가고 나면, 앞 부분은 비어 있기 되는 메모리 낭비 현상이 발생할 수 있음
⇒ 배열의 앞에서 값을 꺼낼 때 마다 데이터를 하나씩 앞으로 옮겨주면 메모리를 낭비하지 않을 수 있음.
BUT, 매번 배열은 순회하면서 데이터를 옮겨 줘야 하기 때문에 매우 비효율적임. → 큐의 삭제는 O(n)임. (스택은 뒤에서 꺼내기 때문에 O(1)임)
그렇다면, 삭제할 때 앞으로 땡기지 않아도 되는 자료 구조인 LinkedList를 사용하면 되지 않은가?
→ 실제로 C++은 LinkedList로 구현되어 있지만, C#에서 LinkedList는 node가 생성 되었다 삭제 될 때 마다 GC(Garbage Collection)이 node를 처리해야 하다 보니 C#에서는 LinkedList를 잘 안 씀.
(큐도 linkedlist로 구현하지 않음.)
하지만, 큐를 LinkedList처럼 작동하도록 직접 구현해서 사용하는 것은 가능함.
(어덥터 패턴을 활용하여 큐를 만들 수 없음)
→ 무조건 어덥터 패턴으로 만든다고 좋은 것만은 아님! 이미 만들어진 기능과 거의 유사할 때 사용하는 것이 적절함 (ex. stack과 list : 스택은 리스트의 기능과 거의 유사하기 때문에 리스트 활용해서 어뎁터 스택으로 재탄생이 가능한 것! )
⇒ 시작과 끝을 붙여서 원형으로 만들면, 앞 부분을 다시 사용할 수 있게 됨.
[환형 큐의 기본 구조]
큐의 overflower
큐에 데이터가 아무것도 없을 때도 head와 tail의 위치가 동일하고, 꽉 찼을 때도 head와 tail의 위치가 동일함.
⇒ 2개를 구별할 수 없음.
마지막 방은 비워 둬서 head와 tail의 위치가 하나 차이 나면 꽉 찬거고, 같은 위치에 있으면 비어 있다고 판단하도록 함.