目录
队列的概念及结构
队列：只允许一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质(First In First Out)
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为对头。
队列的实现
顺序表和链表都可以实现，但是如果使用顺序结构实现，出队列在数组第一个位置出，出完之后还得将后面的数据往前挪一格，使得顺序结构效率很低，所以队列常用链式结构来实现(此篇博客使用的是无头结点的链表来实现)。
队列的创建
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; //用无头结点的链表来实现队列，创建一个结构体来存队列的头尾指针 //可以有效的避免形参需要二级指针的问题 typedef struct Queue { QNode* head; QNode* tail; }Queue;
注意： 在main函数中，直接定义Queue类型的变量，函数传参时，就传变量的地址。
队列初始化
void QueueInit(Queue *pq ) { assert(pq); pq->head = NULL; pq->tail = NULL; }
从队尾入队列
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->data = x; if (!pq->head)//队列为空时 { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->tail->next = NULL; }
从队头出队列
void QueuePop(Queue* pq) { assert(pq); assert(pq->head); QNode* next = pq->head->next; if (!next)//链表只有一个节点，需要对尾指针进行处理 { free(pq->head); pq->head = pq->tail = NULL; } else//链表有两个以上节点，不需要对尾指针进行处理 { free(pq->head); pq->head = next; } }
求队头数据
QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }
求队尾数据
int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
求队列长度
int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
判断队列是否为空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
销毁队列
void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
测试
int main() { Queue q; QueueInit(&q); while (1) { int x; scanf("%d", &x); if (x == -1) break; QueuePush(&q,x); } printf("%d\n", QueueSize(&q)); while (q.head) { printf("%d ",QueueFront(&q)); QueuePop(&q); } }
在vs2019上的编译结果：
