一 . 佇列的含義 以及 應用：
1.含義：佇列（queue）是在表的一端進行插入操作，另一端進行洗掉操作的線性表
2.資料進出順序為：先進先出，和日常排隊打飯一樣，先排隊的先打飯離開，
二. 佇列的存盤結構的選擇：
1.陣列：選用陣列來做堆疊的存盤結構，因為要在兩端都進行操作，所以避免不了挪動資料的這個弊端；
2.單鏈表：使用單鏈表時，先來考慮下，是頭插尾刪，還是頭刪尾插 ，使用頭插尾刪時，每次入隊時都得改變頭指標的指向，比較麻煩，因此采用頭刪尾插；
3.因此：綜合分析采用 單鏈表的頭刪尾插 比較合適，
三. 代碼實作
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}QNode;
typedef struct Queue
{
QNode *head;
QNode *tail;
}Queue;
void QueueInit(Queue *pq)//初始化
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
void QueueDestory(Queue *pq)//銷毀
{
assert(pq);
QNode *val = pq->head;
while (pq->head != NULL)
{
pq->head->next;
free(val);
}
}
void QueuePush(Queue *pq, int x)//入隊
{
assert(pq);
if (pq->head == NULL)
{
QNode *NewNode = (QNode *)malloc(sizeof(QNode));
NewNode->data = x;
NewNode->next = NULL;
pq->head = NewNode;
pq->tail = NewNode;
}
else
{
QNode *NewNode = (QNode *)malloc(sizeof(QNode));
NewNode->data = x;
NewNode->next = NULL;
pq->tail->next = NewNode;
pq->tail = NewNode;
}
}
void QueuePop(Queue *pq)//出隊
{
assert(pq);
QNode *val = pq->head;
if (pq->head == pq->tail)
{
pq->head = NULL;
pq->head = NULL;
free(val);
}
else
{
pq->head = pq->head->next;
free(val);
}
}
DataType QueueHead(Queue *pq)//取隊頭元素
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
bool QueueEmpty(Queue *pq)//檢測佇列是否為空
{
assert(pq);
return pq->head !=NULL;
}
DataType QueueSize(Queue *pq)//計算佇列中元素個數
{
assert(pq);
QNode *val = pq->head;
int size = 0;
while(val)
{
size++;
val=val->next;
}
return size;
}
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("佇列中%d個元素\n",QueueSize(&q));
printf("元素%d出隊\n", QueueHead(&q));
QueuePop(&q);
printf("佇列中%d個元素\n",QueueSize(&q));
printf("元素%d出隊\n", QueueHead(&q));
QueuePop(&q);
printf("佇列中%d個元素\n",QueueSize(&q));
QueuePush(&q, 4);
QueuePush(&q, 5);
while (QueueEmpty(&q))
{
printf("元素%d出隊\n", QueueHead(&q));
QueuePop(&q);
}
QueueDestory(&q);
printf("佇列中%d個元素\n", QueueSize(&q));
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347125.html
標籤：其他