完整代碼鏈接：DataStructure: 基本數據結構的實現。 (gitee.com)

目錄

一、隊列的概念：

二、隊列的實現：

使用鏈表實現隊列：?

1.結構體設計：

2.初始化：

3.銷毀：

4.入隊：

5.出隊：

6.獲取隊頭數據：

7.獲取隊尾數據：

8.判空：

9.查看隊列長度：

---

一、隊列的概念：

隊列是一種特殊的線性表，其只允許在一端執行插入數據操作，在另一端執行刪除數據操作。隊列中的數據元素遵循先進先出 FIFO(First In First Out) 原則。

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

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

二、隊列的實現：

同棧一樣，數組和鏈表都可以實現隊列。但是，使用鏈表的結構實現隊列會更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。

使用鏈表實現隊列：?

1.結構體設計：

typedef int QueueDataType;typedef struct QueueNode//隊列里單個結點的設計
{struct QueueNode* _next;QueueDataType _data;
}QueueNode;typedef struct Queue//隊列結構體的設計
{QueueNode* _head;QueueNode* _tail;
}Queue;

2.初始化：

void QueueInit(Queue* pq)
{assert(pq);//隊列內還沒有數據pq->_head = NULL;pq->_tail = NULL;
}

3.銷毀：

void QueueDestory(Queue* pq)
{assert(pq);QueueDataType* tmp = NULL;//指向要被釋放的結點while (pq->_head != NULL){tmp = pq->_head;pq->_head = pq->_head->_next;free(tmp);}pq->_tail = NULL;//當隊列里所有結點都被釋放時，pq->_tail所指向的結點也被釋放了
}

4.入隊：

void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){printf("內存不足\n");exit(-1);}newNode->_data = x;newNode->_next = NULL;if (pq->_head == NULL)//隊列里沒有數據{pq->_head = pq->_tail = newNode;}else{pq->_tail->_next = newNode;pq->_tail = newNode;}
}

5.出隊：

void QueuePop(Queue* pq)
{assert(pq);assert(pq->_head);QueueNode* next = pq->_head->_next;free(pq->_head);pq->_head = next;if (pq->_head == NULL)//當沒有了數據{pq->_tail = NULL;}
}

6.獲取隊頭數據：

QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->_head);return pq->_head->_data;
}

7.獲取隊尾數據：

QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->_tail);return pq->_tail->_data;
}

8.判空：

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->_head == NULL ? 1 : 0;
}

9.查看隊列長度：

int QueueSize(Queue* pq)
{assert(pq);QueueNode* cur = pq->_head;int size = 0;while (cur != NULL){size++;cur = cur->_next;}return size;
}