目录

一、队列的定义

二、队列的实现

1.使用链表来实现队列

2.实现队列的接口

初始化队列 void QueueInit(Queue *pq)

队尾入队列 void QueuePush(Queue *pq,QDataType data)

队头出队列 void QueuePop(Queue *pq)

获取队列头部元素 QDataType QueueFront(Queue *pq)

获取队列尾部元素 QDataType QueueBack(Queue *pq)

获取队列中的有效元素个数 int QueueSize(Queue *pq)

检测队列是否为空，bool QueueEmpty(Queue *q)

销毁队列 void QueueDestroy(Queue *q)

总结

---

---

 

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、队列的定义

队列：只允许在一端进行插入，另外一端进行删除数据的特殊线性表，队列具有先进先出

入队列：在进行插入操作的一端称为队尾

出队列：在进行删除操作的一端称为队头

二、队列的实现

队列可以使用数组和链表实现，使用数组的结构时，出队列在数据头上出数据，效率低

1.使用链表来实现队列

typedef int QDataType;
//链式结构，表示队列
typedef struct QueueNode
{struct QueueNode * next;QDataType data;
}QNode;//队列的结构
typedef struct Queue
{QNode * head;QNode * tail;int size;
}Queue;

2.实现队列的接口

初始化队列 void QueueInit(Queue *pq)

void QueueInit(Queue *pq)
{assert(pq);pq->head=NULL;pq->tail=NULL;pq->size = 0;
}

队尾入队列 void QueuePush(Queue *pq,QDataType data)

void QueuePush(Queue *pq,QDataType x)
{assert(pq);//插入节点，自己构造一个新节点QNode * newnode =(QNode *)malloc(sizeof(QNode));if(newnode ==NULL){perror("error");exit(-1);}newnode->data = x;newnode->next = NULL;//要考虑是否为空队列if(pq->tail ==NULL){pq->head = pq->tail = newnode;}else{//尾插pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

队头出队列 void QueuePop(Queue *pq)

void QueuePop(Queue *pq)
{assert(pq);assert(!QueueEmpty(pq));//特殊情况，要考虑只有一个节点,释放之后，head指向空，tail为野指针if(pq->head->next ==NULL){free(pq->head);pq->head = pq->tail = NULL;}//保存当前节点，head指向下一个,释放当前节点else{   QNode * del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}

获取队列头部元素 QDataType QueueFront(Queue *pq)

QDataType QueueFront(Queue *pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

获取队列尾部元素 QDataType QueueBack(Queue *pq)

QDataType QueueBack(Queue *pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

获取队列中的有效元素个数 int QueueSize(Queue *pq)

如果使用遍历，size++的方式，时间复杂度为O(n)；如果使用全局变量size来计算个数，会在有多个队列的时候容易混乱。所以在定义队列的时候，增加一个size变量，插入的时候size++,删除的时候size--，计算个数的时候可以直接返回size的大小，此时时间复杂度为O(1)

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

检测队列是否为空，bool QueueEmpty(Queue *q)

如果为空返回非0结果，如果不为空返回0 

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

销毁队列 void QueueDestroy(Queue *q)

 void QueueDestroy(Queue *q)
{QNode * cur = pq->head;while(cur !=NULL){QNode * cur = pq->head;while(cur!=NULL){QNode * del = cur;cur = cur->next;free(del);}//删除完了之后，head和tail为野指针，所以需要置空pq->head = pq->tail = NULL;
}

---

总结

本文主要记录了用链表实现队列，以及对队列的增删改查，技术有限，如有错误请指正。