前言

? ? ? ? 隊列是一種特殊的線性表，它只允許在一端對數據進行插入操作，在另一端對數據進行刪除操作的特殊線性表，隊列具有先進先出的（FIFO）的?特性，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。

1.隊列的特性

? ? ? ? 隊尾：元素在隊尾入隊。插入操作。

? ? ? ? 隊頭：元素在隊頭出對。刪除操作。

如圖：

2.隊列的實現

?????????隊列可以用 數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低，需要挪動數據，因此這里采用鏈表的方式來進行隊列的實現。

//queue.h

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* _next;QDataType _data;
}QueueNode;
typedef struct  Queue//隊列的結構
{QueueNode* _head;//頭指針QueueNode* _tail;//尾指針
}Queue;void QueueInit(Queue* qu);//初始化棧void QueueDestory(Queue* qu);//摧毀棧void QueuePush(Queue* qu,QDataType data);//入隊void QueuePop(Queue* qu);//出隊QDataType QueueFront(Queue* qu);//返回隊頭元素
QDataType QueueBack(Queue* qu);//返回隊尾元素size_t QueueSize(Queue* qu);//隊列長度bool QueueEmpty(Queue* qu);//判斷隊列是否為空

//queue.c

void QueueInit(Queue* qu)//初始化棧
{qu->_head = qu->_tail = NULL;
}
void QueueDestory(Queue* qu)//摧毀棧
{//確保指針有效assert(qu);QueueNode* cur = qu->_head;while (cur){QueueNode* next = cur->_next;free(cur);}
}
void QueuePush(Queue* qu,QDataType data)//入隊
{if (qu->_head == NULL){qu->_head = (QueueNode*)malloc(sizeof(QueueNode));qu->_tail = qu->_head;qu->_head->_next = NULL;qu->_head->_data = data;}else{//尾部入數據QueueNode* cur = qu->_tail;QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));cur->_next = newNode;newNode->_next = NULL;qu->_tail = newNode;newNode->_data = data;}
}
void QueuePop(Queue* qu)//出隊
{//隊頭出數據QueueNode* head = qu->_head;qu->_head = head->_next;free(head);
}
QDataType QueueFront(Queue* qu)//返回隊頭元素
{return qu->_head->_data;
}
QDataType QueueBack(Queue* qu)//返回隊尾元素
{return qu->_tail->_data;
}
size_t QueueSize(Queue* qu)//隊列長度
{assert(qu);//確保指針存在QueueNode* cur = qu->_head;size_t size = 0;while (cur){++size;cur = cur->_next;}return size;
}
bool QueueEmpty(Queue* qu)//判斷隊列是否為空
{return !qu->_head;
}

?

3.測試部分

????????

void TestQueue()
{Queue qu;QueueInit(&qu);QueuePush(&qu, 1);QueuePush(&qu, 2);QueuePush(&qu, 3);QueuePush(&qu, 4);QueuePush(&qu, 5);QueuePush(&qu, 6);QueuePush(&qu, 7);QueuePush(&qu, 8);while (!QueueEmpty(&qu)){printf("%d ", QueueFront(&qu));QueuePop(&qu);}QueueDestory(&qu);
}

?