🧩 Queue

queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조.

📌 Enqueue

queue 에 데이터를 입력하는 작업을 enqueue라고 한다.
enqueue의 경우 맨 뒤에 데이터를 추가하기 때문에 시간복잡도는 O(1)이다.

📌 Dequeue

queue 에 데이터를 추출하는 작업을 dequeue라고 한다.
Dequeue의 경우 맨 앞의 데이터를 추출하기 때문에 시간복잡도는 O(1)이다

📌 Array-Based queue

queue 의 구현방식에 대해서는 두가지가 존재한다.

queue를 Array 자료구조를 활용해서 구현한 형태 이다.

enqueue와 dequeue의 과정에서 남는 메모리가 발생한다.
위의 그림 처럼 dequeue를 한다면 0, 1 index는 메모리 낭비로 직결 될 것이다.

만약 dequeue의 연속 발생으로 7번 index의 데이터만 존재 한다고 가정 해보자.
이때 enqueue가 발생한다면 데이터는 8, 9번 index에만 저장 될 것이다.

즉 0 ~ 6번 까지의 index는 접근 할 수 없거나 dequeue가 발생 할 때마다 데이터를 앞으로 당겨 줘야 하며 데이터를 당길 때 마다 시간복잡도 역시 증가 할 것이다.

📌 circular queue

위와 같은 낭비를 줄이기 위해 고안된 circular queue이다.
논리적으로 원형으로 보여지기에 circular queue이지 물리적으로 원형을 띄고 있지는 않는다.

만약 Enqueue가 계속 발생하여 배열의 끝까지 데이터가 차버린다고 가정해보자.

이때 배열을 확장하는 것이 아니라 front index전 까지 rear포인터를 이동 시킨다.

이렇게 queue를 설계하면 처음과 끝이 이어져 있는 형태 처럼 보여지게 된다.

메모리를 낭비하지 않기 위해 circular queue를 구현 했지만 Array자료구조의 특성 상 모든 배열이 가득차게 된다면 더이상의 데이터 삽입이 불가능 하다.

해당 배열 공간을 늘려주기 위해 Dynamic Array를 활용하는 것이 좋은 방법이 될 수 있다.

📌 List-Based queue

queue를 Linked List 자료구조를 활용해서 구현한 형태 이다.

enqueue 는 단순히 node를 append하는 것으로 구현이 되고 dequeue는 맨 앞의 node를 삭제 한 후 First head를 뒤로 한건 밀어준다.
이때 enquueu와 dequeue의 시간복잡도는 O(1)이다.

List queue는 enqueue시 메모리 동적할당이 발생하고 dequeue시에 할당 해제된다.
이때 시간 소요가 있기 때문에 전반적인 runtime이 느려질 수 있다.

🤔 종합

List를 구현하는 자료구조 형태에 따라서 리스트의 형태가 달라지는 것을 확인해 볼 수 있었다.

전반적인 performance는 Array-Based list가 memory 공간으로 인한 resize가 발생할 때마다 O(n)의 시간복잡도가 발생하기 때문에 특정 부분에서는 훨씬 느린 성능을 보여줄 것이다.

List-Based queue 역시 동적 할당 및 할당 해제 작업이 발생하기 때문에 Array와 Linked의 장점을 상황에 맞게 활용해서 구현하자.

다음 글은 stack에 대해서 간단하게 정리 해보고 queue와 비교해 보겠다.

당시 가지고 있던 기술 개념으로 작성된 글 이므로 정확하지 않을 수 있으며 문제가 발견 된다면 수정 하겠습니다.