队列（链表）

爱被打了一巴掌 2021-09-15 23:14 404阅读 0赞

队列是具有两个特殊属性的链表。第一，新项只能添加到链表的末尾。第二，只能从链表的开头移除项。是一种“先进先出”的数据形式。

队列的操作有：初始化队列为空，确定队列为空，确定队列已满，确定队列中的项数，在队列末尾添加项，在队列开头删除项或返回该项的值以及清空队列。

运用链表表示队列的好处是，我们只需两个指针，一个指向队首，一个指向队尾即可。

首先考虑初始化，因为涉及该队列的类型，所以应以Queue的地址作为参数：

void InitializeQueue(Queue \*pq);

接下来测试改队列是否为空或已满：

int QueueIsFull(const Queue \*pq);

int QueueIsEmpty(const Queue \*pq);

返回队列的项数：

int QueueItemCount(const Queue \*pq);

在队尾进行添加，我们可以通过返回值表示是否添加成功：

int EnQueue(Item item,Queue \*pq)

删除队列的首项，可以这样定义下面的原型：

int DeQueue(Item \*pitem,Queue \*pq)

清空队列的函数原型如下：

void EmptyTheQueue(Queue \*pq)。

Queue内存储该队列的首指针、尾指针和项数，Item为该队列内存储的数据类型。

我们以一个整数为队列进行测试，所以应：

typedef   int    Item;

链表由节点组成，接下来定义节点：

typedef   struct   node

Item item;

struct node \*next;

\}Node;

队列只需存储首指针 、尾指针及项数，构成如下：

typedef   strucct queue

Node \*fronst;   //指向队列首项的指针

Node  \*rear;    //指向队列尾项的指针

int  items ；    //队列中的项数

代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int Item;
    #define MAXQUEUE 10            //队列中能存储的最多项数
    typedef struct node
    {
    	Item item;
    	struct node *next; 
    }Node;
    typedef struct queue
    {
    	Node *front;
    	Node *rear;
    	int items;		//队列中的项数 
    }Queue;
    void InitializeQueue(Queue * pq);//初始化队列 
    int QueueIsFull(const Queue *pq);//检查队列是否已满
    int  QueueIsEmpty(const Queue *pq);//检查队列是否为空
    int QueueItemCount(const Queue *pq);//返回队列中的项数
    int EnQueue(Item item,Queue *pq);//在队列末尾添加项
    int DeQueue(Item *pitem,Queue *pq);//从队列开头删除项
    void EmptyTheQueue(Queue *pq);//清空队列 
    
    
    /*前提：pq指向一个队列*/
    void InitializeQueue(Queue * pq)
    {
    	pq->front = pq->front =NULL;    //队列为空即首项和尾项为NULL
    	pq->items =0;                   //项数为0
    } 
    
    /*前提：pq指向已被初始化的队列*/
    int QueueIsFull(const Queue *pq)
    {
    	return pq->items==MAXQUEUE;       //队列中的项数是否达到所能存储的最大项
    }
    
    /*前提：pq指向已被初始化的队列*/
    
    int  QueueIsEmpty(const Queue *pq)
    {
    	return pq->items==0;              //队列中是否已存储
    }
    
    /*前提：pq指向已被初始化的队列*/
    int QueueItemCount(const Queue *pq)
    {
    	return pq->items;                //返回pq的项数
    }
    
    /*前提：pq指向已被初始化的队列,
            item实在队尾添加的项*/
    int EnQueue(Item item,Queue *pq)
    {
    	Node *pnew;
    	if(QueueIsFull(pq))               //如果队列已满，不能添加
    		return 0;
    	pnew=(Node *)malloc(sizeof(Node));
    	if(pnew==NULL)
    	{
    		printf("空间分配失败");
    		exit(1);
    	}
    	pnew->item=item;        
    	pnew->next=NULL;
    	if(QueueIsEmpty(pq))               //队列为空往队首添加
    		pq->front=pnew;
    	else
    		pq->rear->next=pnew;       //队列不为空往队尾添加
    	pq->rear=pnew;    
    	pq->items++;                        //添加后项数增加
    	return 1;
    }
    
    /*前提：pq指向已被初始化的队列*/
    int DeQueue(Item *pitem,Queue *pq)
    {
    	if(QueueIsEmpty(pq))                 //队列为空
    		return 0;
    	Node *pnew=pq->front;                //记录队首
    	*pitem=pq->front->item;              //返回队首存储的数据
    	pq->front=pq->front->next;           //首指针后移
    	free(pnew);                          //释放原队首
    	pq->items--;                         //项数减一
    	if(pq->items==0)                     //队列变空后，队首、队尾指针置NULL
    		pq->rear=NULL;
    	return 1;
    }
    
    /*前提：pq指向已被初始化的队列*/
    void EmptyTheQueue(Queue *pq)
    {	
            Item pitem;
    	while(!QueueIsEmpty(pq))
    		DeQueue(&pitem,pq);
    }