[큐 (Queue)]
- 선입 선출 (FIFO, First-in First-out) : 가장 먼저 삽입 되는 개체가 가장 먼저 삭제되는 구조
- 전단 (front)은 큐에서 삭제가 일어나는 곳
- 후단 (rear)은 큐에서 삽입이 일어나는 곳
[큐의 연산]
삽입 (Enqueue)
- 비어 있는 큐의 초기 상태에는 Front와 Rear 값 모두 -1로 설정
- 자료가 삽입될 때마다 Rear가 1씩 증가하며 이동
- Rear은 마지막 원소를 가르킴
- 새로운 자료를 삽입하기 위해서는 먼저 Rear 포인터를 증가시키고, 그 위치에 자료를 입력
예시)
삭제 (Dequeue)
- Front 포인터가 1씩 증가하며 자료를 삭제
- Front 는 첫 번째 원소의 앞을 가르킴
- 마지막으로 입력된 자료가 삭제되면 Front 포인터와 Rear 포인터의 값이 같아짐
예시)
[큐의 단점]
옆 사진은 4개의 공간을 가지는 큐 구조에 'A', 'B', 'C', 'D' 4개의 자료를 삽입하고 2개의 자료를 삭제한 경우이다.
큐의 단점 : 메모리가 있는데도 삽입할 수 없다.
[원형큐]
- 원형큐는 Rear나 Front가 배열의 끝에 도달하면 회전하도록 하여 메모리 공간을 좀 더 효율적으로 사용할 수 있음
- Front와 Rear의 초기값은 0
- 원형큐는 자료 공간이 가득 찬 것과 빈 것을 구분하기 위해 Front가 위치한 곳은 자료를 저장할 수 없도록 비워두는 것이 일반적
- Front와 Rear의 값이 같다면 Empty
- Front의 공간은 항상 비워 두기 때문에 (Rear+1) % QueueSize가 Front와 같다면 Full
[내가 구현 해본 선형큐]
#include <iostream>
using namespace std;
class Queue
{
public:
int* buf; // 저장소
int qsize; // 큐의 크기
int front; // 꺼낼 인덱스 앞을 가리킴
int rear; // 가장 최근에 보관된 자료를 가리킴
void InitQueue(int qSize)
{
buf = new int[qSize];
qsize = qSize;
front = rear = -1;
}
void EnQueue(int n)
{
if (IsFull())
{
cout << "큐가 꽉 찼음" << endl;
return;
}
buf[++rear] = n;
}
int DeQueue()
{
if (IsEmpty())
return -1;
return buf[++front];
}
int IsFull()
{
return rear == qsize - 1;
}
int IsEmpty()
{
return rear == front;
}
};
int main()
{
int i;
Queue q1;
q1.InitQueue(10);
for (i = 1; i <= 11; ++i)
{
cout << i << " 입력\n";
q1.EnQueue(i);
}
cout << endl;
while (!q1.IsEmpty())
{
cout << q1.DeQueue() << " 출력 \n";
}
cout << endl;
return 0;
}
[내가 구현해본 원형큐]
#include <iostream>
using namespace std;
class Queue
{
public:
int* buf; // 저장소
int qsize; // 큐의 크기
int front; // 꺼낼 인덱스 앞을 가리킴
int rear; // 가장 최근에 보관된 자료를 가리킴
void InitQueue(int qSize)
{
buf = new int[qSize];
qsize = qSize;
front = rear = 0;
}
void EnQueue(int n)
{
if (IsFull())
{
cout << "큐가 꽉 찼음" << endl;
return;
}
else if (rear == qsize - 1)
rear = 0;
buf[++rear % qsize] = n;
}
int DeQueue()
{
if (IsEmpty())
{
cout << "큐가 비었음" << endl;
return -1;
}
return buf[++front % qsize];
}
int IsFull()
{
return (rear + 1) % qsize == front;
}
int IsEmpty()
{
return rear == front;
}
};
int main()
{
Queue q1;
q1.InitQueue(4);
for (int i = 1; i < 5; ++i)
{
q1.EnQueue(i);
}
for (int i = 1; i < 5; ++i)
{
q1.DeQueue();
}
for (int i = 1; i < 5; ++i)
{
q1.EnQueue(i);
}
return 0;
}
'C++ 자료구조' 카테고리의 다른 글
[탐색] 순차 탐색, 이진 탐색 (0) | 2024.06.10 |
---|---|
[C++ | 연결 리스트] 스택, 큐, 리스트 (0) | 2024.04.29 |
[c++] 스택 (Stack) (0) | 2024.04.15 |
시간복잡도 기초 (0) | 2024.04.15 |
[c++] 연산자 중복 (오버로딩) (0) | 2024.04.02 |