Linked Queue

Operations

<Observers>

- IsEmpty

- IsFull

 

<Transformers>

- MakeEmpty

- Enqueue

- Dequeue

 

LinkedQueue에서는 큐 앞을 관리하는 qFront, 마지막을 관리하는 qRear 가 필요하다.

class LinkedQType

LinkedQType()

template <class ItemType>
LinkedQType<ItemType>::LinkedQType(){
	qFront = NULL;
    	qRear = NULL;
}

 

~LinkedQType()

template <class ItemType>
LinkedQType<ItemType>::~LinkedQType(){
	MakeEmpty();
}

 

bool IsEmpty()

template <class ItemType>
bool LinkedQType<ItemType>::IsEmpty(){
	return (qFront == qRear);
}

 

bool IsFull()

새 노드 만들고 지우는거 성공하면 노드 만들 메모리 아직 존재 -> return false

실패하면 IsFull 

template <class ItemType>
bool LinkedQType<ItemType>::IsFull(){
	NodeType<ItemType>* temp;
    try{
    	temp = new NodeType<ItemType>;
        delete temp;
        return false;
    }
    catch(bad_alloc exception){
    	return true;
        }

 

void MakeEmpty()

포인터 하나 만들어서 비어있는 큐가 아닐 때 tempPtr이 qFront 계속 삭제해준다.

template <class ItemType>
void LinkedQType<ItemType>::MakeEmpty(){
	NodeType<ItemType>* tempPtr;
    while(qFront != NULL){
    	tempPtr = qFront;
        qFront = qFront -> next;
        delete tempPtr;
    }

 

void Enqueue(ItemType newItem)

새로운 아이템을 넣으려면 새 location을 생성해야한다. location의 info에 값을 넣고 next는 NULL로 한다.

왜냐면 새로운 노드는 큐의 맨 끝에 들어갈거니까. 

만약 큐가 비어있는 상태라면 (qFront나 qRear == NULL) 방금 만든 노드가 큐의 첫번째 노드이다. (qFront = location)

큐가 비어있지 않다면 qRear의 next를 location으로. 

마지막으로 qRear = location!!! (큐의 마지막 노드가 방금 넣은 노드) 

template <class ItemType>
void LinkedQType<ItemType>::Enqueue(ItemType newItem){
	if(IsFull()){
    	throw FullQueue();
    }
    else{
    	NodeType<ItemType> location;
        location = new NodeType<ItemType>;
        location -> info = newItem;
        locatino -> next = NULL;
        if(qRear = NULL){               //EmptyQueue일 때 맨앞을 location으로.
        	qFront = location;
        }
        else{
        	qRear -> next = location;
        }
        qRear = location;
    }

 

void Dequeue(ItemType& item)

비어있지 않은 큐에서 시작. tempPtr을 만들어두고 맨 앞을 가리키게 함. qFront는 다음 노드로 넘김. 

근데 그 노드가 NULL이면 (큐에 원소 1개가 들어있어서 qFront = qRear 였던 상황) qRear 도 NULL로 만들어준다.

마지막으로 tempPtr 삭제.

template <class ItemType>
void LinkedQType<ItemType>::Dequeue(ItemType& item){
	if(IsEmpty()){
    	throw EmptyQueue();
        }
    else{
    	NodeType<ItemType>* tempPtr;
        tempPtr = qFront;
        qFront = qFront -> next;
        if(qFront == NULL){
        	qRear = NULL;
            }
        delete tempPtr;