[p179-4]원형 연결 리스트를 이용한 큐 C++ 자료구조론

원형 연결 리스트를 이용하여 큐 ADT를 구현하는 C++ 템플릿 클래스를 작성하고 테스트하라.
CirLinkedQ.cpp



#include<iostream>
using namespace std;

template<class T>
class LinkedQueue;

template<class T>
class ChainNode { // ChainNode Class
friend class LinkedQueue<T>;
public:
ChainNode(T element=0, ChainNode<T> *next=NULL)
: data(element), link(next)
{}
private:
T data;
ChainNode<T> *link;
};

template<class T>
class LinkedQueue { // LinkedQueue Class
public:
LinkedQueue() : front(NULL), rear(NULL)
{}
bool IsEmpty() const; // 공백 큐인지 검사
T& Front() const; // Front의 Accessor
T& Rear() const; // Rear의 Accessor
void Push(const T& e); // 맨 뒤에 노드 추가
void Pop(); // 첫번째 노드 삭제
int length(); // 큐에 있는 노드의 개수를 리턴
void print2Cycle();
// 큐를 두바퀴 출력(원형 연결 리스트임을 확인)
private:
ChainNode<T> *front;
ChainNode<T> *rear;
};

template<class T>
bool LinkedQueue<T>::IsEmpty() const
{ // front==rear 로는 공백 큐인지 검사할 수 없음
return (front==NULL && rear==NULL);
} // 노드가 1개인 경우에 front==rear

template<class T>
T& LinkedQueue<T>::Front() const
{
if(IsEmpty()) { // 공백 큐인 경우 메시지 출력 후 종료
cout<<"Queue is empty. No front element. EXIT"<<endl;
exit(1);
}
return front->data;
}

template<class T>
T& LinkedQueue<T>::Rear() const
{
if(IsEmpty()) { // 공백 큐인 경우 메시지 출력 후 종료
cout<<"Queue is empty. No rear element. EXIT"<<endl;
exit(1);
}
return rear->data;
}

template<class T>
void LinkedQueue<T>::Push(const T& e)
{
if(IsEmpty()) { // 공백 큐인 경우
front = rear = new ChainNode<T>(e, 0);
rear->link = front;
}
else
rear = rear->link = new ChainNode<T>(e, front);
}

template<class T>
void LinkedQueue<T>::Pop()
{
if(IsEmpty()) { // 큐가 비어있는 경우
cout<<"Queue is empty. Cannot delete."<<endl;
return;
}
if(front == rear) { // 노드가 1개인 경우
delete front;
front = rear = NULL;
}
else { // 노드가 2개 이상인 경우
ChainNode<T> *delNode = front;
rear->link = front = front->link;
delete delNode;
}
}

template<class T>
int LinkedQueue<T>::length()
{
if(front==NULL) // 공백 큐인 경우 0 리턴
return 0;
else
{ // 공백이 아닌 경우 i를 1로 초기화 하여 count
int i=1;
ChainNode<T> *temp = front;

for(; temp->link != front ; i++)
temp = temp->link;

return i;
}
}

template<class T>
void LinkedQueue<T>::print2Cycle()
{
if(IsEmpty()) {
cout<<"Queue is empty. Cannot print."<<endl;
return;
}
ChainNode<T> *temp = front;

for(int i=0 ; i<2*length() ; i++)
{
cout<<temp->data<<" -> ";
temp = temp->link;
}
cout<<endl;
}


void main(void)
{
LinkedQueue<char> LQint;
for(int i=0 ; i<4 ; i++)
LQint.Push(i+'A');
cout<<"Length :"<<LQint.length()<<endl;
LQint.print2Cycle();

cout<<"Front: "<<LQint.Front()<<endl;
cout<<"Rear : "<<LQint.Rear()<<"\n\n";

for(int i=0 ; i<4 ; i++) {
LQint.Pop();
cout<<"Length :"<<LQint.length()<<endl;
LQint.print2Cycle();
cout<<endl;
}

LQint.Push('Q');
cout<<"Length :"<<LQint.length()<<endl;
LQint.print2Cycle();
cout<<"Front: "<<LQint.Front()<<endl;
cout<<"Rear : "<<LQint.Rear()<<"\n\n";
}


큐!


덧글

댓글 입력 영역