#include <iostream>
#include <vector>
#include <string>

struct Node {
	int Value;
	Node* nextNode = nullptr;

	Node(const int _Value)
		: Value(_Value)
		, nextNode(nullptr)
	{};
};

class Queue
{
public:
	~Queue()
	{
		while (!IsEmpty())
		{
			dequeue();
		}
	}

	Node* front;
	Node* rear;

	bool IsEmpty()
	{
		return front == nullptr && rear == nullptr;
	}

	void enqueue(int _value)
	{
		Node* newNode = new Node(_value);

		front = front == nullptr ? newNode : front;
		rear = rear == nullptr ? front : rear;

		rear->nextNode = newNode;
		rear = newNode;
		rear->nextNode = front;
	}

	void dequeue()
	{
		if (nullptr != rear && nullptr != front)
		{
			std::cout << "Dequeue : " << front->Value << std::endl;

			Node* nextFront = front->nextNode;
			delete front;
			if (rear == front)
			{
				front = nullptr;
				rear = nullptr;
			}
			else
			{
				front = nextFront;
				rear->nextNode = nextFront;
			}
		}
	}

	void peek()
	{
		static Node* value = front;

		if (nullptr != value)
		{
			std::cout << value->Value << std::endl;
			value = value->nextNode;
		}
	}
};

int main()
{
	Queue queue;

	queue.enqueue(1);
	queue.enqueue(2);
	queue.enqueue(3);
	queue.enqueue(4);
	queue.enqueue(5);

	queue.dequeue();

	for (int index = 0; index < 6; index++)
	{
		queue.peek();
	}
	return 0;
}

Node를 활용한 원형 큐 구현

front, rear Node Pointer와 peek을 하기 위한 value Node pointer가 추가로 필요하였음

그리고, dequeue를 해서 제일 마지막에 요소가 한개만 남았을 때에,
해당 요소를 처리해주는 추가적인 로직이 필요했음 ( 관련 로직은 빠질 수 있지 않았을까? )

은행에서 대기번호를 저장하는 문제를 다시 생각해보자.

앞에서는 1차원 배열에 번호를 저장하도록 구현했다.

이 방법은 처음 선언하는 배열의 크기에 따라 입력할 수 있는 번호의 개수가 제한된다는 심각한 문제가 있다.

미리 너무 큰 배열을 잡으면 다른 중요한 은행 업무 프로그램들이 사용할 메모리가 부족하다.

그렇다고 배열을 너무 작게 잡으면 고객이 많이 몰리는 날에는 문제가 생긴다.

이를 해결하기 위해 연결리스트(Linked List) 자료구조를 써보자.

연결리스트는 노드(node)가 데이터를 담은 채로 연결되어 있는 자료구조다.

데이터와 포인터를 갖고 있는 노드들이 연결되어 있는데, 노드의 포인터는 다음 노드를 가리킨다.

Head는 첫 노드를, Tail은 마지막 노드를 가리킨다.

마지막 노드의 포인터는 아무것도 가리키지 않는다는 의미로 NULL 값을 가진다.

연결리스트는 배열과는 다르게 중간에 노드를 삽입하거나 제거할 때,

원소를 밀어내거나 이동할 필요가 없다.

하지만, 리스트에서 임의의 위치에 있는 ("n번째") 원소를 찾는 과정이 오래 걸린다.

1. 연결리스트로 큐 작성하기

연결리스트를 이용하여 대기번호 관리 프로그램을 구현하라.

[ 코드 ]

ㅇ

[ 결과 ]

ㅇ

사람들이 차례를 기다리며 서있는 줄을 생각해보자.

앞에서부터 한 명씩 빠져나가 업무를 처리하는 줄을 큐(Queue)라고 한다.

은행에서 번호표를 받으면 큐에 들어가는 것을 볼 수 있고,

대기하던 고객이 자신의 번호가 불려져 창구에서 일을 처리하는 것은 큐에서 빠져나오는 것으로 볼 수 있다.

즉, 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조를 말한다. 

반대로 스택(Stack)은 먼저 들어가나 데이터가 가장 나중에 나오는 자료구조다. 

여기서는 큐 자료구조를 구현해보자

1. 배열로 큐 작성하기

은행에서 대기 번호를 관리하는 프로그램을 작성해보자

[ 코드 ]

#include <iostream>

#define QUEIE_CAPACITY 8 // 큐에 사용되는 배열의 크기 설정

using namespace std;

int queue[QUEIE_CAPACITY];
int head = 0;
int tail = -1;
int queue_size = 0;

void enquene(int n){
	if (queue_size == QUEIE_CAPACITY){
		cout << "Queue Full !" << endl;
		return ;
	}
	tail++;
	queue_size++;
	queue[tail] = n;
}

int dequeue(){
	int r;
	if (queue_size ==0){
		cout << "Queue Empty!" << endl;
		return 0;
	}

	r = queue[head];
	head++;
	queue_size--;
	return r;
}

int main(void){
	int number, r;
	do {
		cout <<"Input number :" << endl;
		cin >> number;

		if (number >0){
			enquene(number);
		}

		else if (number ==0){
			r = dequeue();
			cout << r << endl;
		}
	}
	while (number >=0);

	return 0;
}

[ 결과 ] 

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
Input number :
1
Input number :
2
Input number :
3
Input number :
4
Input number :
5
Input number :
6
Input number :
7
Input number :
8
Input number :
9
Queue Full !
Input number :
0
1
Input number :
0
2
Input number :
0
3
Input number :
0
4
Input number :
0
5
Input number :
0
6
Input number :
0
7
Input number :
0
8
Input number :
0
Queue Empty!
0
Input number :
0
Queue Empty!
0
Input number :

2. 원형 큐 작성

앞의 배열의 경우에는 문제점이 있다.

앞의 번호들을 빼고, 다른 번호들을 넣었을 때라고 생각을 해보면,

Head의 위치가 고정되어 있으며, 이의 경우에는 상황에 따라 Head 위치를 지속적으로 반환시켜주어야 한다.

[ 코드 ]

#include <iostream>

#define QUEIE_CAPACITY 8 // 큐에 사용되는 배열의 크기 설정

using namespace std;

int queue[QUEIE_CAPACITY];
int head = 0;
int tail = -1;
int queue_size = 0;

void enquene(int n){
	if (queue_size == QUEIE_CAPACITY){
		cout << "Queue Full !" << endl;
		return ;
	}
	tail = (tail+1) % QUEIE_CAPACITY; // tail 증가
	queue_size++;
	queue[tail] = n;
}

int dequeue(){
	int r;
	if (queue_size ==0){
		cout << "Queue Empty!" << endl;
		return 0;
	}

	r = queue[head];
	head = (head+1) % QUEIE_CAPACITY;
	queue_size--;
	return r;
}

int main(void){
	int number, r;
	do {
		cout <<"Input number :" << endl;
		cin >> number;

		if (number >0){
			enquene(number);
		}

		else if (number ==0){
			r = dequeue();
			cout << r << endl;
		}
	}
	while (number >=0);

	return 0;
}

[ 결과 ]

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
Input number :
1
Input number :
2
Input number :
3
Input number :
4
Input number :
0
1
Input number :
0
2
Input number :
4
Input number :
5
Input number :
0
3
Input number :
0
4
Input number :
0
4
Input number :
0
5
Input number :
0
Queue Empty!
0
Input number :

배열 arr[]과 위치 s(Start Point), t(Turning Point)가 있을 때,

오른쪽으로 한 칸씩 이동하고, arr[t]는 arr[s]로 복사하는 것을 1만큼 오른쪽으로 회전시켰다고 가정한다.

0. 배열 회전

[ 코드 ]

#include <iostream>

using namespace std;

void right_rotate(int arr[], int s, int t){
	int i, last;
	last = arr[t]; // 끝지점의 배열을 호출한다.
	// s : Start 지점
	// t : End 지점

	for ( i = t; i > s; i--){
		arr[i] = arr[i-1];
		// 한칸씩 오른쪽을 밀려가며 변수를 호출 받는다.
		// End 지점을 호출 받았으므로, End 지점이 비었다.
		// End 지점에 End-1의 변수메모리를 넣는다.
		// End-1 지점에 End-2의 변수메모리를 넣는다.
		// 오른쪽에서부터, 오른쪽으로 한칸씩 밀어가며 변수를 호출한다.
	}
	arr[s] = last;
	// 반복문이 끝난 시점에서 Start지점은 Start+1의 주소로 이동하였으므로 비었다.
	// 즉, Start 지점에 다시 End 지점의 메모리를 할당하여서 최종적으로 배열 회전을 종료한다.
}

int main(void){
	int arr[] = {1,4,5,6,7,7,9};
	cout << "변경 전 배열" << endl;
	int len = sizeof(arr) / sizeof(arr[0]);
	for (int i =0 ; i< len ; i++){
		cout << arr[i];
	}
	cout << ""<< endl;
	right_rotate(arr, 3,len-1);
	cout << "변경 후 배열" << endl;
	for (int i=0; i < len; i++){
		cout << arr[i];
	}
	cout << "" << endl;
	return 0;
}

[ 결과 ]

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
변경 전 배열
1456779
변경 후 배열
1459677