큐 개념
큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조로 나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념이다.
실제 예로 매표소 대기열에서 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황과 비슷하다.
큐는 FIFO(First In First Out) / LILO(Last In Last Out) 순서를 따른다.
FIFO : 처음 들어온 값이 처음에 나가는 것
LILO : 마지막에 들어온 값이 마지막에 나가는 것
큐에 끝에서 요소를 추가하는 작업을 enqueue라고 하며 큐에 맨 앞에서 요소를 제거하는 작업을 dequeue라고 한다.
가득 찬 큐에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생한다.
기본 동작
- enqueue() : 큐에 끝(rear)에 항목을 추가
- dequeue() : 큐에 맨 앞(front)에 항목을 제거
- peek() : 큐에 맨 앞(front)에 있는 항목을 반환
- isfull() : 큐가 가득 찼는지 확인
- isempty() : 큐가 비어 있는지 확인.
시간 복잡도 (Time complexity)
| Operation | Average | Worst | |
|---|---|---|---|
| Access | |||
| Search | |||
| Insert(enqueue) | |||
| Delete(dequeue) |
큐를 구현하는 두가지 방법
1. Array 사용
- 장점 : 구현하기 쉬움.
- 단점 : 크기가 동적이 아님. 런타임 시 필요에 따라 늘어나거나 줄어들지 않음.
2. Linked List 사용
- 장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음.
- 단점 : 포인터를 위한 추가 메모리 공간이 필요함.
큐의 종류
선형 큐 (Linear Queue)
기본적인 큐의 형태로써 막대 모양으로 된 큐이다.
배열로 구현 시 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있고 많은 수의 enqueue 및 dequeue 작업이 있는 경우 어느 시점에서 큐가 비어있어도 자료를 삽입하지 못하는 경우가 발생한다.
환형 큐 (Circular Queue)
선형 큐의 문제점을 보완한 것이 환형 큐이다.
환형 큐는 1차원 배열 형태의 큐를 원형(Circular)으로 구성하여 배열의 처음과 끝을 연결하여 만든다.
원형 큐라고도 한다.
큐의 사용 사례
- 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.
ex) CPU 스케줄링, 디스크 스케줄링 - 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용한다. (비동기 전송)
ex) I/O 버퍼, 파이프, 파일 I/O
구현
array 이용
#include<iostream>
using namespace std;
template <typename T>
class queue {
private:
T* arr; //큐 원소 넣는 배열
int q_size; //큐의 사이즈
int frontCursor; //큐의 front가리키는 커서
int rearCursor; //큐의 back가리키는 커서
public:
queue() { //초기화
q_size = 0;
arr = new T[10'000];
frontCursor = 5'000;
rearCursor = 5'000;
}
~queue() {
delete[] arr;
}
void push(T elem){ //원소 넣기
arr[rearCursor] = elem;
rearCursor++;
q_size++;
}
void pop(T elem){ //원소 빼기
if (q_size!=0) { //비어있지 않을 때
arr[frontCursor] = 0;
frontCursor++;
q_size--;
}
else {
cout << "큐가 비어있습니다." << '\n';
}
}
T front(){ //큐의 제일 앞 값(먼저 빠짐)
return arr[frontCursor];
}
T back(){ //큐의 제일 뒷 값
return arr[rearCursor-1];
}
bool empty(){ //큐가 비어있는지 여부
if (q_size==0)
return true;
else return false;
}
int size(){ //큐의 크기
return q_size;
}
};Linked List 이용
#include<iostream>
using namespace std;
template <typename T>
struct Node {
T data;
Node* prev;
Node* next;
};
template <typename T>
class queue {
private:
int q_size; //큐의 사이즈
Node<T>* head; //큐의 앞부분 가리키는 노드포인터
Node<T>* tail; //큐의 뒷 노드 가리키는 노드포인터
public:
//생성자
queue() {
q_size = 0;
Node<T>* tmpHead = new Node<T>;
Node<T>* tmpTail = new Node<T>;
tmpHead->data = T();
tmpTail->data = T();
tmpHead->next = tmpTail;
tmpHead->prev = tmpHead;
tmpTail->next = tmpTail;
tmpTail->prev = tmpHead;
head = tmpHead;
tail = tmpTail;
}
//소멸자
~queue() {
Node<T>* tmp = head;
Node<T>* delNode = tmp;
while (tmp != tail) {
delNode = tmp;
tmp = tmp->next;
delete delNode;
}
//반복문빠져나왔다면 tmp는 tail노드이므로
delete tmp;
}
//원소 넣기
void push(T elem) {
//새로운 노드 생성
Node<T>* newNode = new Node<T>;
newNode->data = elem;
//연결작업
newNode->next = tail;
newNode->prev = tail->prev;
tail->prev->next = newNode;
tail->prev = newNode;
q_size++;
}
void pop() { //원소 빼기
if (!empty()) { //비어있지 않을 때
Node<T>* delNode = head->next;
delNode->next->prev = head;
head->next = delNode->next;
delete delNode;
q_size--;
}
else {
cout << "큐가 비어있습니다." << '\n';
}
}
T front() { //큐의 제일 앞 값(먼저 빠짐)
return head->next->data;
}
T back() { //큐의 제일 뒷 값
return tail->prev->data;
}
bool empty() { //큐가 비어있는지 여부
if (q_size == 0)
return true;
else return false;
}
int size() { //큐의 크기
return q_size;
}
};
강승구