원형큐를 이용해 카드 정렬하기

class와 queue 개념을 활용하여 카드를 정렬하는 알고리즘

학교 과제로 해결했던 카드 정렬 알고리즘에서 원형큐를 잘 이해해버린 것 같다!
평소 python에서 쓰던 .popleft() .append .pop(3) 이런 함수들을 내가 구현해버린 기분.. 😋

원형큐의 핵심은 front와 rear을 이용하는 것이다.

queue.h

#include <iostream>
using namespace std;

class CircularQueue {
private:
	int queue[6] = {};
	int front; //front = 0 으로 초기화
	int rear; //rear는 꼬리로 배열이 차있는 영역까지라고 생각하면 된다
	int maxQueueSize; 

public:
	CircularQueue(int);
	void isEmpty();
	void isFull();
	void enQueue(int item, int index);
	void showCircularQueue();
};

CircularQueue.cpp

#include "queue.h"

CircularQueue::CircularQueue(int maxQueueSize) //원형큐를 생성한다
	:maxQueueSize(maxQueueSize)
{
	front = 0; //머리와 꼬리를 0으로 갱신
	rear = 0;
}

void CircularQueue::isEmpty() { //큐가 비었음을 알려주는 함수
	if (front == rear) {
		cout << "큐가 비었습니다.\n";
	}
}

void CircularQueue::isFull() { //큐가 차있음을 알려주는 함수
	if (front == (rear + 1) % maxQueueSize) {
		cout << "큐가 꽉찼습니다.\n";
	}
}

void CircularQueue::enQueue(int item, int index) { 
	if (front==rear) {
		queue[++rear] = item; //일단 비어있을 때 기본적으로 원소 삽입
	}
	else if (front == (rear + 1) % maxQueueSize) {
		isFull();  //만약 꽉 차있다면 끝!
	}
	else { 
		int shift = front+1; //shift 변수를 front+1 , 즉 배열 1번째 원소부터 차례대로 비교해나간다.
		while (queue[shift]!=0 and queue[shift] - item < 0) { //이 때 내가 넣은 것과 비교해나가면서 내가 넣은 것보다 큰 게 나올 때까지 
																//계속 shift변수를 증가시킨다.
			shift++;
		}
		if (queue[shift] - item == 0) {
			cout << "똑같은 카드가 들어왔습니다. 다시 카드를 삽입합니다.";
			index--;
		}
		else if (shift == rear+1) { //shift를 다 증가시켰는데 꼬리를 넘겼을 경우 그 뒤에다가 그냥 붙인다.
			queue[(++rear) % maxQueueSize] = item;
		}
		else { //꼬리를 넘기지 못할 경우
			for (int i = rear+1; i >= shift; i--) { //꼬리부터 shift 까지의 원소들을 하나씩 뒤로 옮겨준다.
				queue[i % maxQueueSize] = queue[(i - 1) % maxQueueSize];
			}
			queue[shift%maxQueueSize] = item; //그리고 shift 자리에다가 내가 삽입하려는 원소를 넣는다.
			rear++; //이후 하나씩 원소들을 옮겨줬으므로 꼬리를 하나 더해준다.
			}
		}
	}


void CircularQueue::showCircularQueue() { 
	if (front == rear) { //만약 front와 rear가 일치하도록 나온다면 isEmpty 함수를 불러 큐가 비었음을 알린다.
		isEmpty();
	}
	else {
		cout << "현재 원형 큐에 존재하는 수는: \n";

		for (int i = 1; i < maxQueueSize; i++) { //front인 0번 원소를 빼놓고 출력하기 시작한다.
			if (queue[i]/13 == 1) { //S 카드에 해당하는 숫자 검열해서 출력
				int num = (queue[i] + 1) % 13;
				if (num == 0) { num = 13; }
				cout << 'S' << num; 
			}
			else if (queue[i] / 13 == 2  ) { //D
				int num = (queue[i] + 1) % 13;
				if (num == 0) { num = 13; }
				cout << 'D' << num;
			}
			else if (queue[i] / 13 == 3) {//H
				int num = (queue[i] + 1) % 13;
				if (num == 0) { num = 13; }
				cout << 'H' << num;
			}
			else if (queue[i] / 13 == 4){ //C
				int num = (queue[i] + 1) % 13;
				if (num == 0) { num = 13; }
				cout << 'C' << num;
			}
			else {
				cout << 0;
			}
			cout << '\n';
		}
		cout << "\n";
	}

}

main.cpp

#include "queue.h"
#include <random>
using namespace std;

int main() {
	int maxQueueSize = 6; //어차피 넣을 카드는 5개이다. 최대크기를 6으로 설정한다.
	CircularQueue cq(maxQueueSize); //원형큐 만든다
	
	int index = 0; //넣을 카드 숫자 한도 설정
	int cardnum = 0; //카드 숫자를 랜덤으로 받을 예정이다.
	
	while (index < 5) { //다섯 개의 카드를 넣을 예정이다.
		cout << "\n랜덤으로 카드를 선택해 집어넣습니다.\n";
		std::random_device rd; //난수 생성 엔진 초기화
		std::mt19937 gen(rd());
		std::uniform_int_distribution<int> dis(13, 64);//카드 숫자는 13부터 64 중 랜덤으로 받는다.
		cq.enQueue(dis(gen),index); //그 카드를 큐 안에 넣는다
		cq.showCircularQueue(); //큐 속 카드들을 보여준다.
		index++; 
	}
}