C語言數據結構—

0.前言

1.隊列的基本概念

2.隊列的實現

2.1實現方式

2.2具體實現

3.隊列的應用場景

4.一道隊列的算法題（LeetCode225. 用隊列實現棧）

5.結語

（圖像由AI生成）?

0.前言

在計算機科學領域，數據結構是組織和存儲數據的一種方式，它允許我們以有效的方式對數據進行訪問和修改。今天，我們將探討一種基礎但極其重要的數據結構——隊列。通過學習，我們不僅會了解隊列的理論基礎，還會深入其實現方式，探討其應用場景，并通過解決一個實際問題來鞏固我們的理解。

1.隊列的基本概念

隊列是一種基礎但非常重要的線性數據結構，它在計算機科學和編程中有著廣泛的應用。隊列遵循先進先出（FIFO, First-In-First-Out）的原則，這意味著最先被加入隊列的元素將是最先被移除的。這種特性使得隊列非常適合于那些需要按照順序處理元素的場景。

基本操作

隊列的操作通常包括：

入隊（Push）：在隊列的末尾添加一個新的元素。
出隊（Pop）：移除隊列前端的元素。
查看隊首（Peek/Front）：獲取隊列前端的元素，但不移除它。
檢查隊列是否為空（IsEmpty）：判斷隊列中是否有元素。
獲取隊列大小（Size）：獲取隊列中元素的數量。

特性

有序性：隊列保持元素的添加順序，確保第一個加入的元素將是第一個被移除。
動態性：隊列可以動態地增長和縮減，隨著元素的入隊和出隊操作。
操作限制：在隊列中，只能在一端（隊尾）添加元素，在另一端（隊首）移除元素。

2.隊列的實現

2.1實現方式

隊列可以通過不同的方式實現，其中最常見的兩種是：

數組實現：使用數組存儲隊列中的元素。這種實現方式簡單直觀，但可能需要處理數組的動態擴容問題或者實現循環隊列來優化空間利用。
鏈表實現：使用鏈表存儲隊列中的元素。鏈表實現的隊列可以動態地增長，不需要擔心空間限制，但每次操作可能涉及更多的內存分配和釋放。

綜合以上因素以及隊列只需要“尾插”和“頭刪”的特性，我們最終決定用帶頭單向不循環鏈表來實現隊列。

2.2具體實現

在這一部分，我們將詳細介紹如何使用不帶頭單向不循環鏈表來實現隊列。這種實現方式利用了鏈表的動態分配特性，允許隊列在運行時根據需要增長或縮減。下面是具體的實現方法：

隊列的結構定義

首先，我們定義了兩個結構體：queueNode 和 queue。queueNode 結構體表示隊列中的節點，包含數據域 _data 和指向下一個節點的指針 _next。queue 結構體則表示隊列本身，包含指向隊列頭部和尾部的指針 _head 和 _tail。

typedef struct queueNode
{QDataType _data;           // 節點存儲的數據struct queueNode* _next;   // 指向下一個節點的指針
} queueNode;typedef struct queue
{queueNode* _head;          // 指向隊列頭部的指針queueNode* _tail;          // 指向隊列尾部的指針
} queue;

初始化隊列

queueInit 函數用于初始化隊列，設置 _head 和 _tail 指針都為 NULL，表示一個空隊列。

void queueInit(queue* pq)
{assert(pq);pq->_head = pq->_tail = NULL;
}

銷毀隊列

queueDestroy 函數用于銷毀隊列，釋放所有節點占用的內存，并將 _head 和 _tail 指針重置為 NULL。

void queueDestroy(queue* pq)
{queueNode* cur = pq->_head;while (cur){queueNode* next = cur->_next;free(cur);cur = next;}pq->_head = pq->_tail = NULL;
}

入隊操作

queuePush 函數用于在隊列尾部添加新節點。如果隊列為空，新節點即成為隊列的頭部和尾部；否則，將新節點鏈接到原尾節點的 _next 指針，并更新 _tail 指針。

void queuePush(queue* pq, QDataType x)
{assert(pq);queueNode* newNode = (queueNode*)malloc(sizeof(queueNode));if (newNode == NULL){printf("malloc fail\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;}
}

出隊操作

queuePop 函數用于移除隊列頭部的節點。如果隊列在移除節點后變為空，需要同時將 _tail 指針置為 NULL。

void queuePop(queue* pq)
{assert(pq && pq->_head);queueNode* next = pq->_head->_next;free(pq->_head);pq->_head = next;if (pq->_head == NULL){pq->_tail = NULL;}
}

另外我們提供了一些基礎的隊列操作函數，如 queueFront 和 queueBack 分別返回隊列的頭部和尾部元素，queueEmpty 檢查隊列是否為空，queueSize 返回隊列中元素的數量。完整代碼如下：

//queue.h
#pragma once
#ifndef QUEUE_H
#define QUEUE_H
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
typedef struct queueNode
{QDataType _data;struct queueNode* _next;
}queueNode;typedef struct queue
{queueNode* _head;queueNode* _tail;
}queue;void queueInit(queue* pq);
void queueDestroy(queue* pq);
void queuePush(queue* pq, QDataType x);
void queuePop(queue* pq);
QDataType queueFront(queue* pq);//返回隊頭元素
QDataType queueBack(queue* pq);//返回隊尾元素
int queueEmpty(queue* pq);//判斷隊列是否為空,為空返回1，否則返回0
int queueSize(queue* pq);//返回隊列中元素的個數#endif // !QUEUE_H

//queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void queueInit(queue* pq)
{assert(pq);pq->_head = pq->_tail = NULL;
}void queueDestroy(queue* pq)
{queueNode* cur = pq->_head;while (cur){queueNode* next = cur->_next;free(cur);cur = next;}pq->_head = pq->_tail = NULL;
}void queuePush(queue* pq, QDataType x)
{assert(pq);queueNode* newNode = (queueNode*)malloc(sizeof(queueNode));if (newNode == NULL){printf("malloc fail\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;}
}void queuePop(queue* pq)
{assert(pq && pq->_head);queueNode*next = pq->_head->_next;free(pq->_head);pq->_head = next;if(pq->_head==NULL){pq->_tail = NULL;}
}QDataType queueFront(queue* pq)
{assert(pq && pq->_head);return pq->_head->_data;
}QDataType queueBack(queue* pq)
{assert(pq && pq->_tail);return pq->_tail->_data;
}int queueEmpty(queue* pq)
{assert(pq);return pq->_head == NULL ? 1 : 0;
}int queueSize(queue* pq)
{assert(pq);queueNode* cur = pq->_head;int count = 0;while (cur){count++;cur = cur->_next;}return count;
}

3.隊列的應用場景

隊列作為一種基本的數據結構，在計算機科學及其相關領域中有著廣泛的應用。其先進先出（FIFO）的特性使得隊列非常適合于處理需要按順序執行的任務。以下是隊列在不同領域中的一些典型應用場景：（以下查詢自網絡）

操作系統
在操作系統中，隊列被用于多種任務調度和管理過程。例如，CPU調度算法如先來先服務（FCFS）直接使用隊列的FIFO特性來管理進程。進程控制塊（PCB）根據進程到達的順序排隊等待CPU時間。此外，I/O請求管理也常使用隊列，設備請求按照到達順序排隊等待處理。
網絡通信
在網絡通信中，隊列用于管理數據包的傳輸。數據包在進入網絡設備如路由器或交換機時排隊等待處理。這種機制幫助控制網絡擁塞，確保數據包以合理的順序被轉發。
異步編程
在異步編程模型中，隊列用于管理事件或消息。應用程序將事件放入隊列中，事件循環依次處理這些事件。這種模型在JavaScript等語言的事件驅動編程中尤為常見。
打印任務管理
在打印任務管理中，打印任務按照提交的順序排隊等待打印。這確保了文檔將按照用戶提交的順序被打印，避免了因資源競爭造成的混亂。

4.一道隊列的算法題（LeetCode225. 用隊列實現棧）

學習了棧和隊列的知識之后，我們不妨來看一道簡單的算法題——用隊列實現棧。（鏈接在上面）

原題大致如下：

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。

實現?MyStack?類：

void push(int x)?將元素 x 壓入棧頂。
int pop()?移除并返回棧頂元素。
int top()?返回棧頂元素。
boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。

注意：

你只能使用隊列的基本操作 —— 也就是?push to back、peek/pop from front、size?和?is empty?這些操作。
你所使用的語言也許不支持隊列。?你可以使用 list （列表）或者 deque（雙端隊列）來模擬一個隊列?, 只要是標準的隊列操作即可。

以下是用C語言的實現代碼。由于C語言庫函數沒有“隊列”，我們只能先“造”出一個隊列。

typedef int QueueDataType;// 定義隊列節點結構體
typedef struct QueueNode
{QueueDataType data;         // 節點存儲的數據struct QueueNode* next;     // 指向下一個節點的指針
} Node;// 定義隊列結構體
typedef struct Queue
{Node* head;                 // 指向隊列頭節點的指針Node* tail;                 // 指向隊列尾節點的指針size_t size;                // 隊列中元素的數量
} Queue;// 初始化隊列
void QueueInit(Queue* q)
{// 創建哨兵節點q->head = q->tail = (Node*)malloc(sizeof(Node));q->head->next = NULL;q->size = 0;
}// 向隊列中添加元素
void QueuePush(Queue* q, QueueDataType x)
{Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = x;newNode->next = NULL;q->tail->next = newNode;q->tail = newNode;q->size++;
}// 從隊列中移除元素
void QueuePop(Queue* q)
{assert(q->head->next != NULL); // 確保隊列非空Node* toDelete = q->head->next;q->head->next = toDelete->next;if (q->tail == toDelete) // 如果移除的是尾節點，更新tail指向哨兵節點{q->tail = q->head;}free(toDelete);q->size--;
}// 獲取隊列頭部元素
QueueDataType QueueFront(Queue* q)
{assert(q->head->next != NULL);return q->head->next->data;
}// 獲取隊列尾部元素
QueueDataType QueueBack(Queue* q)
{assert(q->head->next != NULL);return q->tail->data;
}// 檢查隊列是否為空
bool QueueEmpty(Queue* q)
{return q->head->next == NULL;
}// 獲取隊列中元素的數量
size_t QueueSize(Queue* q)
{return q->size;
}// 銷毀隊列，釋放內存
void QueueDestroy(Queue* q)
{while (q->head->next != NULL){QueuePop(q);}free(q->head);q->head = q->tail = NULL;
}// 定義棧結構體，內部使用兩個隊列實現
typedef struct {Queue q1;   // 主隊列Queue q2;   // 輔助隊列，用于實現棧的pop和top操作
} MyStack;// 創建并初始化棧
MyStack* myStackCreate() {MyStack* stack = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));QueueInit(&(stack->q2));return stack;
}// 向棧中添加元素
void myStackPush(MyStack* obj, int x) {if(QueueEmpty(&(obj->q2))) // 如果q2為空，向q1中添加元素{QueuePush(&(obj->q1), x);}else // 如果q1為空，向q2中添加元素{QueuePush(&(obj->q2), x);}
}// 從棧中移除元素
int myStackPop(MyStack* obj) {if(QueueEmpty(&(obj->q2))) // 如果q2為空，從q1中移動元素到q2，直到最后一個元素{while(obj->q1.size > 1){int num = QueueFront(&(obj->q1));QueuePop(&(obj->q1));QueuePush(&(obj->q2), num);}int ret = QueueFront(&(obj->q1));QueuePop(&(obj->q1));return ret;}else // 如果q1為空，從q2中移動元素到q1，直到最后一個元素{while(obj->q2.size > 1){int num = QueueFront(&(obj->q2));QueuePop(&(obj->q2));QueuePush(&(obj->q1), num);}int ret = QueueFront(&(obj->q2));QueuePop(&(obj->q2));return ret;}
}// 獲取棧頂元素
int myStackTop(MyStack* obj) {if(QueueEmpty(&(obj->q2))) // 如果q2為空，棧頂元素在q1的尾部{return QueueBack(&(obj->q1));}else // 如果q1為空，棧頂元素在q2的尾部{return QueueBack(&(obj->q2));}
}// 檢查棧是否為空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}// 銷毀棧，釋放內存
void myStackFree(MyStack* obj) {QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));free(obj);
}

實現原理

該實現策略涉及兩個隊列，q1 和 q2，它們交替作為主隊列和輔助隊列。這種方法的核心在于利用隊列的先進先出（FIFO）特性來模擬棧的后進先出（LIFO）特性。

Push 操作：總是向當前非空的隊列中添加新元素。如果兩個隊列都為空，則可以選擇任意一個隊列進行添加。這保證了所有元素都存儲在同一個隊列中，而另一個隊列處于空閑狀態，待下一次pop或top操作時使用。
Pop 操作：將主隊列中的所有元素（除最后一個元素）依次出隊并入隊到輔助隊列中，然后移除并返回主隊列中的最后一個元素。通過這種方式，可以實現棧的LIFO特性。操作完成后，主隊列和輔助隊列的角色會互換。
Top 操作：與pop操作類似，但是不移除最后一個元素，只返回其值。
Empty 操作：當兩個隊列都為空時，棧也為空。

代碼解析

在以上代碼中，Queue結構體用于實現隊列的基本功能，而MyStack結構體則使用兩個Queue實例來模擬棧的行為。

myStackPush函數向當前活躍的隊列中添加元素。
myStackPop函數通過將主隊列中的元素（除了最后一個）轉移到輔助隊列中，然后移除并返回最后一個元素，實現了棧的pop操作。此后，隊列的角色將互換。
myStackTop函數與myStackPop類似，但是在返回最后一個元素的值后，不會將其移除。
myStackEmpty函數檢查兩個隊列是否都為空，以確定棧是否為空。
myStackFree函數負責釋放兩個隊列和棧實例所占用的內存資源。