前言

陸陸續續的,我們已經學完了順序表,單鏈表,雙鏈表以及堆疊.今天,博主更新的內容就是資料結構中的佇列.

1. 何為佇列

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出的特性

只允許插入資料操作的一端叫做隊尾

只允許洗掉資料操作的一端叫做隊頭

而洗掉操作叫做出隊,插入操作叫做入隊

上面的所有特性,博主用下面一張圖給大家演示:

2. 怎樣實作佇列

既然想要實作佇列,我們就需要根據需求抓取供應.

那么我們佇列的主要需求是什么呢? 沒錯,答案就是 入隊和出隊

入隊,毫無疑問是尾插操作,用順序表實作非常方便.

出隊,毫無疑問是頭刪操作,用鏈表實作非常方便.

也就是說只考慮目前操作的好壞,鏈表和順序組持平,那我們再考慮更優可能性吧,嗯~~~.鏈表比順序表跟節約空間

所以我們選擇用鏈表實作佇列

但是用鏈表實作的話,尾插操作就比較麻煩了(需要遍歷到尾部),怎么解決這個麻煩呢,這里采用再開辟一個結構體,用來包含鏈表結點,新的結構體中只有頭尾指標,代碼實作請看下一標題

3. 專案搭建

博主這里用的VS2019,就用它進行演示:

先建立Queue.h,Queue.c和test.c三個檔案

Queue.h的作用是寫檔案參考,函式宣告

Queue.c的作用是寫檔案函式的定義

test.c的作用是測驗所寫操作是否正確

4. 定義佇列

在2標題內容下,已經說明了實作佇列最好選擇鏈表鏈式結構,并單獨開一個結構體進行包含,所以下面就是開始這樣的實作

typedef int QDataType;

typedef struct QueueNode  //定義佇列結點
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

typedef struct Queue   //定義佇列
{
    QueueNode* head;  //隊頭
    QueueNode* tail;  //隊尾
}Queue;

5. 佇列的所有操作

對于佇列來說,我們用到的操作最多的就是下面幾種:

入隊(尾插), 出隊(頭刪),取隊頭元素,取隊尾元素,判空,獲取佇列元素數量,初始化和銷毀空間

所以,博主先在Queue.h檔案中宣告所有方法,后續再詳細實作

void QueueInit(Queue* pq);
bool QueueEmpty(Queue* pq);

void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
void QueueDestory(Queue* pq);

5.1 佇列之初始化

我們創建一個佇列后,佇列的頭尾指標還是野指標,所以我們將其初始化為NULL.

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

測驗是否成功:

成功!!

5.2 佇列之判空

判空,即判斷佇列是否為空,怎么判斷呢? 只要頭指標沒有指向任何空間就說明佇列為空

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    
    return pq->head == NULL;
}

5.3 佇列之入隊

入隊,即尾插,在前面的鏈表和順序章節中,我們對這個操作還是很熟悉的:

第一步,開辟一個新空間存盤資料

第二步,tail->next指向新結點. (只是這里需要注意當鏈表為空時候)

void QueuePush(Queue* pq, QDataType elem)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if(newnode == NULL)
    {
        perror("空間申請失敗原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;
    
    //注意這里佇列是否為空
    pq->head == NULL ? (pq->tail = newnode ):(pq->tail->next = newnode,pq->tail = pq->tail->next); 
}

測驗:

成功!!!

5.4 佇列之出隊

很明顯,出隊即頭刪,對于頭刪操作我們也是比較熟悉的:

第一步,先保存下一個結點

第二步,釋放頭結點

第三步,指向所保存的下一個結點

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //如果佇列為空,不能洗掉
    
    QueueNode* next = pq->head->next;//保存下一個結點
    free(pq->head);//釋放
    pq->head = next;//指向下一個結點
}

測驗是否成功:

成功…???了嗎,大家仔細看看上面的代碼,想想哪里會出Bug.

沒錯,當這樣出隊到最后只剩下一個結點時候,tail將會是一個野指標,如下圖:

就會發現,當剩下最后一個時候,tail還是指向了原來位置,形成一個野指標

修改代碼:

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //如果佇列為空,不能洗掉
    
    QueueNode* next = NULL;
    
    pq->head->next == NULL?
    (free(pq->head),pq->head = pq->tail = NULL):
    (next = pq->head->next, free(pq->head),pq->head = next);//條件運算式
}

現在測驗,才是真的成功

5.5 佇列之獲取隊首

這個比較簡單,直接回傳即可

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //不能為空
    
    return pa->head->data;
}

5.6 佇列之獲取隊尾

同理,直接回傳

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //不能為空
    
    return pa->tail->data;
}

測驗是否成功:

成功!!

5.7 佇列之回傳佇列元素數量

這個直接開一個變數num,然后遍歷佇列,進行計數

int QueueSize(Queue* pq)
{
    assert(pq);
    int num = 0;
    QueueNode* cur = pq->head;
    while(cur)
    {
        num++;
        cur = cur->next;
    }
    return num;
}

5.8 佇列之銷毀空間

挨個銷毀每個空間

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

測驗是否成功:

成功!!!

總代碼

Queue.h頭檔案

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.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 QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType elem);

void QueuePop(Queue* pq);

int QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

Queue.c源檔案

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType elem)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("空間申請失敗原因:");
		exit(-1);
	}
	newnode->data = elem;
	newnode->next = NULL;

	//注意這里佇列是否為空
	pq->head == NULL ? 
	(pq->tail = pq->head = newnode) : (pq->tail->next = newnode, pq->tail = pq->tail->next);
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq)); //如果佇列為空,不能洗掉

	QueueNode* next = NULL;

	pq->head->next == NULL ?
		(free(pq->head), pq->head = pq->tail = NULL) :
		(next = pq->head->next, free(pq->head), pq->head = next);//條件運算式
}


int QueueSize(Queue* pq)
{
	assert(pq);

	int num = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		num++;
		cur = cur->next;
	}
	return num;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}