<C++> 11. 큐

큐

- 선입 선출(FIFO, First-in First-out)

: 가장 먼저 삽입되는 개체가 가장 먼저 삭제되는 구조, 편의점에서 물건 채울때 원리

- 전단(front)은 큐에서 삭제가 일어나는 곳

- 후단(rear)은 큐에서 삽입이 일어나는 곳

큐의 연산 - 삽입(Enqueue)

- 비어 있는 큐의 초기 상태에는 Front와 Rear 값 모두 -1로 설정

- 자료가 삽입될 때마다 Rear가 1씩 증가하며 이동.

- 새로운 자료를 삽입하기 위해서는 먼저 Rear 포인터를 증가시키고,
그 위치에 자료를 입력

큐의 연산 - 삭제(Dnqueue)

- Front 포인터가 1씩 증가하며 자료를 삭제

- 마지막으로 입력된 자료가 삭제되면 Front 포인터와 Rear 포인터의 값이 같아짐.

큐의 연산

큐의 단점

- 위 사진은 4개의 공간을 가지는 큐 구조에 'A', 'B', 'C', 'D' 4개의 자료를 삽입

(Enqueue)하고 2개의 자료를 삭제(Dequeue)한 경우

 

원형큐의 이해

- 원형큐는 Rear나 Front가 배열의 끝에 도달하면

회전하도록 하여 메모리 공간을 좀 더 효율적으로 사용할 수 있음.

- Front와 Rear의 초깃값은 0

- 원형 큐는 자료 공간이 가득 찬 것과 빈 것을 구분하기 위해 Front가 위치한 곳은 자료를 저장할 수 없도록 비워두는 것이 일반적

- Front와 Rear의 값이 같다면 Empty

- Front의 공간은 항상 비워 두기 때문에 Rear+1의 위치가 Front와 같게 된다면 Full

큐의 구현 - 구현할 함수

void InitQueue(int qsize)    크기가 qsize인 배열 할당-> front와 rear를 -1로 설정

 

void Enqueue(int data)       큐가 꽉 찼을 때 알림 -> 그렇지 않으면 rear 인덱스 증가시키고 자료를 큐에 저장

 

int Dequeue()                       큐가 비어있으면 -1을 반환 -> 그렇지 않으면 front 증가시키고  front가 가리키는 값을 반환

 

int IsFull()                            큐가 꽉 찬 상태면 1을 반환

int IsEmpty()                        큐가 꽉빈 상태면 1을 반환

 

< 코드 >

#include <iostream>

using namespace std;
class Queue
{
	int* buf;
	int qsize;
	int front;
	int rear;
public:
	void InitQueue(int qsize)
	{
		this->qsize = qsize;
		buf = new int[qsize];
		front = rear = -1;

	}
	void Enqueue(int data)
	{
		if (IsFull())
		{
			cout << "큐가 꽉 찼음" << endl;
			return;
		}
		buf[++rear] = data;
	}

	int Dequeue()
	{
		if (IsEmpty())
			return -1;
		return buf[++front];
	}

	int IsEmpty()
	{
		return front == rear;
	}
	int IsFull()
	{
		return rear == qsize-1;
	}
};
int main()
{
	int i;
	Queue q1;
	q1.InitQueue(10);
	for (size_t i = 1; i <= 11; i++)
	{
		cout << i << " 입력\n";
		q1.Enqueue(i);
	}
	cout << endl;

	while (!q1.IsEmpty())
	{
		cout << q1.Dequeue() << " 출력\n";
	}
	cout << endl;
	return 0;
}

 

원형큐 구현

• front와 rear의 초깃값은 0
• front와 rear의 값이 같다면 Empty
• rear+1의 위치가 front와 같게 된다면 Full
• 삽입 시, rear <-( rear + 1 ) % qsize
• 삭제 시, front <- (front + 1) % qsize