[자료구조] 3-1. Queue

 

🔗 공부 과정에서 참고한 자료 

https://happysalmon.tistory.com/77?category=911360

(C++) 자료구조 - 큐(Queue) - 배열(Array), 링크드리스트(Linked List)

 

---

 

💡 Queue 란? 💡

큐의 동작 구조

 

• FIFO(First In First Out) 구조 : 먼저 온 데이터는 먼저 나간다.
• 큐의 중간에서 데이터의 입출력이 발생할 수 없다.
  • Front : 출력(삭제)이 발생하는 큐의 앞 부분
  • Rear :  입력(삽입)이 발생하는 큐의 뒷 부분

 

---

먼저 배열(Array)를 이용하여 구현한 큐를 공부했다.

 

BUT 발생하는 문제점이 존재한다

 

     index를 따라서 앞에 있는 값을 빼다보면 언젠가는 index == maxSize
     그렇다고 값을 뺄때마다 배열 한 칸씩 땡기는 것은 비효율적이다
           => index가 maxSize에 도달할 경우 0으로 초기화하여 다시 처음부터 돌게 만드는 방법 : 원형 큐

 

💻 QueueArray.h

#pragma once

class QueueArray {

private:
	int front;	// Dequeue 했을 때 나오는 index
	int rear;	// Enqueue 했을 때 들어가는 index
	int maxSize;	// 배열의 크기
	int* arrays;	// 동적 할당할 배열

public:
	QueueArray(int size = 10);	// 생성자
	~QueueArray();			// 소멸자
	bool Enqueue(int value);	// 값을 넣는다
	bool Dequeue(int& value);	// 값을 뺀다
	void Clear();			// 모든 값을 비운다
	void PrintAll();		// 모든 값을 출력한다
};

 

💻 3-1. Queue.cpp

#include "QueueArray.h"
#include <stdio.h>

QueueArray::QueueArray(int size) {

	printf("생성자\n");

	maxSize = size + 1;			// size = 사용할 크기 + 1(비어있는 값 rear)
	arrays = new int[maxSize];	// 배열 동적 할당
	front = rear = 0;			// front == rear -> 비어있다
}

QueueArray::~QueueArray() {

	delete[] arrays;			// 동적할당이므로 delete
	printf("소멸자\n");
}

bool QueueArray::Enqueue(int value) {

	if ((rear + 1) % maxSize == front)  // 큐가 꽉 차있는 경우
		return false;

	*(arrays + rear++) = value;			// 값을 넣어준다.
	rear %= maxSize;					// 원형 큐를 위해서 하는 작업
	printf("enqueu : %d\t", value);	
	printf("front : %d\t rear : %d\n", front, rear);
	return true;
}

bool QueueArray::Dequeue(int& value) {

	if (front == rear)					// 큐가 비어있는 경우
		return false;

	value = *(arrays + front++);		// 값을 넣어준다
	front %= maxSize;					// 원형 큐를 위해서 하는 작업
	printf("dequeu : %d\t", value);
	printf("front : %d\t rear : %d\n", front, rear);
	return true;
}

void QueueArray::Clear() {

	front = rear;				// 같을 경우 큐는 비어있다
	printf("clear\n");
}

void QueueArray::PrintAll() {

	for (int i = front; i != rear; i = ++i % maxSize) {

		printf("%d\t", *(arrays + i));
	}
	printf("\n");
}

int main()
{
	QueueArray* arrayQueue = new QueueArray(3);

	arrayQueue->Enqueue(10);
	arrayQueue->Enqueue(20);
	arrayQueue->Enqueue(30);
	arrayQueue->Enqueue(40);
	arrayQueue->PrintAll();

	int temp;
	arrayQueue->Dequeue(temp);
	arrayQueue->Dequeue(temp);
	arrayQueue->PrintAll();

	arrayQueue->Enqueue(50);
	arrayQueue->Enqueue(60);
	arrayQueue->PrintAll();
	arrayQueue->Clear();
	arrayQueue->PrintAll();

	delete arrayQueue;

}

 

이해한 과정 추가하기