C++实现链表队列

时间:2022-04-19 17:41:25
   今天一个学妹问了我一个上机题,写一个链表队列,从10-20000之间取500次随机数,后一个比前一个大至少5就进入队列,否则略去。
然后在这个队列中取出数据,求和以及平均值。关键就是链表队列的实现,下面贴上代码和注释。
#include <iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;
class LinkNode
{
public:
int data;//存放当前节点的数据
LinkNode * next;//指向下一个节点
LinkNode (const int el,LinkNode *ptr = 0){//构造函数 传入数据值以及下一个节点
data = el;
next = ptr;
}
};
class LinkQueue
{
private:
LinkNode *rear; //指向尾巴节点
LinkNode *front; //指向头节点
public:
bool IsEmpty(); //判断是否为空
LinkQueue(); //构造函数 无参
bool EnQueue(const int item); //进入队列
bool DeQueue(int & item); //取出队列的头部元素并且删除 传入引用 这样就可以将取出来的值储存在item中
int size; //当前储存元素的个数
};

bool LinkQueue::IsEmpty(){
return front==NULL; //通过头结点是否为空来确定队列链表为不为空
}
LinkQueue::LinkQueue(){
size=0; //初始化的时候size赋值为0 即队列链表为空
front=rear=NULL; //头结点和尾节点相等 且均指向空
}


bool LinkQueue::EnQueue (const int item)
{
if (IsEmpty()) //当链表为空时开辟新节点 并且让头指针和尾指针均指向该节点
{
front = rear = new LinkNode(item, NULL);
}
else //不为空的时候 开辟新节点,将尾指针往下移
{
rear->next = new LinkNode(item, NULL);
rear = rear->next;
}
size++; //储存的个数加1
return true;
}

bool LinkQueue:: DeQueue(int &item)
{
LinkNode * temp; //创建一个中间节点 来完成节点的删除
item = front->data; //取出头结点的data值 放在item中
temp = front;
front = front->next; //删除当前front
delete temp;
if (IsEmpty())
{
return false; //链表队列为空的时候返回false 删除失败
}
size--; //储存元素个数减1
return true;
}

int main(int argc, const char * argv[]) {
int old_num=0;
int new_num=0;
LinkQueue queue;
srand(time(NULL));
int i=0;
while(i<500)
{
new_num=(rand()%19991+10);
if (new_num>old_num+5)
{
old_num=new_num;
cout<<new_num<<"入队列"<<endl;
queue.EnQueue(new_num);
}
i++;
} //生成该链表队列的过程
int size;
size=queue.size;
int sum=0;
int average=0;
int max,min;
int num;
while (queue.DeQueue(num)) //挨个取出链表队列的成员进行操作
{
sum+=num;
}
average=sum/size;
cout<<"共"<<size<<"个数"<<endl;
cout<<"和为"<<sum<<endl;
cout<<"平均值为"<<average<<endl;
}
有错误或者有一些需要优化的地方请指出。