C++中隊(duì)列的建立與操作詳細(xì)解析

更新時(shí)間：2013年10月14日 09:33:21 作者：

隊(duì)列結(jié)構(gòu)是從數(shù)據(jù)運(yùn)算來分類的，也就是說隊(duì)列結(jié)構(gòu)具有特殊的運(yùn)算規(guī)則。而從數(shù)據(jù)的邏輯結(jié)構(gòu)來看，隊(duì)列結(jié)構(gòu)其實(shí)就是一種線性結(jié)構(gòu)。如果從數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來進(jìn)一步劃分，隊(duì)列結(jié)構(gòu)可以分成兩類

什么是隊(duì)列結(jié)構(gòu)

順序隊(duì)列結(jié)構(gòu)：即使用一組地址連續(xù)的內(nèi)存單元依次保存隊(duì)列中的數(shù)據(jù)。在程序中，可以定義一個(gè)指定大小的結(jié)構(gòu)數(shù)組來作為隊(duì)列。

鏈?zhǔn)疥?duì)列結(jié)構(gòu)：即使用鏈表形式保存隊(duì)列中各元素的值。

在隊(duì)列結(jié)構(gòu)中允許對(duì)兩端進(jìn)行操作，但是兩端的操作不同。在表的一端只能進(jìn)行刪除操作，稱為隊(duì)頭；在表的另一端只能進(jìn)行插入操作，稱為隊(duì)尾。如果隊(duì)列中沒有數(shù)據(jù)元素，則稱之為空隊(duì)列。從數(shù)據(jù)的運(yùn)算角度分析，隊(duì)列是按照“先進(jìn)先出”的原則處理結(jié)點(diǎn)的。

可以將隊(duì)列結(jié)構(gòu)理解成是：超市排隊(duì)結(jié)賬的人群，排在隊(duì)首的人先結(jié)賬，然后不斷會(huì)有人排在隊(duì)尾等待結(jié)賬，這就是一個(gè)先來先服務(wù)的隊(duì)列的現(xiàn)實(shí)中的例子。

一般隊(duì)列結(jié)構(gòu)的基本操作只有兩個(gè)：

入隊(duì)列：將一個(gè)元素添加到隊(duì)尾（相當(dāng)于到隊(duì)列最后排隊(duì)等待）

出隊(duì)列：將對(duì)頭的元素取出，同時(shí)刪除該元素，使后一個(gè)元素成為隊(duì)頭。

初次之外，還有初始化隊(duì)列、獲取隊(duì)列長(zhǎng)度的簡(jiǎn)單運(yùn)算。下面，我們就是用C++建立順序隊(duì)列結(jié)構(gòu)，并完成順序隊(duì)列結(jié)構(gòu)的基本運(yùn)算。
準(zhǔn)備數(shù)據(jù)

準(zhǔn)備數(shù)據(jù)就是定義在隊(duì)列操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。

復(fù)制代碼代碼如下:

struct DATA{
 string name;
 int age;
};
struct SQType
{
 DATA data[QUEUELEN];   //隊(duì)列數(shù)組 
 int head;      //隊(duì)頭 
 int tail;      //隊(duì)尾 
};

這里，定義了隊(duì)列結(jié)構(gòu)的最大長(zhǎng)度QUEUELEN ,隊(duì)列結(jié)構(gòu)數(shù)據(jù)元素的類型DATA以及隊(duì)列結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)SQType。在數(shù)據(jù)結(jié)構(gòu)SQType中，data為數(shù)據(jù)元素，head為隊(duì)首的序號(hào)，tail為隊(duì)尾的序號(hào)。當(dāng)head=0時(shí)表示隊(duì)列為空，當(dāng)tail=QUEUELEN時(shí)表示隊(duì)列滿。

初始化隊(duì)列數(shù)據(jù)

順序隊(duì)列的初始化操作步驟如下：

（1）按符號(hào)常量QUEUELEN指定的大小申請(qǐng)一段內(nèi)存空間，用來保存隊(duì)列中的數(shù)據(jù)。

（2）設(shè)置head=0和tail=0，表示一個(gè)空棧。

示例代碼如下：

復(fù)制代碼代碼如下:

SQType *SQTypeInit()
{
 SQType * q;
 if(q=new SQType)    //申請(qǐng)隊(duì)列的內(nèi)存空間
 {
  q->head=0;     //設(shè)置隊(duì)首 
  q->tail=0;     //設(shè)置隊(duì)尾 
  return q;
 }
 else
 {
  return NULL;    //返回空 
 } 
} 

首先使用new申請(qǐng)內(nèi)存，申請(qǐng)成功以后設(shè)置隊(duì)頭和隊(duì)尾，然后返回申請(qǐng)內(nèi)存的首地址，如果申請(qǐng)失敗則返回NULL。

判斷空隊(duì)列

判斷空隊(duì)列是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為空。如果是空隊(duì)列，則表示該隊(duì)列結(jié)構(gòu)中國沒有數(shù)據(jù)。此時(shí)可以進(jìn)入如隊(duì)列操作，不可以進(jìn)行出隊(duì)列操作。

示例代碼如下：

復(fù)制代碼代碼如下:

int SQTypeIsEmpty(SQType *q)
{
 return(q->head==q->tail);
} 

輸入?yún)?shù)q為一個(gè)指向操作的隊(duì)列的指針。程序中，根據(jù)隊(duì)列head是否等于tail判斷隊(duì)列是否為空。

判斷滿隊(duì)列

判斷滿隊(duì)列就是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為滿。如果是滿隊(duì)列，則表示該隊(duì)列中沒有多余的空間來保存額外數(shù)據(jù)。測(cè)試不可以進(jìn)行入隊(duì)列操作，可以進(jìn)行出隊(duì)列操作。

示例代碼如下：

復(fù)制代碼代碼如下:

int SQTypeIsFull(SQType *q)
{
 return(q->tail==QUEUELEN)
} 

輸入?yún)?shù)q為一個(gè)指向操作的隊(duì)列的指針。程序中，根據(jù)隊(duì)列tail是否等于隊(duì)列的最大值QUEUELEN判斷隊(duì)列是否是滿的。

清空隊(duì)列

清空隊(duì)列就是清楚一個(gè)隊(duì)列中的所有的數(shù)據(jù)。示例代碼如下：

復(fù)制代碼代碼如下:

void SQTypeClear(SQType *q)
{
 q->head=0;
 q->tail=0;
} 

將隊(duì)列頂指針head和尾指針tail設(shè)置為0，表示執(zhí)行清空操作。

釋放空間

釋放空間是釋放隊(duì)列結(jié)構(gòu)所占用的內(nèi)存單元。由前面可知，在初始化隊(duì)列結(jié)構(gòu)時(shí)，使用了new關(guān)鍵字分配內(nèi)存單元。雖然可以使用清空隊(duì)列操作，但是清空隊(duì)列操作并沒有釋放內(nèi)存空間，這就需要使用delete關(guān)鍵字釋放所占的內(nèi)存單元。

示例代碼如下：

復(fù)制代碼代碼如下:

void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}

程序中，調(diào)用了得delete釋放new申請(qǐng)的內(nèi)存空間。

入隊(duì)列

入隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作，主要操作是將數(shù)據(jù)元素保存到隊(duì)列結(jié)構(gòu)。入隊(duì)列操作的具體步驟如下：

（1）首先判斷隊(duì)尾，如果tail等于QUEUELEN，則表示溢出，進(jìn)行出錯(cuò)處理。否則執(zhí)行以下操作。

（2）設(shè)置tail=tail+1（隊(duì)列頂指針加1，指向入隊(duì)列地址）

（3）就將入隊(duì)列元素保存到tail指向的位置

示例代碼如下：

復(fù)制代碼代碼如下:

int InSQType(SQType *q,DATA data)
{
 if(q->tail==QUEUELEN)
 {
  cout<<"隊(duì)列已滿！操作失??！"<<endl;
  return 0;
 }else
 {
  q-data[q->tail++]=data;      //將元素入隊(duì)列 
  return 1; 
 } 
} 

輸入?yún)?shù)q為指向操作的隊(duì)列的指針，輸入?yún)?shù)data為需要入隊(duì)列的數(shù)據(jù)元素。程序中首先判斷隊(duì)列是否溢出，如果溢出則不進(jìn)行入隊(duì)列操作，否則修改隊(duì)列頂指針的值，再將元素入隊(duì)列。

因?yàn)閠ail的值從0開始，當(dāng)前的值就是要插入的數(shù)組對(duì)應(yīng)的元素的位置，所以寫成q->tail++。

出隊(duì)列

出隊(duì)列是隊(duì)列結(jié)構(gòu)的基本操作，主要操作與入隊(duì)列相反，其實(shí)從隊(duì)列頂彈出一個(gè)數(shù)據(jù)元素。出隊(duì)列操作的具體步驟如下：

（1）首先判斷隊(duì)首head，如果head等于tail，則表示為空隊(duì)列，進(jìn)行出錯(cuò)處理。否則，執(zhí)行下面的步驟

（2）從隊(duì)列首部取出隊(duì)頭元素（實(shí)際返回隊(duì)頭元素的指針）

（3）修改隊(duì)首head的序號(hào)，使其指向后一個(gè)元素。
示例代碼如下：

復(fù)制代碼代碼如下:

DATA *OutSQType(SQType *q)
{
 if(q->tail==q->head)
 {
  cout<<"隊(duì)列已空！操作失?。?<<endl;
  exit(0);  
 }else
 {
  return &(q->data[q->head++]);
 }
} 

輸入?yún)?shù)q為指向操作的隊(duì)列的指針。該函數(shù)返回值是一個(gè)DATA類型的數(shù)據(jù)，返回值是指向該數(shù)據(jù)元素的指針。

讀結(jié)點(diǎn)數(shù)據(jù)

讀結(jié)點(diǎn)數(shù)據(jù)也就是讀取隊(duì)列結(jié)構(gòu)中結(jié)點(diǎn)的數(shù)據(jù)，這里的讀操作其實(shí)就是讀隊(duì)列頭的數(shù)據(jù)。需要助于的是，讀結(jié)點(diǎn)數(shù)據(jù)的操作和出隊(duì)列操作不同。讀結(jié)點(diǎn)數(shù)據(jù)的操作僅是顯示隊(duì)列頂結(jié)點(diǎn)數(shù)據(jù)的內(nèi)容，而出隊(duì)列操作則將隊(duì)列頂數(shù)據(jù)彈出，該數(shù)據(jù)不再存在。

示例代碼如下：

復(fù)制代碼代碼如下:

DATA * PeekSQType(SQType *q)
{
 if(SQTypeIsEmpty(q))
 {
  cout<<"空隊(duì)列"<<endl;
  return NULL; 
 }else
 {
  return &(q->data[q->head]);
 }

} 

該函數(shù)返回值同樣是一個(gè)DATA類型的指針數(shù)據(jù)，返回值是指向數(shù)據(jù)元素的指針。

計(jì)算隊(duì)列長(zhǎng)度

計(jì)算隊(duì)列長(zhǎng)度就是統(tǒng)計(jì)該隊(duì)列中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。計(jì)算隊(duì)列長(zhǎng)度的方法比較簡(jiǎn)單，直接隊(duì)尾序號(hào)減去隊(duì)首序號(hào)即可。

示例代碼如下：

復(fù)制代碼代碼如下:

int SQTypeLen(SQType *q)
{
 return(q->tail-q->head); 
}

隊(duì)列結(jié)構(gòu)操作實(shí)例代碼：

完整的代碼會(huì)比較長(zhǎng)，不過函數(shù)部分和上面介紹的基本一致，主要是看main函數(shù)中這些函數(shù)的用法：

復(fù)制代碼代碼如下:

#include<iostream>
#include<string>
using namespace std;
#define QUEUELEN 10
struct DATA{
 string name;
 int age;
};
struct SQType
{
 DATA data[QUEUELEN];   //隊(duì)列數(shù)組 
 int head;      //隊(duì)頭 
 int tail;      //隊(duì)尾 
};
/*******************隊(duì)列的初始化*************************/ 
SQType *SQTypeInit()
{
 SQType * q;
 if(q=new SQType)    //申請(qǐng)隊(duì)列的內(nèi)存空間
 {
  q->head=0;     //設(shè)置隊(duì)首 
  q->tail=0;     //設(shè)置隊(duì)尾 
  return q;
 }
 else
 {
  return NULL;    //返回空 
 } 
}
/*******************判斷空隊(duì)列*************************/ 
int SQTypeIsEmpty(SQType *q)
{
 return(q->head==q->tail);
} 
/*******************判斷滿隊(duì)列*************************/ 
int SQTypeIsFull(SQType *q)
{
 return(q->tail==QUEUELEN);
} 
/*******************清空隊(duì)列*************************/ 
void SQTypeClear(SQType *q)
{
 q->head=0;
 q->tail=0;
} 
/*******************釋放空間*************************/
void SQTypeFree(SQType *q)
{
 if(q!=NULL) delete q;
} 
/*******************入隊(duì)列操作*************************/
int InSQType(SQType *q,DATA data)
{
 if(q->tail==QUEUELEN)
 {
  cout<<"隊(duì)列已滿！操作失??！"<<endl;
  return 0;
 }else
 {
  q->data[q->tail++]=data;      //將元素入隊(duì)列 
  return 1; 
 } 
} 
/*******************出隊(duì)列操作*************************/
DATA *OutSQType(SQType *q)
{
 if(q->tail==q->head)
 {
  return NULL;  
 }else
 {
  return &(q->data[q->head++]);
 }
} 
/*******************讀結(jié)點(diǎn)數(shù)據(jù)*************************/
DATA * PeekSQType(SQType *q)
{
 if(SQTypeIsEmpty(q))
 {
  cout<<"空隊(duì)列"<<endl;
  return NULL; 
 }else
 {
  return &(q->data[q->head]);
 }

} 
/*******************計(jì)算隊(duì)列長(zhǎng)度*************************/
int SQTypeLen(SQType *q)
{
 return(q->tail-q->head); 
}
/*********************主函數(shù)******************************/
int main()
{
 SQType *stack;
 DATA data,*p;
 stack=SQTypeInit();     //執(zhí)行初始化操作
 cout<<"執(zhí)行入隊(duì)列操作："<<endl;
 cout<<"輸入姓名,年齡進(jìn)行入隊(duì)操作："<<endl;
 while(1)
 {
  cin>>data.name>>data.age;
  if(data.age==0)
  {
   break;      //若輸入為0，則退出 
  }
  else
  {
   InSQType(stack,data); 
  } 
 }
 cout<<"進(jìn)行出棧操作："<<endl;
 p=OutSQType(stack);
 cout<<p->name<<","<<p->age<<endl;
 cout<<"讀取首結(jié)點(diǎn)數(shù)據(jù)："<<endl;
 p=PeekSQType(stack);
 cout<<p->name<<","<<p->age<<endl;
 cout<<"執(zhí)行出棧操作："<<endl;
 while(1)
 {
  if(SQTypeIsEmpty(stack))
  {
   cout<<"所有數(shù)據(jù)出棧完畢，棧為空！"<<endl;
   break;
  }else
  {
   p=OutSQType(stack);
   cout<<p->name<<","<<p->age<<endl;
  } 
 } 
 SQTypeFree(stack);
 return 0;
}