Queue

Queue 는 스택과 비슷하게 삽입과 삭제의 위치가 제한되어있는 유한 순서리스트이다. 큐는 스택과 다른점으로 뒤에서 삽입만 하고 , 앞에서는 삭제를 할수 있는 구조인 First In First Out , FIFO , 선입선출구조라고 할수있다.

Queue 연산

q,empty() : 비어있게되면 true 아니면 false 를 return 을 해준다.
q.size() : queue 안에 들어있는 원소의 수를 return 해준다.
q.front(): 맨앞의 원소를 return 해준다 .
q.back() : 맨 뒤 원소를 return 을 해준다 .
q.push(index): queue 에 index를 추가를하는데 맨뒤에 삽입을 한다.
q.pop() : queue 에서 맨앞의 원소를 삭제를 한다.

코드 구현

queue 에는 선형 queue 와 원형 queue 가 있다. 이번에는 선형 queue 를 다루어보도록 하겠다 .

배열 사용

#include<iostream>
using namespace std;
#define SIZE 5
template <typename T>
class Queue
{
private:
	int front; //맨앞 index를 나타냄
	int rear; //맨뒤 index를 나타냄
	int size;
	T QueueArr[SIZE];

public:
	Queue()
	{
		for (int i = 0; i < SIZE; i++)
		{
			QueueArr[i] = NULL;
		}
		front = 0;
		rear = 0;
		size = 0;
	}
	~Queue()
	{
		cout << "Release Queue" << '\n';
	}
	void Push(T data)
	{
		if (IsFull()) //포화 상태 확인 
		{
			cout << "Queue is Full" << '\n';
			return;
		}
		else
		{
			QueueArr[rear] = data; //맨끝에 삽입 
			rear++; //맨끝 index+1
			size++; //size 늘어남
		}
	}
	void Pop()
	{
		cout << "Remaining Arr : " << size << '\n';
		if (Empty())
		{
			cout << "Release Arr" << '\n';
		}
		else
		{
			QueueArr[front] = NULL;
			front++ ;//front index 를 늘려줌
			size--;
		}
	}
	bool IsFull()
	{
		if (SIZE <= rear) //현재 max size 5가 rear랑 같거나 이상이면 가득참
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool Empty()
	{
		if (front == rear) //front 와 rear 가 같으면 queue 안에 원소가 없다는것을 의미
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Front()
	{
		if (Empty())
		{
			exit(1); //빠져 나옴 
		}
		else
		{
			return QueueArr[front];
		}

	}
	T& Back()
	{
		if (Empty())
		{
			exit(1); //빠져 나옴 
		}
		else
		{
			return QueueArr[rear-1];
		}

	}
	int& Size() // '&'사용해주면서 복사되는 비용 안쓰게 됌  
	{			//반환 되는 값 size가 같이 들어가게 됌  기존의 int Size() 는
				//return 하면서 size 갓을 복사하여 반환하기에 복사비용이 생성됨
		return size;
	}
};

int main()
{
#pragma region 선형구조 Queue
	// 배열의 공간에 들어간 데이터가 고정되어 
	// 데이터를 빼내더라도 초기화하지 않으며,
	// 원래 데이터가 있던 배열의 자리에 더이상 다른 값이 
	// 들어올 수 없는 Queue.

	Queue <int>queue;
	queue.Push(10);
	queue.Push(20);
	queue.Push(30);
	queue.Push(40);
	queue.Push(50);
	cout << queue.Back() << endl;



	cout << "Queue.Size : " << queue.Size() << endl;
	while (!queue.Empty())
	{
		cout << queue.Front() << endl;
		
		queue.Pop();
	}



#pragma endregion


	return 0;


}

연결구조 활용 선형 queue

배열을 사용하여 queue 를 만드는 것은 쉽게 가능하지만 배열은 크기가 정해져있다는 단점이 있다. (포화가 생기는 점 ) 그래서 연결구조를 활용하여 선형 queue를 제작하여 포화문제를 해결해보도록하겠다.

#include<iostream>
using namespace std;

template<typename T>

class Queue
{
private:
	struct QNode
	{
		T data; 
		QNode* link; 
	};
	QNode* front;
	QNode* rear;
	int size;

public:
	Queue() //초기화 
	{
		front = nullptr;
		rear = nullptr;
		size = 0;
	}
	void Push(T data)
	{
		QNode* newNode = new QNode;
		newNode->data = data;
		newNode->link = nullptr;
		if (front == nullptr) //현재 queue 에 아무것도 없을때
		{
			front = newNode;
			rear = newNode; //현재 맨끝도 newNode;
		}
		else
		{
			rear->link = newNode;
			rear = newNode;
		}
	}
	void Pop() 
	{
		QNode* deleteNode = front; //맨앞노드 삭제를 위함 
		if (Empty())
		{
			cout << "Queue is Empty" << '\n';
			return;
		}
		else
		{	
			front = front->link;
			if (front == nullptr) //그다음 front 가없다 = 삭제하게되면 queue 는 비었다
			{
				rear = nullptr; //rear 초기화
			}
			delete deleteNode; //삭제 
		}
	}
	bool Empty() //비어있는지 확인
	{
		if (!front)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Front() //맨앞출력
	{
		return  front->data;
	}
	T& Back() //맨뒤 출력
	{
		return rear->data;

	}
	void Print() //queue 안에 있는 원소들 전부 출력
	{
		QNode* printNode = front;
		cout << "Linked Queue : [";
		while (printNode)
		{
			cout << printNode->data << " ";
			printNode = printNode->link;
		}
		cout << "]\n";
	}
	~Queue()
	{
		while (!Empty())
		{
			Pop();
		}
		cout << "Release Queue" << '\n';
	}
};

int main()
{

	Queue<int>que;
	que.Push(1);
	que.Push(2);
	que.Push(3);
	que.Push(4);
	que.Push(5);
	que.Print();
	cout << que.Back() << '\n';
	while (!que.Empty())
	{
		cout << que.Front() << '\n';
		que.Pop();
	}
	return 0;
}

이렇게 선형 큐를 다루어보았다 그다음으로 원형큐를 다루어보도록 하겠다.