Question

c++使用单向循环链表结构实现循环队列。

1 使用链表结构实现循环队列类，要求是多态的；2 要求有循环队列的基本运算操作，如初始化、进队列、出队列、判断队列是否为空和取队首元素等等；3 要求有普通的构造函数、拷贝构造函数和析构函数；4 要求=、<< 和 >>的重载；

Answer 1

我实在不知道你们这个题目是什么意思，竟然继承链表来实现队列，帮你实现了，VC6.0通过
//list.h
#ifndef LIST_H
#define LIST_H
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
class List
{
public:
List();
~List();
List(List&rhs);
List &operator=(List&);
int operator >>(int x);//让>>从尾部输入x
int operator <<(int x);//让<<删除x
virtual void push(int x);
void push(int x,int idx);
void deletex (int x);
virtual void pop();
virtual int top();
bool empty();
int get_num()
{
return m_nNum;
}
Node *get_head()
{
return m_pHead;
}
protected:
int m_nNum;
Node *m_pHead;
};
List::List()
{
m_nNum=0;
m_pHead=new Node;
m_pHead->data=NULL;
m_pHead->next=NULL;
}
List::List(List&rhs)
{

if(this->get_num!=rhs.get_num)
{
cout<<"链变大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;

}

}
}
List&List::operator=(List&rhs)
{
if(this->get_num()!=rhs.get_num())
{
cout<<"链变大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;

}

}
return *this;

}
List::~List()//释放所有的内存
{
Node *i=m_pHead->next;
while(i!=m_pHead)
{
Node *j=i->next;
delete i;
i=j;
}
delete m_pHead;
}
void List::pop()
{
if(empty())
{
cout<<"链表为空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
--m_nNum;
return;

}

}
void List::push(const int x,const int idx)//在idx位置后插入x
{

if(m_nNum==0)
{
Node *idx_node=new Node;
m_pHead->next=idx_node;
idx_node->data=x;
idx_node->next=m_pHead;

}
else
{
Node *tmp=m_pHead;
for(int i=0;i<idx;++i)
{
tmp=tmp->next;

}
Node *tmpnext=tmp->next;
Node *idx_node=new Node;
tmp->next=idx_node;
idx_node->data=x;
idx_node->next=tmpnext;
}
++m_nNum;
}
void List::push(const int x)
{
push(x,m_nNum);
}
void List::deletex (int x)//删除值为x的所有点
{
Node *tmp=m_pHead;
int idx=0;
while(idx<m_nNum)
{
Node *preNode=tmp;
tmp=tmp->next;
if(tmp->data==x)
{
Node*tmpNext=tmp->next;
tmp->next=tmpNext;
delete tmp;
tmp=tmpNext;
++idx;
}
tmp=tmp->next;
++idx;

}

}
inline int List::top ()
{
if(empty())
{
cout<<"空链表"<<endl;
return false;
}
return m_pHead->next->data ;

}
inline bool List::empty()
{
return m_nNum==0;
}
int List::operator <<(int x)
{
deletex(x);
return 0;
}
int List::operator >>(int x)
{
push(x);
return 0;
}
#endif
////deque.h
#ifndef QUEUE_H
#define QUEUE_H
#include "list.h"
class Queue:public List
{
public:
Queue(){}
Queue(Queue&);

virtual void pop();
virtual void push(int x);
virtual int top();

};
Queue::Queue(Queue&rhs)
{
if(this->get_num!=rhs.get_num)
{
cout<<"队列大小不同，不能复制"<<endl;
}
else
{
Node*tmp1=m_pHead->next ;
Node*tmp2=rhs.m_pHead->next;
while(tmp1!=m_pHead)
{
tmp1->data=tmp2->data;
tmp1=tmp1->next;
tmp2=tmp2->next;
}
}
}
void Queue::pop()
{
if(empty())
{
cout<<"队列为空"<<endl;
return ;
}
else
{
Node*tmp=m_pHead->next->next ;
delete m_pHead->next ;
m_pHead->next=tmp;
return;
--m_nNum;
}

}
int Queue::top()
{
if(empty())
{
cout<<"队列为空"<<endl;
return false;
}
return m_pHead->next->data ;

}
void Queue::push(int x)
{
Node *new_node=new Node;
Node *tmp=m_pHead;
for(int i=0;i<m_nNum;++i)
{
tmp=tmp->next;
}
tmp->next=new_node;
new_node->next =m_pHead;
new_node->data =x;
++m_nNum;
}
#endif
///main.cpp
/*--------------------------
这个主函数用于测试list
#include"list.h"
#include<iostream>
using namespace std;
int main()
{
List xx;
if(xx.empty())
cout<<"空"<<endl;
for(int i=0;i<3;++i)
xx.push(i);
cout<<xx.top()<<endl;
xx.pop();
cout<<xx.top()<<endl;

return 0;

}
-----------------------------------*/

#include "queue.h"
#include<iostream>
using namespace std;
int main()
{
List *xx=new Queue;//检验多态
xx->pop();
for(int i=0;i<3;++i)
xx->push(i);
cout<<xx->top()<<endl;
xx->pop();
cout<<xx->top()<<endl;
return 0;

}