![[C++] 큐 직접 구현해보기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbiC7GX%2Fbtr9Nh6YIwM%2FtaAmcVkybvS4mzDEs4g7jk%2Fimg.png)
큐(Queue)란?
큐도 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다.
가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO : First In First Out)의 구조를 가지고 있다.
많은 예시로 은행의 대기열을 예시로 든다.
나같은 경우는 큐를 알림시스템에 사용해서 들어온 순서대로 알림이 출력되게 하거나,
들어온 순서대로 오브젝트를 재사용하는 오브젝트 풀링을 구현할때 사용했던 자료구조다.
[Queue.h - 선언]
#pragma once
class Queue
{
private:
int myQueue[1000] = { 0, };
int num = 0; //큐에 담긴 값의 갯수
int* firstNum = nullptr; // 첫번째 값의 포인터
public:
Queue();
void Init();
void EnQueue(int value);
int DeQueue();
bool IsEmpty();
void Clear();
int Count();
};
[Queue.cpp - 정의]
#include "Queue.h"
Queue::Queue()
{
Init();
}
void Queue::Init()
{
firstNum = &myQueue[0];
}
void Queue::EnQueue(int value)
{
myQueue[num++] = value;
}
int Queue::DeQueue()
{
if (IsEmpty())
{
return -1;
}
int value = *firstNum;
for (int i = 0; i < num-1; i++)
{
myQueue[i] = myQueue[i + 1];
}
num--;
return value;
}
bool Queue::IsEmpty()
{
if (num == 0)
return true;
else
return false;
}
void Queue::Clear()
{
num = 0;
}
int Queue::Count()
{
return num;
}
스택을 구현할때와 비슷하게 기본적인 함수들을 구현했다.
생성자에서 Init 함수로 배열의 첫번째 요소의 주소를 포인터에 담아줬고,
Dequeue를해서 값을 꺼낼때는 요소를 한칸씩 앞으로 땡겨줬다.
이 작업은 큐에서 값을 꺼낼때마다 O(n)의 시간복잡도를 가지는 작업이기 때문에 효율적이지는 못하다.
[main]
#include <iostream>
#include "Queue.h"
using namespace std;
int main()
{
Queue queue;
cout << "비어있는지 체크(0 - false / 1 - true)" << endl;
cout << queue.IsEmpty() << endl;
queue.EnQueue(3);
queue.EnQueue(6);
queue.EnQueue(9);
cout << "\nEnqueue하고 비어있는지 체크(0 - false / 1 - true)" << endl;
cout << queue.IsEmpty() << endl;
cout << "\n제일 처음넣은 수 3" << endl;
cout << queue.DeQueue() << endl;
cout << "\n두번째 수 6" << endl;
cout << queue.DeQueue() << endl;
queue.Clear();
cout << "\n클리어하고 비어있는지 체크(0 - false / 1 - true) " << endl;
cout << queue.IsEmpty() << endl;
}
<링 버퍼> - Dequeue를 효율적으로 바꿔보기
현재 구현한 Dequeue 함수는 값을 꺼낼때마다 요소의 값을 한칸씩 땡겨주는 작업을 하기때문에 상당히 비효율적이다.
그래서 '링 버퍼' 자료구조를 사용해서 구조를 바꿔볼 수 있다.
링버퍼란?
배열의 처음이 끝과 연결되었다고 보는 자료구조
[Queue.h - 선언]
#include <iostream>
#pragma once
class Queue
{
private:
int myQueue[10] = { 0, };
int max = 10;
int front = 0;
int rear = 0;
int num = 0;
public:
Queue();
void Init();
void EnQueue(int value);
int DeQueue();
bool IsEmpty();
void Clear();
int Count();
bool IsFull();
};
큐의 맨 앞 front , 꼬리 rear 변수를 추가해주었다.
맨 앞과 꼬리가 잘 도는지 확인하기위해 배열의 수를 10개로 선언하고,
max라는 변수를 선언해서 배열의 최대 수인 10을 넣어주었다.
[Queue.cpp - 정의]
#include "Queue.h"
void Queue::EnQueue(int value)
{
if (IsFull())
{
std::cout << "큐가 꽉찼습니다!"<<std::endl;
return;
}
myQueue[rear++] = value;
num++;
if (rear == max)
rear = 0;
}
int Queue::DeQueue()
{
if (IsEmpty()) return -1;
int value = myQueue[front++];
num--;
if (front == max)
front = 0;
return value;
}
bool Queue::IsEmpty()
{
if (num == 0)
return true;
else
return false;
}
void Queue::Clear()
{
rear = front = num = 0;
}
int Queue::Count()
{
return num;
}
bool Queue::IsFull()
{
if (Count() == max)
return true;
else
return false;
}
[Enqueue (삽입)]
큐에 삽입할때는 맨 끝인 rear에 삽입하고 rear의 수를 1 증가 시켜주었다.
주의 할점은 rear의 인덱스가 최대 인덱스인 9를 넘어서면 0으로 바꿔주어야한다.
[Dequeue (꺼내기)]
큐에서 값을 꺼낼때는 맨 앞쪽인 front의 값을 빼주고 front를 1증가시켜 주었다.
여기서도 주의할점은 front의 인덱스가 최대 인덱스인 9를 넘어서면 0으로 바꿔주어야한다.
[Main]
#include <iostream>
#include "Queue.h"
using namespace std;
int main()
{
Queue queue;
for (int i = 0; i <= 10; i++)
{
queue.EnQueue(i);
}
cout << "\n현재 큐의 count\n";
cout << queue.Count() << endl << endl;
cout << "\n Dequeue 시작\n";
for (int i = 0; i <= 10; i++)
{
cout << queue.DeQueue() << endl;
}
}
일부러 반복을 max보다 많은 11번을 반복했는데, 큐가 꽉차서 삽입되지 않는다는 메세지가 잘 뜨는것을 알 수 있다.
front와 rear의 변수가 잘 순환하는지를 보기위해 반복문으로 위의 과정을 3번 실행해보았다.
깔끔하게 잘 순환하는것을 볼 수있다.
'프로그래밍 공부 > 자료구조&알고리즘 공부' 카테고리의 다른 글
[C++] 연결리스트 직접 구현해보기 (0) | 2023.04.18 |
---|---|
[C++] 스택 직접 구현해보기 (0) | 2023.04.12 |
버블정렬 알고리즘 개선하기 (0) | 2022.07.22 |
셸 정렬(Shell Sort) (0) | 2022.07.19 |
단순 선택 정렬 & 단순 삽입 정렬 (0) | 2022.07.18 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!