본문 바로가기

C++ 자료구조

[c++] 큐 (Queue)

[큐 (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