1.隊列存在的實現方式及其存在意義

1.1為什么隊列使用單鏈表實現更好

1. 動態內存分配：鏈表在C語言中通常使用動態內存分配，這意味著可以在運行時根據需要動態地添加或刪除節點。這對于實現一個動態大小的隊列非常有用，因為隊列的大小可以在運行時變化。相比之下，數組的大小通常是固定的，需要在編譯時確定，這可能會限制隊列的靈活性。
2. 插入和刪除效率：在鏈表中，插入和刪除操作的時間復雜度為O(1)（在已知位置的情況下）。這意味著在鏈表的頭部或尾部添加或刪除節點非常高效。由于隊列是一種先入先出（FIFO）的數據結構，我們通常在隊列的尾部添加元素（入隊），并在頭部刪除元素（出隊）。因此，使用鏈表實現隊列可以充分利用其高效的插入和刪除操作。
3. 空間效率：鏈表只存儲節點本身的數據和指向下一個節點的指針，不需要像數組那樣預留一定的空間。這使得鏈表在存儲大量數據時更為空間高效.

1.2 隊列存在的意義

無論是棧,隊列,抑或是樹,它們基本都是由順序表,鏈表這些基本的元素構成的,并且人們將棧,隊列等一些數據結構發明出來也是為了根據人類的需求解決人類的一些問題,舉一個例子,醫院叫號排隊,為了防止有些人亂插隊從而引起的不必要的糾紛,于是以數據結構隊列為基本原理開發出有關排隊就醫的系統?

2.有關隊列的一些基本操作如何使用c語言代碼將其具現化

2.1如何寫一個隊列的結點

typedef int QDataType;
typedef struct QueueNode
{
?? ?int val;
?? ?struct QueueNode* next;
}QNode;

typedef struct Queue
{
?? ?QNode* phead; // 指向隊列頭部的指針 ?
?? ?QNode* ptail; ?// 指向隊列尾部的指針 ?
?? ?int size;
} Queue;

如果只是寫一個隊列的結點

然后在之后的對隊列的操作每次都去再設置一個頭指針和尾指針如果我們需要去找隊列的尾結點,那么就需要尾指針每次都從頭開始去遍歷整個鏈表的結點,但是這樣做的話時間復雜度便可以來到O(n),是不合情的

所以我們在最初設置隊列的結點相關基礎信息的時候就連帶著將它的頭指針和尾指針一并設置好.

設置兩個結點指針phead和ptail,例如我們每次進行一次尾插操作,就讓ptail指向新的尾結點,如此一來,ptail便一直指向尾結點,每當我們需要取去尋找尾結點是,可以直接使用ptail,就不需要再去從頭開始遍歷了.

2.2隊列的初始化操作

void QueueInit(Queue* pq)
{
?? ?assert(pq);//pq是指向結構體的指針
?? ?pq->phead = NULL;
?? ?pq->ptail = NULL;
?? ?pq->size = 0;
}

2.3隊列的銷毀操作

//銷毀操作
void QueueDestroy(Queue* pq)
{
?? ?assert(pq);
?? ?QNode* cur = pq->phead;//從頭開始銷毀,和出隊一樣
?? ?while (cur != NULL)
?? ?{
?? ??? ?QNode* nexttemp = cur->next;
?? ??? ?free(cur);
?? ??? ?cur = nexttemp;
?? ?}

?? ?pq->phead = pq->ptail = NULL;
?? ?pq->size = 0;
}

?QNode* nexttemp = cur->next;

這一步的意思是為了保證在將cur目前所指向的結點刪除以后還可以定位到原被刪除結點的下一個結點,所以事先將下一個結點cur->next用創建的臨時變量nexttemp保存起來,待目前結點被刪除以后,cur又快速指向下一個結點cur->next結點.

2.4入隊操作

//入隊
void QueuePush(Queue* pq,QDataType x)
{
?? ?assert(pq);
?? ?QNode* newnode = (QNode*)malloc(sizeof(QNode));
?? ?if (newnode == NULL)
?? ?{
?? ??? ?perror("malloc fail");
?? ??? ?return;
?? ?}
?? ?newnode->val = x;
?? ?newnode->next = NULL;
?? ?if (pq->ptail = NULL)//啥都沒有
?? ?{
?? ??? ?pq->ptail = pq->phead = newnode;

?? ?}
?? ?else//本來就有結點
?? ?{
?? ??? ?pq->phead->next = newnode;
?? ??? ?pq->ptail = newnode;
?? ?}
?? ?pq->size++;
}

2.5出隊操作

//出隊
void QueuePop(Queue* pq)
{
?? ?assert(pq);
?? ?//暴力檢查
?? ?//至少要有一個結點才可以進行銷毀操作
?? ?assert(pq->phead!=NULL);
?? ??
?? ?if (pq->phead->next == NULL)
?? ?{
?? ??? ?free(pq->phead);
?? ??? ?pq->phead = pq->ptail = NULL;
?? ?}
?? ?else
?? ?{
?? ??? ?QNode* nexttemp = pq->phead->next;
?? ??? ?free(pq->phead);
?? ??? ?pq->phead = nexttemp;
?? ?}
?? ?pq->size--;
}

2.6取頭操作

//取頭
QDataType ?QueueFront(Queue* pq)
{
?? ?assert(pq);
?? ?//要有首結點才可以進行取頭操作
?? ?assert(pq->phead != NULL);
?? ?return pq->phead->val;
}

2.7取尾操作

//取尾
QDataType QueueBack(Queue* pq)
{
?? ?assert(pq);
?? ?//要有尾結點才可以進行取尾操作
?? ?assert(pq->ptail != NULL);
?? ?return pq->ptail->val;
}