在編程語言中怎樣定義隊列及其使用(C++)

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

隊列在編程語言中是如何定義的呢？小編與大家分享自己的經(jīng)驗。

隊列的定義

隊列是限制結(jié)點插入操作固定在一端進行,而結(jié)點的刪除操作固定在另一端進行的線性表.

隊列猶如一個兩端開口的管道.允許插入的一端稱為隊頭,允許刪除的一端稱為隊尾.隊頭和隊尾各用一個”指針”指示,稱為隊頭指針和隊尾指針.不含任何結(jié)點的隊列稱為”空隊列”.隊列的特點是結(jié)點在隊列中的排隊次序和出隊次序按進隊時間先后確定,即先進隊者先出隊.因此,隊列又稱先進先出表.簡稱FIFO(first in first out)表.

步驟

隊列是用來存儲暫未處理但需要按一定順序處理的元素的一種數(shù)據(jù)結(jié)構(gòu)。

隊列是一種先進先出（First In First Out，F(xiàn)IFO）的線性表，特點是先進隊的元素先出隊。

隊列只允許在表的一端進行插入，而在另一端刪除元素。

隊尾是隊列中允許插入的一端；隊首是隊列中允許刪除的一端。

一般用順序表q[m]存儲隊列中的元素，m是隊列能存儲元素的最大數(shù)量。

front隊首指針指向隊首元素存儲的位置；rear隊尾指針指向隊尾元素的下一個位置。

順序隊列及其操作

隊列的順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)存儲的隊列稱為順序隊列.和順序表一樣,用一個一維數(shù)組存.對頭在數(shù)組的低下標端,隊尾設在高下表端.隊頭,隊尾指針值是數(shù)組元素的下標.對頭指針始終指向?qū)︻^結(jié)點的前一個結(jié)點位置,初始值為0.隊尾指針是指向隊尾結(jié)點位置,初始值也為0.

隊列初始條件:隊頭指針=隊尾指針=0
隊列滿條件:隊尾指針=m(設隊列當前容量為m)
隊列空條件:隊頭指針=隊尾指針

在QueueCs.c文件中定義了結(jié)構(gòu)

#define DT char
#define M 100
typedef struct {

  DT data[M];
  int front,rear;
}SEQUEUE;

data[M]也為數(shù)組為隊列,front為隊頭指針,rear為隊尾指針.(注意:front和rear是整數(shù)類型,不是指針類型),當front=rear=0時,為初始隊列.因為C語言中數(shù)組的第一個元素下標為0,而不是1;所以這里約定數(shù)組元素data[0]閑置不用.

順序隊列上的操作

(1)創(chuàng)建隊列

初始化隊列,隊頭指針和隊尾指針=0.

在QueueControl.h寫出方法聲明

/*
 創(chuàng)建隊列
 */
SEQUEUE initQueue();

在QueueControl.c中實現(xiàn)此方法

#include "QueueControl.h"
/*
 創(chuàng)建隊列
 */
SEQUEUE initQueue(){
  SEQUEUE Q;
  //1.初始化隊列,隊頭指針=隊尾指針=0
  Q.front=Q.rear=0;
  return Q;
}

(2)插入

在QueueControl.h寫出方法聲明

/*
 插入
 */
SEQUEUE inQueue(SEQUEUE Q,DT x);

在QueueControl.c中實現(xiàn)此方法

#include "QueueControl.h"

SEQUEUE inQueue(SEQUEUE Q,DT x){
  //1.判斷隊列是上溢,就是隊尾指針是否等于最大申請的空間
  if(Q.rear==M){
    printf("Up Overflow\n");
  }else{
     //2.從隊尾插入結(jié)點
    Q.rear++;
    Q.data[Q.rear]=x;
    printf("in success\n");
  }
  return Q;
}

(3)刪除

在QueueControl.h寫出方法聲明

/*
 刪除
 */
SEQUEUE outQueue(SEQUEUE Q);

/*
 打印隊列元素
 */
void printQueue(SEQUEUE Q);

在QueueControl.c中實現(xiàn)此方法

#include "QueueControl.h"

SEQUEUE outQueue(SEQUEUE Q){
  //1.首先判斷是否是空隊列
  if(Q.front==Q.rear){
    printf("queue is empty\n");
  }else{
    //2.刪除結(jié)點是從隊頭刪除
    Q.front++;
     printf("out success\n");
  }
  return Q;
}



/*
 打印隊列元素
 */
void printQueue(SEQUEUE Q){
  //1.從隊頭開始打印數(shù)據(jù)
  SEQUEUE temp=Q;
  printf("queue={");
  while (temp.front<temp.rear) {
     temp.front++;
    if(temp.front==Q.front+1){
      printf("%c",temp.data[temp.front]);
    }else{
      printf(",%c",temp.data[temp.front]);
    }

  }
  printf("}\n");
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進行判斷

#include "QueueControl.h"
int main(int argc, const char * argv[]) {
  //初始化順序隊列
  SEQUEUE queue=initQueue();
  printQueue(queue);
  //插入
  queue=inQueue(queue, 'a');
  queue=inQueue(queue, 'b');
  queue=inQueue(queue, 'c');
  queue=inQueue(queue, 'd');
  printQueue(queue);
  //刪除
  queue=outQueue(queue);
  printQueue(queue);
  return 0;

}

打印結(jié)果:

queue={}
in success
in success
in success
in success
queue={a,b,c,d}
out success
queue={b,c,d}
Program ended with exit code: 0

從插入隊列和刪除隊列操作的打印結(jié)果來看,隊列的特點確實是:先進先出.

循環(huán)隊列及其操作

循環(huán)隊列的存儲結(jié)構(gòu)

根據(jù)順序隊列的操作和敘述可以看出,隊尾指針=m表示隊滿,不能再插入結(jié)點了,當隊頭指針等于隊尾指針表示對空.但是當隊尾指針和隊尾指針都等于m的時候,那么此時表示對空,那么也不能插入了其他的結(jié)點,但是此時0-m之間的結(jié)點已經(jīng)空閑,這樣許多空閑的結(jié)點不能被利用,浪費存儲空間.

循環(huán)隊列是把順序隊列的頭尾相接形成一個圓環(huán).邏輯上吧1號結(jié)點作為m號結(jié)點的后繼結(jié)點處理.

循環(huán)隊列初始條件:隊頭指針=隊尾指針=0
循環(huán)隊列隊滿條件:MOD(隊尾指針+1,m)=隊頭指針
循環(huán)隊列空條件:隊頭指針=隊尾指針
隊頭指針推進計算:隊頭指針=MOD(隊頭指針+1,m)
隊尾指針推進計算:隊尾指針=MOD(隊尾指針+1,m)

在QueueCycleCs.c文件中定義了結(jié)構(gòu)

#define CDT char
#define CM 5
typedef struct {

  CDT data[CM];
  int front,rear;
}SECYCLEQUEUE;

循環(huán)隊列上的操作

(1)創(chuàng)建循環(huán)隊列

初始化隊列,隊頭指針和隊尾指針=0.

在QueueCycyleControl.h寫出方法聲明

#include "QueueCycleCs.c"

/*
 創(chuàng)建循環(huán)隊列
 */
SECYCLEQUEUE initCycleQueue();

在QueueCycyleControl.c中實現(xiàn)此方法

#include "QueueCycleControl.h"
/*
 創(chuàng)建循環(huán)隊列
 */
SECYCLEQUEUE initCycleQueue(){
  SECYCLEQUEUE Q;
  //隊頭指針=隊尾指針=0;
  Q.front=Q.rear=0;
  return Q;
}

(2)插入

在QueueCycyleControl.h寫出方法聲明

#include "QueueCycleCs.c"

/*
 循環(huán)隊列插入
 */
SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,char x);

在QueueCycyleControl.c中實現(xiàn)此方法

#include "QueueCycleControl.h"
SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,CDT x){

  //1.判斷循環(huán)隊列是否已經(jīng)滿了,MOD(隊尾指針+1,m)=隊頭指針
  if((Q.rear+1)%CM==Q.front){
    printf("queue is full!\n");
  }else{
    //2.在隊尾插入,計算隊尾指針的
    Q.rear=(Q.rear+1)%CM;
    //3.設置插入結(jié)點的值數(shù)值
    Q.data[Q.rear]=x;
    printf("in Cycle queue Success!\n");
  }
  return Q;
}

(3)刪除

在QueueCycyleControl.h寫出方法聲明

#include "QueueCycleCs.c"
/*
 循環(huán)隊列刪除
 */
SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q);
/*
 打印循環(huán)隊列
 */
void printCycleQueue(SECYCLEQUEUE Q);

在QueueCycyleControl.c中實現(xiàn)此方法

#include "QueueCycleControl.h"
SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q){

  //1.判斷循環(huán)隊列是否是空
  if(Q.front==Q.rear){
    printf("Cycle queue is Empty!\n");
  }else{
    //2.刪除結(jié)點從隊頭刪除,計算隊頭指針:隊頭指針=MOD(隊頭指針+1,m)
    Q.front=(Q.front+1)%CM;
    printf("out cycle queue success!\n");
  }
  return Q;
}

/*
 打印循環(huán)隊列
 */
void printCycleQueue(SECYCLEQUEUE Q){
  //M=5;
  //1.從隊頭開始打印數(shù)據(jù)
  SECYCLEQUEUE temp=Q;
  printf("queue={");
  //2.判斷的條件是,隊頭指針!=隊尾指針
  while (temp.front!=temp.rear) {
    temp.front=(temp.front+1)%CM;
    if(temp.front==((Q.front+1)%CM)){
      printf("%c",temp.data[temp.front]);
    }else{
      printf(",%c",temp.data[temp.front]);
    }

  }
  printf("}\n");
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進行判斷

#include "QueueCycleControl.h"
int main(int argc, const char * argv[]) {
  //創(chuàng)建循環(huán)隊列
  SECYCLEQUEUE CQ=initCycleQueue();
  //插入數(shù)據(jù)5個結(jié)點,但是最大是5,一個空閑,最后一個添加不進去,
  CQ=inCycleQueue(CQ, 'a');
  CQ=inCycleQueue(CQ, 'b');
  CQ=inCycleQueue(CQ, 'c');
  CQ=inCycleQueue(CQ, 'd');
  CQ=inCycleQueue(CQ, 'e');
  printCycleQueue(CQ);
  //刪除節(jié)點-三個結(jié)點
  CQ=outCycleQueue(CQ);
  CQ=outCycleQueue(CQ);
  CQ=outCycleQueue(CQ);
  printCycleQueue(CQ);
  //插入-兩個結(jié)點
  CQ=inCycleQueue(CQ, 'e');
  CQ=inCycleQueue(CQ, 'f');
  printCycleQueue(CQ);
  //刪除節(jié)點--刪除四個結(jié)點,現(xiàn)在此時是三個結(jié)點,最后一個刪除不了
  CQ=outCycleQueue(CQ);
  CQ=outCycleQueue(CQ);
  CQ=outCycleQueue(CQ);
  CQ=outCycleQueue(CQ);
  printCycleQueue(CQ);

  return 0;
}

打印結(jié)果:

in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
queue is full!
queue={a,b,c,d}
out cycle queue success!
out cycle queue success!
out cycle queue success!
queue=c8jzdxauzz
in Cycle queue Success!
in Cycle queue Success!
queue={d,e,f}
out cycle queue success!
out cycle queue success!
out cycle queue success!
Cycle queue is Empty!
queue={}
Program ended with exit code: 0

鏈隊列及其操作

隊列的鏈存儲結(jié)構(gòu)

鏈存儲結(jié)構(gòu)存儲的隊列稱為鏈隊列.隊頭指針指向鏈隊列的頭結(jié)點,頭結(jié)點的指針域若為空,則為空隊列;若不為空,則為指向隊首結(jié)點的指針.

鏈隊列設有一個隊頭指針,其值指向隊列的頭結(jié)點.也是唯一地標示一個鏈隊.設置一個隊尾指針方便插入結(jié)點.隊頭指針和隊尾指針都是指針型變量.

鏈隊列沒有容量的限制,所以在可用的存儲空間范圍內(nèi),一般不會出現(xiàn)上溢問題,也不存在如順序隊列的假溢出問題.

在QueueLinkCs.c中定義了結(jié)構(gòu)

#define LDT char
//結(jié)點類型
typedef struct llnode{
  LDT data;
  struct llnode *next;
}LINKNODE;

//鏈隊列結(jié)構(gòu)
typedef struct{
  LINKNODE *front,*rear;
}LINKQUEUE;

鏈隊列上的操作

(1)創(chuàng)建鏈隊列

在QueueLinkControl.h寫出方法聲明

#include <stdio.h>
#include "QueueLinkCs.c"


/*
 創(chuàng)建鏈隊
 */
LINKQUEUE * initLinkQueue(LINKQUEUE *LQ);

在QueueLinkControl.c中實現(xiàn)此方法

#include "QueueLinkControl.h"
#include <stdlib.h>
/*
 創(chuàng)建鏈隊
 */
LINKQUEUE *initLinkQueue(LINKQUEUE *LQ){
  //設置隊頭指針
  LQ->front=(LINKNODE *)malloc(sizeof(LINKNODE));
  LQ->front->data='#';//設置隊頭指針,也是頭結(jié)點的指針域
  LQ->front->next=NULL;
  //初始條件:隊頭指針和隊尾指針一致
  LQ->rear=LQ->front;
  return LQ;
}

(2)插入

在QueueLinkControl.h寫出方法聲明

/*
 鏈隊插入:隊尾
 */
LINKQUEUE * inLinkQueue(LINKQUEUE *LQ,LDT x);

在QueueLinkControl.c中實現(xiàn)此方法

(3)刪除

在QueueLinkControl.h寫出方法聲明

/*
 鏈隊刪除:隊頭
 */
LINKQUEUE *outLinkQueue(LINKQUEUE *LQ);

/*
 打印鏈表結(jié)點
 */
void printLinkQueue(LINKQUEUE *LQ);

在QueueLinkControl.c中實現(xiàn)此方法

#include "QueueLinkControl.h"
#include <stdlib.h>
LINKQUEUE *outLinkQueue(LINKQUEUE *LQ){
  if(LQ==NULL || LQ->rear==LQ->front){
    printf("LQ is empty!\n");
    return LQ;
  }
  //1.獲取首結(jié)點
  LINKNODE *frontNextNode;
  frontNextNode=LQ->front->next;

  //2.將首節(jié)點的next指針域的值存儲頭結(jié)點的next域

  LQ->front->next=frontNextNode->next;

  //3.如果隊尾結(jié)點等于首節(jié)點的next指針域的值,那么表示是空棧,根據(jù)空鏈隊列的結(jié)構(gòu),還需修改隊尾指針,使指向頭結(jié)點.
  if(LQ->rear==frontNextNode){
    LQ->rear=LQ->front;
  }
  //4.釋放刪除的結(jié)點
  free(frontNextNode);

  printf("out link queue success!\n");
  return LQ;
}

/*
 打印鏈表結(jié)點
 */
void printLinkQueue(LINKQUEUE *Q){
  //實例化一個LQ,為了不改變原來鏈隊Q
  LINKQUEUE *LQ;
  LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
  LQ->front=Q->front;
  LQ->rear=Q->rear;
  printf("queue={");
  //1.判斷不是空鏈表
  if(LQ!=NULL && LQ->rear!=LQ->front){
    int flag=0;

    do{
      //2.輸出數(shù)據(jù)
      if(flag==0){
        printf("%c",LQ->front->data);
        flag=1;
      }else{
        printf(",%c",LQ->front->data);
      }
      //3.鏈頭指針向后移動
      LQ->front=LQ->front->next;

    }while (LQ->front!=LQ->rear) ;

   printf(",%c",LQ->front->data);
  }

  printf("}\n");
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})調(diào)用此方法,并且進行判斷

#include "QueueLinkControl.h"
int main(int argc, const char * argv[]) {

  //創(chuàng)建鏈隊列
  LINKQUEUE *LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
  LQ=initLinkQueue(LQ);
  //向鏈隊插入結(jié)點
  LQ=inLinkQueue(LQ,'a');
  LQ=inLinkQueue(LQ,'b');
  LQ=inLinkQueue(LQ,'c');
  LQ=inLinkQueue(LQ,'d');
  printLinkQueue(LQ);
  //刪除結(jié)點--從隊頭
  LQ=outLinkQueue(LQ);
  LQ=outLinkQueue(LQ);
  printLinkQueue(LQ);
  return 0;
}

打印結(jié)果:

in link queue success!
in link queue success!
in link queue success!
in link queue success!
queue={#,a,b,c,d}
out link queue success!
out link queue success!
queue={#,c,d}
Program ended with exit code: 0

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持我們。

上一篇：C語言數(shù)據(jù)結(jié)構(gòu)之迷宮問題

欄目：C語言

下一篇：C語言合并兩個帶頭節(jié)點升序排列鏈表

本文標題：在編程語言中怎樣定義隊列及其使用(C++)

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/406.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

在編程語言中怎樣定義隊列及其使用(C++)

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機閱讀