📌 선형 큐 (Linear Queue)
- 데이터가 뒤에서 들어오고 데이터가 앞에서 빠져나가는 구조
- 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out)구조 (선입선출 구조)
- 예를 들면, 버스정류장에서 대기하는 사람들
-> 가장 먼저 와서 기다리는 사람이 가장 먼저 버스에 탑승- 앞부분과 뒷부분을 추적하는 front 변수와 rear 변수를 가짐
- 뒤에서는 데이터 추가 & 앞에서는 데이터 삭제
선형큐를 배열로 구현해보았다
✅ 선형큐를 클래스로 만들기(선언 & 초기화)
-
큐를 구현할 Container 배열 선언
-
큐의 크기 size변수
-
큐의 앞부분을 가리키는 front변수
-
큐의 뒷부분을 가리키는 rear변수
-> front == rear : 큐가 비어있는 상태
-> rear 가 배열의 끝에 도달함 : 큐가 꽉 찬 상태
#include <iostream>
#define SIZE 5
using namespace std;
template <typename T>
// 선형 큐
class LinearQueue
{
private:
T Container[SIZE];
int size;
int front;
int rear;
public:
LinearQueue()
{
for (int i = 0; i < SIZE; i++)
{
Container[i] = NULL;
}
size = 0;
front = 0;
rear = 0;
}✅ Push( ) 함수 (데이터 넣기)
-
rear가 SIZE보다 크거나 같으면 더이상 데이터를 넣을 수 없음
-
기본적으로 데이터를 넣을때 값을 넣어준 후 rear값 증가
void Push(T data)
{
if (rear >= SIZE)
{
cout << "Linear Queue OverFlow" << endl;
}
else
{
Container[rear++] = data;
size++;
}
}✅ Pop( ) 함수 (데이터 빼기)
-
큐가 비어있는지 확인하기 위한 bool형 Empty( ) 함수
-> rear 와 front가 같으면 큐에 데이터가 하나도 없다는 것 -
큐가 비어있으면 뺄 데이터가 없기에 메세지 출력
-
큐가 비어있지 않으면 Container[front++] = NULL로
-> 데이터를 NULL로 만들고 후위증가로 front이동
void Pop()
{
if (Empty() == false)
{
Container[front++] = NULL;
size--;
}
else if (Empty())
{
cout << "Linear Queue is Empty" << endl;
}
}
bool Empty()
{
if (front == rear)
{
return true;
}
else
{
return false;
}
}
📌 맨 앞부분 데이터 & 맨 뒷부분 데이터 & 사이즈 반환
- 큐가 비어있으면 종료
- front는 그자리 바로 반환
- rear는 데이터를 넣고 증가시키기 때문에 실제 위치는 +1 위치이다
-> 그렇기 때문에 rear - 1 해줌
const T & Front()
{
if (Empty())
{
cout << "No Data Exists" << endl;
exit(0);
}
else
{
return Container[front];
}
}
const T & Back()
{
if (Empty())
{
cout << "No Data Exists" << endl;
exit(0);
}
else
{
return Container[rear - 1];
}
}
const int& Size()
{
return size;
}📌 메인 함수
-
Push( )함수를 이용해서 선형큐에 데이터를 다 삽입
-
while문을 사용해서 첫번째 들어온 데이터부터 차례로 출력한 후 Pop( )
❌선형큐의 문제점
- 현재 데이터를 모두 뺀 상태 -> 데이터를 새로 넣으면 들어가야함
-> 하지만, 이 코드를 실행했을 경우 큐 오버플로우가 발생한다 - rear가 (배열의 끝) 마지막 인덱스를 가리키고 있는 경우, rear가 배열의 끝에 있기에, 앞부분의 인덱스는 사용하지 못하는 경우가 발생
-> ✅ 앞부분이 비어있어도 사용못함 -> 공백으로 남은상태 (사용하려면 요소들을 이동시켜야함)
- ✅ 큐 앞부분이 비어있음에도 rear가 배열의 끝이라 이미 큐는 꽉찬걸로 인식되어 한번 더 Push( )하게되면 오버플로우가 발생하는 것
int main()
{
LinearQueue<int> linearQueue;
linearQueue.Push(10);
linearQueue.Push(20);
linearQueue.Push(30);
linearQueue.Push(40);
linearQueue.Push(50);
cout << "Linear Queue의 크기 : " << linearQueue.Size() << endl;
while (linearQueue.Empty() == false)
{
cout << linearQueue.Front() << " ";
linearQueue.Pop();
}
// 다 지운 후 새로 넣어도 오버플로우 발생
linearQueue.Push(99);
return 0;
}출력값 :
선형큐의 시간복잡도
O(1)
선형 큐의 모든 기본 연산(삽입, 삭제, 확인 등)은 배열의 인덱스를 직접 접근하는 방식. 큐의 크기에 상관없이 항상 일정한 시간을 가짐
뉴비 개발자