數據結構之隊列（C語言版）

     本來此篇是準備總結堆棧順序表的一些應用，但是覺得先接著上篇把隊總結完，然后再將應用總結。ok，廢話不多數，我們先來看隊定義：

    和棧相反，隊列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。這和我們日常生活中的排隊是一樣的，最早進入隊列的元素最早離開。在隊列中允許插入的一端叫隊尾（rear），允許刪除的一端稱為隊頭（front）。隊在程序中經常用到。一個最典型的例子就是操作系統的排隊作業。ok我們先來看隊的結構圖：

    隊的基本概念，以及結構圖弄明白了的話，我們來看隊列的抽象數據類型的定義：

ADT Queue

{

    數據對象：D = {ai| ai屬于ElemSet，i = 1，2，……，n， n >= 0 }

    約定a1端為隊頭，an隊尾。

    基本操作：

    //初始化函數

    Status  InitLinkQueue(LinkQueue *q);

    //入隊，入隊成功返回TRUE,入隊失敗返回FALSE

    Status  EnterQueue(LinkQueue *q,ElemType x);

    //出隊，出隊成功返回TRUE,失敗返回FALSE

    Status DeQueue(LinkQueue *q);

    //獲取隊頭元素值，用x帶回隊頭的值

    Status GetHead(LinkQueue *q,ElemType *x);

    //求長度，返回隊的長度

    int GetLength(LinkQueue *q);

    //清空隊列,摧毀成功返回TRUE,否則返回FALSE

    Status ClearQueue(LinkQueue *q);

    //摧毀隊

    Status DestortQueue(LinkQueue *q);

    //打印隊列，打印成功返回TRUE,失敗返回FALSE

    Status Show_Queue(LinkQueue *q);

}

    對于隊列也是受限的線性表，所以，隊列也有兩種存儲結構，順序隊列和鏈式隊列。但是由于順序存儲會出現假溢出，所以出現了循環隊列的結構，鏈隊列不會出現這種情況。但是從存儲結構上看依然是兩種鏈式和順序。我們就按照順序，先看順序隊列：

順序隊列

#define ElemType  int 
#define TRUE      1
#define FALSE     0
#define Status    int
#define MAX_SIZE   8
typedef struct listqueue
  {
    ElemType *base;
    int front;
    int rear;
  }ListQueue;

按照我個人理解的順序隊的結構就是這樣：

既然隊的結構弄清了，我們來看隊列的的基本操作：

順序隊列初始化：

    順序隊就像順序表一樣，所以就要初始化的時候動態開辟內存或者用數組的形式為其開辟內存，除了要開辟內存外，還要初始化結構中的其他項。當front和rear相等時表示空，且是指向基地址下表。

Status InitListQueue(ListQueue  *lq)
  {
     lq->base = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
     if(NULL == lq->base)
          {
                printf("out of memory\n");
                return FALSE;
           }
           
     lq->front = 0;
     lq->rear = 0;
     return TRUE;
   }

順序隊列入隊出隊

    隊列的兩項重要操作就是入隊和出隊，隊列我們也一直強調是受限的線性表，主要不同就在這里，入隊和出隊，入隊操作只能從表尾，出隊操作只能從表頭，入隊我們先要保證內存空間要有，所以就要先判斷是否隊已滿，然后就是尾插，rear表示的是隊尾的存儲值的空間的下一個，也就是直接把值存進下標為rear 的空間。

//入隊操縱，入隊成功返回TRUE,入隊失敗返回FALSE

Status EnListQueue(ListQueue *lq,ElemType x)
 {
    if(lq->rear >= MAX_SIZE)
     {
        printf("隊已滿\n");
        return FALSE;
      }
      
    lq->base[lq->rear++] = x;
    return TRUE;
  }

    順序隊的出隊，只能從隊頭出隊，對于順序隊，只需要修改隊頭標志front 就可以，這樣就可以把數據從邏輯上刪除。

//出隊操作，出隊成功返回TRUE,出隊失敗返回FALSE

Status DeListQueue(ListQueue *lq)
  {
      if(lq->front == lq->rear)
        {
            printf("隊已空\n");
            return FALSE;
         }
    
    lq->front++;
    return TRUE;
  }

順序隊列獲取隊列元素個數

    由于順序隊的內存是連續的，所以獲取隊列數據元素個數，只需要把rear與front相減就可以得到隊列的長度。

//獲取長度，

int Get(ListQueue lq)
    {
        int  length = lq.rear - lq.front;
        return length;
    }

順序隊列對頭元素

    對于獲取隊頭元素操作，由于front表示的就是首元素的下標，所以只需要把數組中front下標中的值返回就好。

//獲取隊頭，獲取成功返回TRUE,獲取失敗返回FALSE

Status GetHead(ListQueue *lq,ElemType *val)
{
    if(lq->front == lq->rear)
    {
        printf("隊已空\n");
        return FALSE;
    }
    *val = lq->base[lq->front];
    return TRUE;
}

順序隊列清空隊列

    清空順序隊列，我們只需要把front和rear下標從新指向數組的0下邊即可。

//清空,清空成功返回TRUE

Status ClearListQueue(ListQueue *lq)
{
    lq->front = lq->rear = 0;
    return TRUE;
}

順序隊列的摧毀

    對于摧毀操作，我們就要把初始化中開辟的內存釋放掉并且把rear和front賦值為0

//摧毀，摧毀成功返回TRUE.

Status DestoryListQueue(ListQueue *lq)
{
    free(lq->base);
    lq->base = NULL;
    lq->front = lq->rear = 0;
    return TRUE;
}

順序隊列的輸出打印

    順序隊的打印輸出我們時，隊結構中front表示著隊頭元素的下標，rear表示隊尾下一個位置，所以只需要打印輸出從front到rear的元素。

//打印，打印成功返回TRUE,失敗返回FALSE

Status ShowListQueue(ListQueue *lq)
{
    if(lq->rear == 0)
    {
        printf("隊已空\n");
        return FALSE;
      }
    for(int i = lq->front; i < lq->rear; i++)
        {
            printf("%d ",lq->base[i]);
        }
    printf("\n");
    return TRUE;
}

鏈隊列

    用鏈表 表示的隊列稱為鏈隊列，如下圖，分別是按照理解畫的圖，一個鏈隊列得分別有指向隊頭和隊尾的指針（分別稱作頭指針和尾指針）才能唯一確定。由于隊列是限定在進行頭刪尾插，那么我們之前總結鏈表的時候說過，帶頭結點的頭單鏈表更方便頭刪，所以這里采用帶頭結點的單鏈表表示隊列。

    開篇已經把隊列的抽象數據類型介紹了，所以這里直接實現鏈隊列。

鏈隊列定義結點類型和管理結構

#define Status   int
#define TRUE     1
#define FALSE    0
#define ElemType int 


//定義結點類型
typedef struct  QueueNode
{
	ElemType data;
	struct QueueNode *next;

}QueueNode;

//定義管理結構
typedef struct LinkQueue
{
	QueueNode *front;
	QueueNode *tail;
}LinkQueue;

鏈隊列初始化

    我們一直強調，對于棧、隊是受限的線性表，所以，初始化鏈隊列的時候，我們聯想一下之前的帶頭結點的單鏈表如何初始化，就明白了鏈隊如何初始化了。

//初始化隊列
Status  InitLinkQueue(LinkQueue *Q)
{
	QueueNode  *s = (QueueNode *)malloc(sizeof(QueueNode));

	if(NULL == s)
	{
		printf("out of memory\n");
		return FALSE;
	}

	Q->front = s;
	Q->tail = s;
	s->next = NULL;
	return TRUE;	
}

鏈隊列進隊出隊

    隊是受限的線性表，那么對于隊列進隊、出隊是需要注意的操作，隊的先進先出，映射到鏈表中就是進行頭刪，尾插。這里由于帶頭結點頭插的時候，也就是入隊的時候操作就簡化了好多.入隊出隊操作就是帶頭結點的頭刪尾插，所以，我就不過多廢話。

//入隊操作，入隊成功返回TRUE,入隊失敗返回FALSE
Status  EnterQueue(LinkQueue *q,ElemType x)
{
	QueueNode  *s = (QueueNode *)malloc(sizeof(QueueNode));

	if(NULL == s)
	{
		printf("out of memory\n");
		return FALSE;
	}

	s->data = x;
	s->next = NULL;
	q->tail->next = s;
	return TRUE;
}

//出隊操作，出隊成功返回TRUE,出隊失敗返回FALSE,出隊的時候，需要注意釋放內存，防止內存泄露
Status DeQueue(LinkQueue *q)
{
	if(q->front == q->tail )
	{
		printf("隊已空\n");
		return FALSE;
	}

	QueueNode *p = q->front->next;

	q->front->next = p->next;
	free(p);
	p = q->front->next; 

	if(q->tail == p)
	{
		q->tail = q->front;
	}
	return TRUE;
}

鏈隊列獲取隊頭元素

    獲取對頭元素這里需要強調一下，獲取隊頭元素大多數課本上是用參數中一個值帶回，或者用return語句直接返回返回值，這樣做呢對于順序隊、隊中只有一個值的時候沒有錯，但是不知道你有沒有想過，假如說隊的結點中不是一個數據域呢？還可以用return語句直接返回直接返回返回數據域嗎？不可以吧！所以呢，個人覺得用return語句直接將整個結點返回，這樣需要不論他是幾個都可以，之前的鏈表、棧中是按照之前的操作做的，后邊的操作將改掉這部分的操作，采用返回結點。

//獲取對頭元素，獲取成功返回頭結點，獲取失敗返回NULL
 QueueNode *GetHead(LinkQueue *q)
{
	QueueNode *p = q->front->next;
	if(q->front == q->tail )
	{
		printf("隊已空\n");
		return NULL;
	}

	return q->front->next;
}

鏈隊求數據個數

    鏈隊求隊中元素個數，不在像順序隊中，直接用reat和front直接相減就可以獲取隊列的元素個數，鏈隊不可以，鏈隊的內存不連續，這里就需要用一個變量計算隊列的長度，防止頭指針被修改就需要用臨時指針遍歷鏈表，然后計算其長度。或者在隊列管理結構中在添加一項數據項，記住隊列的個數。這樣的話就可以方便的獲取隊列的元素個數。

//求長度
int GetLength(LinkQueue *q)
{
	int length;
	QueueNode *p = q->front->next;
	while(NULL != p)
	{
		length++;
		p = p->next;
	}
	return length;
}

鏈隊打印輸出隊中元素

    鏈表不空的話，遍歷整個鏈表輸出整個鏈表的數據域，為了防止頭指針被修改就需要定義一個臨時變量指向隊列

//遍歷成功返回TRUEM,遍歷失敗返回FALSE
Status Show_Queue(LinkQueue *q)
{
	QueueNode *p = q->front->next;
	if(q->front == q->tail )
	{
		printf("隊已空\n");
		return FALSE;
	}
	while(NULL != p)
	{
		printf("%d",p->data);
	}
	printf("\n");
	return TRUE;
}

鏈隊的清空

    鏈表的清空就需要把申請的所有結點釋放掉，防止內存空間泄露。

//清空隊列
Status ClearQueue(LinkQueue *q)
{
	if(q->front == q->tail)
	{
		return FALSE;
	}
	QueueNode *p = q->front->next;
	while(NULL != p)
	{
		q->front->next = p->next;
		free(p);
		p = q->front->next;
	}
	p = NULL;
	q->tail = q->front;
	return TRUE;
}

鏈隊的摧毀 

    鏈隊的摧毀就是在釋放了所有結點后，再把頭結點釋放掉。

//鏈隊的摧毀
Status DestortQueue(LinkQueue *q)
{
	ClearQueue(q);
	free(q->front);
	q->front = NULL;
	q->tail = NULL;
	return TRUE;
}

循環隊列

    為什么會出現循環隊列？上邊總結順序隊列的時候提到一個問題就是順序隊列會出現假溢出，對于鏈隊不會出現假溢出，也就不需要處理這種情況。這下我們先來看前邊講的順序隊列，當進行不斷的進隊出隊操作后，會出現什么情況？

    我們可以從圖中清晰的看出來，隊列只能再插入一個元素了，但是事實上隊的空間是空的。為了解決這個問題就出現了循環隊列。關于循環隊列大多數的書上會畫下邊這樣一個圖，來解釋循環隊列：

    關于這個圖，不是我畫的是我從課本上截的，不知道大家第一眼從課本上看到這個圖什么感覺，反正我看完，沒有感覺，這畫的什么啊？不是隊啊，咋就成圈了！后來當我理解了以后，這個圖好也不好，好就是形象的說明了循環隊列的情況，但是這會讓人產生誤會，會以為計算機中就是這樣存的，ok，當然不是，如果是那就厲害了。其實呢。在C語言中實現環是通過求模實現的，當你想實現一個多大的環通過求它的模就可以把數字控制在0 到 n-1，這個想必大家沒有疑問吧？那么循環隊列就是通過這樣控制順序隊列的下表來實現順序隊列。 ok。我們來邊看代碼邊解釋。

     循環隊列是建立在順序隊列上的，所以結構一樣的只是基本操作處理上不一樣。

定義循環隊列的結構

#define ElemType  int 
#define TRUE      1
#define FALSE     0
#define Status    int
#define MAX_SIZE   12

typedef struct listqueue
{
	ElemType *base;
	int front;
	int rear;
}ListQueue;

 循環隊列的初始化

    循環鏈表的初始化與順序鏈表的操作也一樣。這也不用說

Status InitListCycQueue(ListQueue  *lq)
{
	lq->base = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
	if(NULL == lq->base)
	{
		printf("out of memory\n");
		return FALSE;
	}
	lq->front = 0;
	lq->rear = 0;
	return TRUE;
}

 循環隊列的入隊、出隊

    ok入隊出隊進入循環隊列的重點，循環隊列為什么可以實現循環？我們先看順序隊列遇到了那些問題：

    問題一：由于順序隊列是通過數組實現的，即就是你的數組開辟的很大，那么也會隨著不斷的插入的數據導入隊滿是吧？這個沒有錯吧？也會出現上面圖中那種情況rear大小等于了數組的空間大小，已經越界不能再增大了雖然front隨著數據的不斷出隊也不斷向后指向，就造成了前邊的空間無法訪問，那么我們可不可通過讓rear從新指向數組是開頭，這樣就可以從新插入數據，那么實現這個就要用到我之前已經提到的求模，通過rear求數組空間大小的模就可以把rear大小控制在0 - SIZE-1 的范圍內，而C語言的數組下標正好是從0開始到 SIZE - 1,ok解決了讓空間循環回去的問題，我們就會遇到另一個問題這也就是

    問題二：那么我們之前的判斷隊滿的條件已經不在適用，有人就說既然都循環了，不會存在隊滿，個人覺得呢！不不不，判斷隊滿是非常有必要的，雖然循環了但是隊可以容納的有效數據是一定的，當隊滿時如果繼續插入，就會將之前的數據覆蓋掉這是不允許的！所以判斷隊滿是非常有必要的！并且修改成循環以后還會遇到之前判斷隊空的條件的也不好用了，因為當采用循環以后rear == front，有可能是隊空，也有可能是隊滿，對吧？這個大家認同吧？ok解決這個問題有兩種方法：

    方法一：在結構中再引入一個標記變量，隊空時一個狀態值，堆滿時是一個狀態值。

    方法二：既然存滿時rear循環回去會造成rear == front，判斷困難，那么就犧牲最后一個空間，讓其永遠也不會相等。這樣就可以解決了判斷隊滿的條件，同時判斷隊空的問題也就相應解決了

    ok問題解決完了，那么循環隊列也就實現了

//循環隊列入隊，入隊成功返回TRUE,入隊失敗返回FALSE
Status EnListCycQueue(ListQueue *lq,ElemType x)
{

//注意看這個判斷隊滿的條件，這里采用剛才提到的第二種方法，犧牲隊尾的最后一個空間（注意
//不一定是數組的最后一個空間，是隊尾的最后一個空間）當rear + 1 時等于 front就是隊滿，rear//== front  依然是判斷隊空時的條件
	if(((lq->rear + 1) % MAX_SIZE) == lq->front)
	{
		printf("隊已滿\n");
		return FALSE;
	}
	lq->base[lq->rear] = x;
	lq->rear = (lq->rear + 1) % MAX_SIZE;
	return TRUE;
}

//出隊，出對成功，返回TRUE,出隊失敗返回FALSE
Status DeListCycQueue(ListQueue *lq)
{

	if(lq->front == lq->rear)
	{
		printf("隊已空\n");
		return FALSE;
	}
	lq->front = (lq->front + 1) % MAX_SIZE;
	return TRUE;
}

循環隊列獲取隊中元素個數

//獲取長度
int GetLentg(ListQueue *lq)
{
	return (lq->rear + MAX_SIZE - lq->front) % MAX_SIZE;
}

循環隊列獲取隊頭元素

    雖然采用了循環結構但是我們可以發現front依然是表述隊頭元素的下標，所以與順序隊的操作是沒有區別的。

//獲取隊頭
Status GetHead(ListQueue *lq,ElemType *val)
{
	if(lq->front == lq->rear)
	{
		printf("隊已空\n");
		return FALSE;
	}

	*val = lq->base[lq->front];
	return TRUE;
}

循環隊列的清空

    循環隊列的清空同樣是讓隊恢復到初始狀態，所以操縱與順序隊的操作一樣

//清空，清空成功返回TRUE
Status ClearListCycQueue(ListQueue *lq)
{
    lq->front = lq->rear = 0;
    return TRUE;
}

循環隊列的摧毀

    循環隊列只是再存儲時進行了改變，對于摧毀，東西都不在了，與順序隊又有什么區別呢？

//摧毀,摧毀成功返回TRUE,
Status DestoryListCycQueue(ListQueue *lq)
{
free(lq->base);
lq->base = NULL;
lq->front = lq->rear = 0;
return TRUE;
}

循環隊列的打印

    關于打印輸出，需要注意一下，循環隊列中的元素已經不能通過之前的方式訪問輸出了我們可以看下圖：

    當采用順序隊的方式打印輸出時，front本身就是大于rear所以不會進入循環打印輸出數據，并且那個判斷空的條件也已經不在適用了，即使循環隊中有值它也會在某中情況下判斷為空。那么循環隊列怎樣存就怎樣訪問輸出，ok我們來看：前邊已經說到循環隊列中判斷隊空的條件修改為是front == rear，然后，由于rear是指向隊尾的下一個空間的，所以循環條件只要i不等于 rear讓其循環就可以，此時還要注意i的增長方式是循環的ok

Status ShowListCycQueue(ListQueue *lq)
{
	if(lq->rear == lq->front)
	{
		printf("隊已空\n");
		return FALSE;
	}
	for(int i = lq->front; i != lq->rear; )
	{
		printf("%d ",lq->base[i]);
		i = (i+1) % MAX_SIZE;
	}
	printf("\n");
	return TRUE;
}

    ok關于隊的基本操作就總結的到這里，博文呢按照我個人的理解，盡我最大的努力進行了總結，但也不能不能避免一些表述錯誤，代碼是沒有問題的。希望各位讀者發現了其中的錯誤，評論指出錯誤，讓我改正其中的錯誤。

    后面呢按照之前說的進行線性表，棧、隊的遺留問題進行總結以及他們的應用。