Queue
큐(queue)란?
선입선출 (First In First Out)의 구조를 가지는 자료구조
-> 시간 순서상 먼저 들어간 데이터가 먼저 나오는 자료구조이다.
활용 예시: 캐시(cache) 구현, 프로세스 관리, BFS등
enqueue
queue에서 데이터를 추가하는 것
queue의 맨 뒤에 데이터를 추가하면 완료되기 때문에 O(1) 의 시간복잡도를 가짐
dequeue
queue에서 데이터를 추출하는 것
queue의 맨 앞에 데이터를 삭제하면 완료되기 때문에 O(1) 의 시간복잡도를 가짐
구현
Array-based-queue
배열을 기반으로 구현된 큐 자료구조로 큐는 FIFO(First In First Out)의 원칙에 따라 동작하며, 배열 기반 큐는 큐의 시작과 끝을 배열의 처음과 끝으로 설정하여 구현된다.
어레이 기반 큐에서는 큐의 요소를 배열에 저장한다. 요소를 추가할 때는 배열의 끝에 새로운 요소를 추가하고, 요소를 제거할 때는 배열의 맨 앞 요소를 제거한다. 이렇게 하면 첫 번째 요소가 항상 가장 오래된 요소가 되어 FIFO 순서를 유지할 수 있다.
어레이 기반 큐는 요소를 추가하거나 제거할 때 배열의 요소를 이동할 필요가 없기 때문에 연결 리스트를 기반으로 하는 List-based queue에 비해 더 빠른 접근 시간을 가진다. 또한 메모리 할당 및 해제에 따른 Overhead가 없어 메모리 관리 측면에서 효율적이다 하지만 크기가 고정되어 있어 동적으로 크기를 조정하기 어렵다.
==> enqueue나 dequeue 과정에서 남는 메모리가 생기기 때문에 메모리 낭비를 줄이기 위해 주로
circular queue형식으로 구현한다.
Linked List-based queue
각 노드가 데이터 요소와 다음 노드를 가리키는 포인터로 구성된다. 큐에 요소를 추가할 때는 리스트의 끝에 새로운 노드를 추가하고, 요소를 제거할 때는 리스트의 맨 앞에서 노드를 제거한다. 이렇게 하면 첫 번째 요소가 항상 가장 오래된 요소가 되어 FIFO 순서를 유지할 수 있다.
동적으로 크기가 조정될 수 있기 때문에 크기를 미리 지정할 필요가 없다. 그러나 요소를 추가하거나 제거할 때마다 메모리 할당 및 해제 작업이 수행되므로, 성능 면에서는 배열 기반 큐에 비해 Overhead가 발생
==> 재할당이나 메모리 낭비의 걱정을 할 필요가 없어진다.
⭐️Q. Array-Base 와 List-Base의 차이
🔥 Array-Base의 경우 큐는 circular queue 로 구현하는 것이 일반적인데 이는 메모리를 효율적으로 사용하기 위함이다. 또 enqueue가 계속 발생하면 고정된 size를 넘어서기 때문에 dynamic array같은 방법으로 배열의 크기를 확장시켜야한다. 그럼에도 enqueue의 시간 복잡도는 O(1)을 유지할 수 있다.
🔥 List-Base의 경우 보통 단일 연결 리스트로 구현한다. enqueue는 단순히 단일 연결 리스트에서 append 하는 것으로 구현되고 이때의 시간복잡도는 O(1)이다. dequeue는 맨 앞 원소를 삭제하고 first head를 변경하기 때문에 O(1)의 시간이 걸린다.
요약
두가지 종류의 자료구조로 큐를 구현하더라고 enqueue와 dequeue는 모두 O(1)의 시간 복잡도를 가진다. Array-Based의 경우 전반적인 수행이 좋지만 worst case 의 경우 resize에 의해 더 느릴 수 있다. List-Base의 경우 enqueue를 할 때 마다 메모리 할당을 해야하기 때문에 전반적 런타임이 느릴 수 있다.
Circular queue (원형 큐)
배열 기반의 큐 자료구조로, 선형 큐(Linear Queue)의 문제점을 보완하기 위해 도입되었다. 선형 큐는 배열의 끝에 도달하면 더 이상 요소를 추가할 수 없기에 이러한 문제를 해결하기 위해 원형 큐는 배열의 처음과 끝이 연결되어 있는 구조를 가진다.
일반적으로, 원형 큐는 배열의 특정 위치를 'front'와 'rear' 포인터로 사용하여 큐의 시작과 끝을 나타낸다. 큐에 요소를 추가할 때 rear 포인터를 이동시켜서 새로운 요소를 추가하고, 요소를 제거할 때는 front 포인터를 이동시켜서 가장 오래된 요소를 제거한다. 이렇게 하면 배열의 처음과 끝이 연결되어 있기 때문에 배열의 끝에 도달하면 dequeue()로 발생한 빈 공간에 요소를 추가할 수 있다. 즉, 큐의 요소가 가득차 있어도 첫 인덱스 부터 다시 삽입 가능!
원형 큐의 구현은 front와 rear 포인터를 갱신하는 논리적 연산에 주의해야 하는데 예를 들어, rear 포인터가 배열의 끝에 도달하면 다음 요소를 배열의 처음에 추가해야 하며, front 포인터가 배열의 끝에 도달하면 다음 요소를 배열의 처음으로 이동해야 한다.
원형 큐는 배열의 재활용을 통해 메모리를 효율적으로 사용할 수 있으며, 큐의 요소를 순환적으로 처리할 수 있다.
우선순위 큐
우선순위 큐(Priority Queue)는 각 요소에 우선순위가 할당된 큐 자료구조로 일반적으로 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리되는 큐이다. 우선순위 큐는 일반적인 큐와 달리 요소를 삽입할 때마다 요소의 우선순위를 기준으로 정렬되거나, 우선순위가 가장 높은 요소가 항상 먼저 나오도록 구현된다.
응용 분야: 작업 스케줄링, 이벤트 처리, 그래프 알고리즘 등에서 주어진 우선순위에 따라 작업이나 이벤트를 처리할 때 활용
Q. ⭐️Queue와 priority Queue의 차이 비교
Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 구조로 저장하는 형식이다. 이와 달리 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.
시간 복잡도:
- Queue: enqueue->O(1), dequeue->O(1)
- priority queue: push->O(logn), pop-> O(logn)
**우선 순위 큐 구현 => Heap 을 이용해 이진완전트리 활용
heap
c++에서의 큐
- 큐 헤더파일
큐를 사용하기 위해서는 헤더파일 queue를 포함해야한다.
#include<queue>- 큐 생성
queue<int> q;
//int 자료형을 데이터로 하는 q 큐 생성- 큐 기본 함수
- 데이터 추가
.push
큐이름.push(데이터) 로 데이터 추가
q.push(2);- 데이터 삭제
.pop
큐이름.pop(데이터) 로 데이터 삭제
q.pop(2);- 첫번째 데이터 반환
.front
큐이름.front() 로 큐의 첫번째 데이터 반환
q.front();- 마지막 데이터 반환
.back
큐이름.back() 로 큐의 마지막 데이터 반환
q.back();- 큐 사이즈 반환
.size
큐이름.size() 로 큐의 현재 사이즈 반환
q.size();- 비었는지 확인
.empty
큐이름.empty() 로 큐가 비어있는지 확인
q.empty();- 두 큐의 내용 바꾸기
.swap
큐이름.swap() 로 큐의 내용을 서로 바꿔준다.
q.swap(queue1,queue2);