1.隊列的概念以及結(jié)構(gòu)

隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFo(Frist in Frist out)的特性

入隊列：進行插入才操作的一端稱為隊尾

出隊列：進行刪除操作的一端稱為隊頭

2.隊列的實現(xiàn)

隊列也可以使用數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會很低

隊列常見的基本操作：

//初始化
void QueueInit(Queue* pq);
//清空隊列成員
void QueueDestroy(Queue* pq);
//隊尾插入元素
void QueuePush(Queue* pq, QDataType x);
//刪除隊隊頭元素，隊列先進先出
void QueuePop(Queue* pq);
//獲取隊頭元素
int QueueFront(Queue * pq);
//獲取隊尾元素
int QueueBack(Queue* pq);
//獲取隊列中有效與元素個數(shù)
int QueueSize(Queue* pq);
//查看隊列是否為空
bool QueueEmpty(Queue* pq);

每個功能的實現(xiàn)以及解釋

實現(xiàn)隊列這里我們使用的是動態(tài)順序表

->1.初始化隊列

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

->2.清空隊列成員

//清空隊列成員
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;//QNode* cur = pq->head->next;while (cur){/*free(pq->head);pq->head = cur;cur = cur->next;*/QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

->3.隊尾插入元素

//隊尾插入元素
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("QueuePsuh::malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

->4.刪除隊隊頭元素，隊列先進先出

//刪除隊列成員，隊列先進先出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//第一種方法//Queue* cur = pq->head;//if (cur->next == NULL)//{//	free(cur);//	pq->head = pq->tail = NULL;//}/*else{pq->head = cur->next;free(cur);cur = NULL;}*///第二種方法QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}

->5.獲取隊頭元素

//獲取隊頭成員
int QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}

->6.獲取隊尾元素

//獲取隊尾成員
int QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

->7.獲取隊列中有效元素個數(shù)

//獲取隊列中有效元素個數(shù)
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

->8.查看隊列是否為空

//查看隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

3.完整代碼

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>typedef int QDataType;typedef struct QListNode 
{struct QListNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;QDataType size;
}Queue;//初始化
void QueueInit(Queue* pq);
//清空隊列成員
void QueueDestroy(Queue* pq);
//隊尾插入隊列
void QueuePush(Queue* pq, QDataType x);
//刪除隊隊頭元素，隊列先進先出
void QueuePop(Queue* pq);
//獲取隊頭元素
int QueueFront(Queue * pq);
//獲取隊尾元素
int QueueBack(Queue* pq);
//獲取隊列中有效與元素個數(shù)
int QueueSize(Queue* pq);
//查看隊列是否為空
bool QueueEmpty(Queue* pq);

Queue.c

#include "queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//銷毀隊列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;//QNode* cur = pq->head->next;while (cur){/*free(pq->head);pq->head = cur;cur = cur->next;*/QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}//插入隊列成員
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (NULL == newnode){perror("QueuePsuh::malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//刪除隊列成員，隊列先進先出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//Queue* cur = pq->head;//if (cur->next == NULL)//{//	free(cur);//	pq->head = pq->tail = NULL;//}/*else{pq->head = cur->next;free(cur);cur = NULL;}*/QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}//獲取隊頭成員
int QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}//獲取隊列中有效元素個數(shù)
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//獲取隊尾成員
int QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//查看隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0; //pq->head == NULL && pq->tail == NULL
}

test.c

#include "queue.h"int main()
{Queue st;QueueInit(&st);QueuePush(&st, 1);QueuePush(&st, 2);QueuePush(&st, 3);QueuePush(&st, 4);QueuePush(&st, 5);while (!QueueEmpty(&st)){printf("%d ", QueueFront(&st));QueuePop(&st);}printf("\n");return 0;
}

測試結(jié)果: