快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列算法詳解

更新時(shí)間：2021年12月28日 14:29:27 作者：知心寶貝

這篇文章介紹了C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的算法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

一、前言

隊(duì)列在程序設(shè)計(jì)中經(jīng)常出現(xiàn)，如：操作系統(tǒng)中的排隊(duì)問題。

這篇文章主要介紹了隊(duì)列的基本概念、性質(zhì)，順序、鏈、循環(huán)三種不同的方法實(shí)現(xiàn)隊(duì)列，順序和循環(huán)隊(duì)列在算法中比較常用

二、基本概念

??

定義：隊(duì)列是允許在一端插入，另一端刪除的線性表

隊(duì)頭（front）：允許刪除的一端

隊(duì)尾（rear）：允許插入的一端

特點(diǎn)：先進(jìn)先出

三、順序隊(duì)列

動態(tài)圖：

算法講解：?

圖解：入隊(duì)，rear++，出隊(duì)，front++

真溢出：front==0，rear==n-1

假溢出：front ! = 0，rear==n-1

結(jié)構(gòu)體：

#define MAXQSIZE 100;
Typedef struct{
  QElemType  element[MAXQSIZE];  //隊(duì)列的元素空間
  int  front;  //頭指針，若隊(duì)列不空，指向隊(duì)頭元素；
  int  rear;    //尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一個(gè)位置
}SeqQueue;

四、鏈隊(duì)列

定義：用鏈表實(shí)現(xiàn)的隊(duì)列，為了操作方便，通常采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)，設(shè)置一個(gè)隊(duì)頭指針和隊(duì)尾指針

隊(duì)頭指針：始終指向頭結(jié)點(diǎn)

隊(duì)尾指針：指向當(dāng)前最后一個(gè)元素

空的鏈隊(duì)列：隊(duì)頭指針和隊(duì)尾指針均指向頭結(jié)點(diǎn)

入隊(duì)：

int EnterQueue ( LinkQueue *Q; QElemType x ) {
//1. 為待插入結(jié)點(diǎn)開辟存儲空間
p = ( LinkQueueNode ) malloc ( sizeof ( QNode ) );
if (p==NULL )  return ( FALSE ); // 存儲空間分配失敗
//2. 將值 x放入新結(jié)點(diǎn)的數(shù)據(jù)域,令新結(jié)點(diǎn)的指針域?yàn)榭?
p->data = x; p->next = NULL;
// 3. 將新結(jié)點(diǎn)插入到隊(duì)列 Q 的尾, 并修改隊(duì)列 Q 的隊(duì)尾指針
 Q->rear->next = p; 
Q->rear = p; 
 return (TRUE);
} // EnterQueue

出隊(duì)：

int DeleteQueue ( LinkQueue *Q, QElemType *x ) {
// 1.如果隊(duì)列為空則無法進(jìn)行刪除，則返回 ERROR
if ( Q->front = = Q->rear ) return (FALSE); 
// 2.令 p 指向隊(duì)列 Q 的頭, 并將隊(duì)頭結(jié)點(diǎn)的值取出并放入 x
p = Q->front->next;    x = p->data; 
//3. 修改隊(duì)頭指針
Q->front->next = p->next; 
// 4. 若隊(duì)中只有一個(gè)元素，則P出隊(duì)后成為空隊(duì)
if ( Q->rear = = p )  Q->rear = Q->front;
 free ( p ); // 釋放隊(duì)頭元素所占空間
return (TRUE);
} // DeleteQueue

五、循環(huán)隊(duì)列

概念：隊(duì)列的一種順序表示和實(shí)現(xiàn)方法，與順序棧類似

動態(tài)圖：

?算法講解：?

A? B? C? D入隊(duì)時(shí)，頭指針front不動，rear=(rear+1)%n

A? B? C? D出隊(duì)時(shí)，尾指針rear不動，front=(front+1)%n

入隊(duì)：

int EnterQueue(SeqQueue *Q,QueueElementType x)
{  	
	//1. 判斷隊(duì)列是否已經(jīng)滿了 
    if((Q->rear+1)%MAXSIZE==Q->front)  
               return (FALSE);
   //2. 新元素x入隊(duì)
	Q->element[Q->rear]=x; 	
   // 3. 重新設(shè)置隊(duì)尾指針
  Q->rear=(Q->rear+1)%MAXSIZE; 	
      return (TRUE);      
}

出隊(duì)：

int DeleteQueue(SeqQueue *Q,QueueElementType *x)
{
  //1. 判斷隊(duì)列是否已經(jīng)空了 
		if(Q->front==Q->rear)
		return(FALSE);
 //2. 刪除隊(duì)列的隊(duì)頭元素，用x返回其值
	   *x=Q->element[Q->front];
// 3. 重新設(shè)置隊(duì)頭指針
	  Q->front=(Q->front+1)%MAXSIZE;   
     return(TRUE);  
}

特點(diǎn)：

隊(duì)空： rear==front

隊(duì)滿：(rear+1)%n==front

入隊(duì)：rear=(rear+1)%n

出隊(duì)：front=(front+1)%n

隊(duì)中元素個(gè)數(shù)：（rear-front+n）%n

六、總結(jié)與提高

對于使用C++編程來說，上文隊(duì)列的判空、判滿、插入、刪除等等一系列代碼，不需要你完全掌握，C++的STL標(biāo)準(zhǔn)庫中為你準(zhǔn)備好了函數(shù)等你調(diào)用。

C++queue頭文件：

#include<queue>
//#include<bits/stdc++.h>或者萬能頭文件
using namespace std;

C++queue具體操作：

用queue定義q類（定義什么都可以，只要把s變成定義的字母就可以調(diào)用C++中的函數(shù)）,具體使用方法為：

函數(shù)	用法
q.empty()	判斷隊(duì)列是否為空，不為空返回1，為空返回0
q.size()	返回隊(duì)列中元素個(gè)數(shù)
q.pop()	刪除隊(duì)列首元素
q.front()	返回隊(duì)列首元素，不刪除該元素
q.back()	返回隊(duì)列尾元素，不刪除該元素
s.push()	隊(duì)尾插入新的元素