队列的链式存储结构及其实现
程序员文章站
2024-03-01 11:58:58
...
队列也是一种特殊的线性表,只允许在一端进行插入操作,在另一端进行删除操作。允许插入的一段为对尾,允许删除的一端为队头。本次记录的是队列的链式存储结构以及实现。该存储结构有两个指针,一个指向头节点,称为头指针(front);一个指向队尾,称为尾指针(rear)。当front==rear时,表示空队列。当需要在队列中插入元素时,需要将队尾结点指向新插入的结点,然后将尾指针指向新插入的结点。当要在队列中进行删除操作时,只需让头指针指向队头结点的下一个结点即可。实现代码如下:
#include <iostream>
#include<stdlib.h>
using namespace std;
typedef struct QNode //定义一个连队列的结点
{
int data;
struct QNode *next;
}QNode;
typedef struct //定义链队列的数据结构
{
QNode *front;
QNode *rear;
}LinkQueue;
// 构造一个空队列q
LinkQueue *InitQueue(LinkQueue *q)
{
QNode *tmp = (QNode*)malloc(sizeof(QNode));
q->front = tmp;
q->rear = tmp;
q->front->next = NULL;
return q;
}
// 元素入队
LinkQueue *EnQueue(LinkQueue *q, int e)
{
QNode *p = (QNode*)malloc(sizeof(QNode));//为插入节点分配空间
if(!p)
{//分配空间失败
cout<<"插入节点内存分配失败!"<<endl;
}
else
{ //建节点
p->data = e; //为插入节点数据域赋值
p->next = NULL;//为插入节点指针域赋值
//实现插入
q->rear->next = p;//插入到队尾
q->rear = p;//队尾指针重新指向新任队尾
}
return q;
}
//元素出队
LinkQueue *DeQueue(LinkQueue *q)
{
QNode *p;
if(q->front == q->rear)
{
cout<<"链队列已空,不可再执行删除操作!"<<endl;
}
else
{
p = q->front->next;//将欲删除的队头结点暂存给p
int e = p->data;//把队头数据赋给e
cout <<"delete: " << e <<endl;
q->front->next = p->next;//删除,将原队头结点的后继p->next赋值给头结点后继
if(q->rear == p) //此时链队列只存在一个元素结点
{
//若队头就是队尾,则删除后将rear指向头结点
cout<<"链队列数据全部删除完毕!"<<endl;
q->rear = q->front;
}
free(p);
}
return q;
}
//返回队头元素
void GetQHead(LinkQueue *q)
{
QNode *p;
if(q->front == q->rear)
{
cout<<"链队列为空,无法返回队头数据"<<endl;
}
else
{
p = q->front->next;//队头
cout<< "队头元素:" << p->data <<endl;
}
}
//求队列长度
void QueueLength(LinkQueue *q)
{
int length = 0;
QNode *p;
p = q->front->next;//队头
while(p)
{
length++;
p = p->next;
}
cout<<"队列长度:"<< length << endl;
}
//打印。带头结点,真正存储元素的位置从头结点下一位置(队头)开始!!!
void PrintQueue(LinkQueue *q)
{
QNode *p;//队头
p = q->front->next;//头结点的下一节点,即为队头!!!
while(p)
{//从队头开始,依次往后遍历
cout<< p->data <<" ";
p = p->next;
}
cout << endl;
}
int main()
{
LinkQueue q ;
InitQueue(&q);
EnQueue(&q, 1);
PrintQueue(&q);
EnQueue(&q, 2);
PrintQueue(&q);
EnQueue(&q, 3);
PrintQueue(&q);
EnQueue(&q, 4);
PrintQueue(&q);
GetQHead(&q);
QueueLength(&q);
cout<<"***************"<<endl;
DeQueue(&q);
PrintQueue(&q);
GetQHead(&q);
DeQueue(&q);
PrintQueue(&q);
GetQHead(&q);
DeQueue(&q);
PrintQueue(&q);
DeQueue(&q);
PrintQueue(&q);
QueueLength(&q);
cout<<"***************"<<endl;
DeQueue(&q);
cout<<"***************"<<endl;
return 0;
}
运行结果截图:
上一篇: WIN32 基础控件的使用