큐

큐란?

가장 처음에 들어간 데이터가 처음으로 꺼내지는 구조를 가진 자료구조 입니다. (FIFO)

 

 

큐의 ADT

큐란 자료구조를 구현하기 전에 해당 자료구조의 ADT를 정의할 필요가 있습니다.

1. First in First Out(FIFO) : 처음에 들어간 값이 첫 번째로 나오는 구조

2. 탐색, 삽입, 삭제를 구현할 것.

3. 큐의 전방, 후방을 나타내는 변수를 선언할 것.

 

 

큐의 ADT 선언

큐의 ADT를 참고하여 클래스로 선언 해보겠습니다. 

#include "pch.h"
#include <iostream>
using namespace std;

template <typename T>
struct Node
{
	T		 value;
	Node<T>* prevNode;
	Node<T>* nextNode;
};

template <typename T>
class CustomQueue
{
public:
	CustomQueue()
		, m_front(nullptr)
		, m_rear(nullptr)
	{

	}
public:
	// 1. 탐색
	bool search(T data);

	// 2. 삽입
	void push(T data);

	// 3. 삭제
	void pop();

	// 4. 가장 앞에 있는 값 추출
	T front();

	// util 함수들
	bool empty();
	int  size();

private:
	Node* m_front;
	Node* m_rear;
	

};

 

코드 분석

일단 ADT에서 생각했던 부분을 위주로 선언을 해두었습니다.

위와 같이 선언된 큐는 기본적인 요소와 기능을 갖추고 있으며 구현하는 사람에 따라 요소와 기능의 선언이 달라질 수 있습니다. 위의 선언에서 요소와 기능을 중점으로 간단하게 설명해보겠습니다.

 

요소

1. m_front    :  가장 앞에 있는 노드를 나타내는 포인터입니다.

2. m_rear     :  가장 뒤에 있는 노드를 나타내는 포인터입니다.

                        m_rear는 가장 먼저 삽입한 객체를 반환하기 위한 포인터입니다.                    

 

기능

1. search : 탐색 기능입니다.

2. push : 삽입 기능입니다.

3. pop : 삭제 기능입니다.

4. front : 가장 먼저 삽입한 노드의 값을 반환하는 함수입니다.