日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言數據結構之隊列算法詳解_C 語言

作者：知心寶貝 ? 更新時間： 2022-03-19 編程語言

一、前言

  • 隊列在程序設計中經常出現，如：操作系統中的排隊問題。
  • 這篇文章主要介紹了隊列的基本概念、性質，順序、鏈、循環三種不同的方法實現隊列，順序和循環隊列在算法中比較常用

二、基本概念

??

  • 定義：隊列是允許在一端插入，另一端刪除的線性表
  • 隊頭（front）：允許刪除的一端
  • 隊尾（rear）：允許插入的一端
  • 特點：先進先出

三、順序隊列

動態圖：

算法講解：?

  • 圖解：入隊，rear++，出隊，front++
  • 真溢出：front==0，rear==n-1
  • 假溢出：front ! = 0，rear==n-1

結構體：

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

四、鏈隊列

  • 定義：用鏈表實現的隊列，為了操作方便，通常采用帶頭結點的鏈表結構，設置一個隊頭指針和隊尾指針
  • 隊頭指針：始終指向頭結點
  • 隊尾指針：指向當前最后一個元素
  • 空的鏈隊列：隊頭指針和隊尾指針均指向頭結點

入隊：

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

出隊：

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

五、循環隊列

概念：隊列的一種順序表示和實現方法，與順序棧類似

動態圖：

?算法講解：?

  • A? B? C? D入隊時，頭指針front不動，rear=(rear+1)%n
  • A? B? C? D出隊時，尾指針rear不動，front=(front+1)%n

入隊：

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

出隊：

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

特點：

  • 隊空： rear==front
  • 隊滿：(rear+1)%n==front
  • 入隊：rear=(rear+1)%n
  • 出隊：front=(front+1)%n
  • 隊中元素個數：（rear-front+n）%n

六、總結與提高

對于使用C++編程來說，上文隊列的判空、判滿、插入、刪除等等一系列代碼，不需要你完全掌握，C++的STL標準庫中為你準備好了函數等你調用。

C++queue頭文件：

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

C++queue具體操作：

用queue定義q類（定義什么都可以，只要把s變成定義的字母就可以調用C++中的函數）,具體使用方法為：
函數 用法
q.empty() 判斷隊列是否為空，不為空返回1，為空返回0
q.size() 返回隊列中元素個數
q.pop() 刪除隊列首元素
q.front() 返回隊列首元素，不刪除該元素
q.back() 返回隊列尾元素，不刪除該元素
s.push() 隊尾插入新的元素

原文鏈接：https://blog.csdn.net/qq_53673551/article/details/122016182

欄目分類
最近更新