[C++/템플릿으로 만드는 자료구조] 큐(Queue)

C++/템플릿으로 제작한 큐(Queue)의 소스입니다. iostream을 인클루드 해야 이용할 수 있습니다.

template<typename Type>
class Node
{
public:
    Node *Link;
    Type VALUE;
};
 
template<typename Type>
class Queue
{
private:
    Node<Type> *header;//제일 앞 포인터
    Node<Type> *tailer;//제일 뒤 포인터
    Node<Type> *pre_tail;//제일 뒤 바로 앞 포인터
public:
    Queue();
    ~Queue();
    bool Is_Empty();
    void Enqueue(Type Item);
    Type Dequeue();
    void Printing();
};
 
template<typename Type>
Queue<Type>::Queue()
{
    this->header = NULL;
    this->tailer = NULL;
    this->pre_tail = NULL;
}
 
template<typename Type>
Queue<Type>::~Queue()
{
 
}
 
template<typename Type>
bool Queue<Type>::Is_Empty()
{
    if (this->header == NULL)
    {
        std::cout << "This Queue is empty." << std::endl;;
        return true;
    }
    else
    {
        std::cout << "This Queue is not empty." << std::endl;;
        return false;
    }
}
 
template<typename Type>
void Queue<Type>::Enqueue(Type Item)
{
    Node<Type> *New = new Node<Type>;
    if (this->Is_Empty())
    {
        this->header = New;
        this->tailer = New;
        New->VALUE = Item;
        New->Link = NULL;
        return;
    }
    else
        if (this->pre_tail == NULL)
        {
            New->Link = this->header;
            New->VALUE = Item;
            this->pre_tail = New;
            this->header = New;
        }
        else
        {
            New->Link = this->header;
            New->VALUE = Item;
            this->header = New;
        }
}
 
template<typename Type>
Type Queue<Type>::Dequeue()
{
    if (this->Is_Empty())
    {
        return 0;
    }
    int Value = 0;
    Node<Type> *Temp = NULL;
    Node<Type> *Delete = NULL;
    Node<Type> *Cur = this->header;
    while (Cur != this->pre_tail)
    {
        Temp = Cur;//temp Tail 이전의 노드를 가리키는 포인터 저장
        Cur = Cur->Link;
    }
    Delete = this->tailer;
    Value = Delete->VALUE;
    this->pre_tail = Temp;
    this->tailer = Temp->Link;
    this->tailer->Link = NULL;
    delete(Delete);
    return Value;
}
 
template<typename Type>
void Queue<Type>::Printing()
{
    Node<Type> *Cur = this->header;
    while (Cur != NULL)
    {
        std::cout << Cur->VALUE << " ";
        Cur = Cur->Link;
    }
    std::cout << std::endl;
}

Queue는 STL에서 이용할 때는 queue를 인클루드 하여 사용하게됩니다.

같이보기

2015/12/16 - [Programming/자료구조] - [C로 만드는 자료구조]큐(Queue) - 배열

2015/12/16 - [Programming/자료구조] - [C로 만드는 자료구조]큐(Queue) - 동적