🤓오늘의 공부 주제: Queue🤓
Q. Queue는 무슨 자료구조 인가?
A. queue는 선입선출 FIFO(First In First Out)의 자료구조
시간복잡도는 enqueue , dequeue 입니다. 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등
queue에서 데이터를 추가하는 것을 enqueue
queue에서 데이터를 추출 하는 것은 dequeue
enqueue의 경우 queue의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1). 이와 비슷하게 dequeue의 경우 맨 앞의 데이터를 삭제하면 완료 되기 때문에 동일하게 O(1)의 시간복잡도.
🔑key point!
Queue의 두가지 구현 방식
1) Array-Based queue
enqueue와 dequeue 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현
2) List-Based
재할당이나 메모리 낭비의 걱정을 할 필요가 없음
Q. 원형큐(circular queue)는 무슨 자료구조 인가?
A. 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조. 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없음. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능
Q. Array-Base 와 List-Base의 경우 어떤 차이가 있나?
두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖는다. Array-Base의 경우 전반적으로 성능이 더 좋지만, 최악의 경우에는 리사이즈로 인해 훨씬 더 느릴 수 있음. List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있음.
Array-Base의 경우 메모리의 효율을 위해 queue는 circular queue로 구현하는 것이 일반적이라고 한다. 또한, enqueue가 계속 발생하면 고정된 사이즈를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 하는 불편함이 있다. 그럼에도 enqueue의 시간복잡도는 (amortized)O(1)를 유지한다.
List-Base의 경우 보통 singly-linked list로 구현을 한다. enqueue는 단순히 singly-linked list에서 append를 하는 것으로 구현되고, 이 때 시간복잡도는 O(1)이다. dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에 이 연산도 O(1)의 시간이 걸린다.
출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]
