隊(duì)列

1、隊(duì)列的定義
隊(duì)列（Queue）是一種先進(jìn)先出的線性表（First In Frist Out，簡稱FIFO）。只允許在表的一端（front）進(jìn)行刪除，另一端（rear）進(jìn)行插入。
隊(duì)首（front）：只允許進(jìn)行刪除的一端
隊(duì)尾（rear）：只允許進(jìn)行插入的一端
隊(duì)列中沒有元素的時(shí)候成為空隊(duì)列。在空隊(duì)列中依次加入元素a1,a2,...,an之后，a1是隊(duì)首元素，an是隊(duì)尾元素。所以退出隊(duì)列的次序是a1,a2,...,an，按照先進(jìn)先出的原則進(jìn)行。

隊(duì)列.jpg

2.隊(duì)列的主要操作
（1）清空隊(duì)列
（2）判斷是否為空
（3）元素的個(gè)數(shù)
（4）入隊(duì)列
（5）出隊(duì)列
（6）取隊(duì)頭元素
3.順序?qū)崿F(xiàn)隊(duì)列
隊(duì)列數(shù)組實(shí)現(xiàn).png

存在問題
設(shè)數(shù)組長度為M,則：
當(dāng)front=0，rear=M，再有元素入隊(duì)時(shí)發(fā)生溢出----真溢出
當(dāng)front!=0，rear=M，再有元素入隊(duì)時(shí)發(fā)生溢出----假溢出
解決方案
循環(huán)隊(duì)列：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[m-1]之后，若rear+1==M，則令rear=0。
循環(huán)隊(duì)列.png

順序?qū)崿F(xiàn)隊(duì)列
（1）

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

定義了隊(duì)列結(jié)構(gòu)的最大長度是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ì)列滿。

（2）初始化隊(duì)列數(shù)據(jù)
<1>按符號(hào)常量QUEUELEN指定的大小申請一段內(nèi)存空間，用來保存隊(duì)列中的數(shù)據(jù)。
<2>設(shè)置head=0和tail=0，表示一個(gè)空棧。

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

（3）判斷空隊(duì)列
判斷空隊(duì)列是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為空。如果是空，此時(shí)隊(duì)列可以進(jìn)行入隊(duì)操作，不可以進(jìn)行出隊(duì)操作。

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

（4）判斷滿隊(duì)列
判斷滿隊(duì)列就是判斷一個(gè)隊(duì)列結(jié)構(gòu)是否為滿。滿隊(duì)列不可以進(jìn)行入隊(duì)操作，可以進(jìn)行出隊(duì)操作

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

（5）清空隊(duì)列

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

（6）釋放空間
釋放空間是釋放隊(duì)列結(jié)構(gòu)所占用的內(nèi)存空間，前面用new關(guān)鍵字分配的內(nèi)存單元，可以用delete釋放。

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

（7）入隊(duì)列
<1>判斷隊(duì)尾，如果tail等于QUEUELEN，隊(duì)列滿不能插入數(shù)據(jù)。
<2>設(shè)置tail=tail+1
<3>將入隊(duì)元素保存到tail指向的位置

int InSQType(SQType *q,DATA data)
{
 if(q -> tail == QUEUELEN)
  {
    cout<<"隊(duì)列已滿，操作失?。?！"<<endl;
  }
 else
 {
    q -> data[q -> tail++] = data;
     return 1;
 }
}

（8）出隊(duì)列
<1>判斷隊(duì)首head，如果head等于tail，則表示隊(duì)列為空
<2>從隊(duì)列首部取出隊(duì)頭元素（實(shí)際返回隊(duì)頭元素的指針）
<3>修改隊(duì)首head的序號(hào)，指向后一個(gè)元素

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

（9）讀節(jié)點(diǎn)數(shù)據(jù)
讀節(jié)點(diǎn)數(shù)據(jù)就是讀隊(duì)頭的數(shù)據(jù)

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

（10）計(jì)算隊(duì)列長度
計(jì)算隊(duì)列長度就是計(jì)算該隊(duì)列中數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)。用隊(duì)尾序號(hào)減去隊(duì)首序號(hào)。

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

源代碼：http://pan.baidu.com/s/1qYKZG76
截圖：

結(jié)果.png

4.鏈表實(shí)現(xiàn)隊(duì)列

#include <stdio.h>
#include <stdlib.h>

#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr, "%s\n", str),exit(1)

typedef int ElementType;
#define MAXQUEUE 10

typedef struct node
{
  ElementType data;
  struct node* nextNode;
}Node;

typedef struct queue
{
  Node* front; //隊(duì)首指針
  Node* rear;//隊(duì)尾指針
  int items;//隊(duì)列中項(xiàng)目個(gè)數(shù)
}*ptrQueue;

typedef ptrQueue Queue;
int IsEmpty(Queue q);
int IsFull(Queue q);
Queue CreateQueue(void);
void DisposeQueue(Queue q);
void MakeEmpty(Queue q);
void Enqueue(ElementType x, Queue q);
ElementType Front(Queue q);
void Dequeue(Queue q);
ElementType FrontAndDequeue(Queue q);

int main(void)
{
  Queue sqQueue;
  
  sqQueue = CreateQueue();
  if(IsEmpty(sqQueue))
    printf("創(chuàng)建一個(gè)空隊(duì)列");
  
  int value = 0;
  printf("隊(duì)列中的數(shù)據(jù)為（front -> rear）: \n");
  while(!IsFull(sqQueue))
  {
    Enqueue(value*value, sqQueue);//入隊(duì)
    printf("%d", value*value);
    value++;
  }
  printf("隊(duì)列已滿\n");

  ElementType frontQueue;
  frontQueue = Front(sqQueue);
  printf("對(duì)頭元素為： %d\n",frontQueue);
  
  Dequeue(sqQueue);
  frontQueue = Front(sqQueue);
  printf("執(zhí)行出隊(duì)操作Dequeue之后，對(duì)頭元素是： %d\n",frontQueue);
  DisposeQueue(sqQueue);
  return 0;
}

/***是否為空***/
int IsEmpty(Queue q)
{
  return q -> items == 0;
}

/***是否已滿***/
int IsFull(Queue q)
{
  return q -> items == MAXQUEUE;
}

/***創(chuàng)建隊(duì)列***/
Queue CreateQueue(void)
{
  Queue q;
  
  q = (Queue)malloc(sizeof(struct queue));
  if(NULL == q)
    Error("空間不足，隊(duì)列分配內(nèi)存失??！");

  q -> front = (Node*)malloc(sizeof(Node));
  if(NULL == q -> front)
    Error("空間不足，隊(duì)列首節(jié)點(diǎn)內(nèi)存分配失敗！");
  
  q -> rear = (Node*)malloc(sizeof(Node));
  if(NULL == q -> rear)
    Error("空間不足，隊(duì)列尾節(jié)點(diǎn)內(nèi)存分配失?。?);

  q -> items = 0;

  return q;
}

/***釋放隊(duì)列***/
void DisposeQueue(Queue q)
{
  MakeEmpty(q);
  free(q);
}

/***使隊(duì)列為空***/
void MakeEmpty(Queue  q)
{
  if(q == NULL)
    Error("必須先使用CreateQueue創(chuàng)建隊(duì)列！");

  while(IsEmpty(q))
    Dequeue(q);
}

/***入隊(duì)***/
void Enqueue(ElementType x, Queue q)
{
  if(IsFull(q))
    Error("隊(duì)列已滿");
  
  Node* pnode;
  pnode = (Node*)malloc(sizeof(Node));
  if(NULL == pnode)
    Error("新節(jié)點(diǎn)分配內(nèi)存失?。?);

  pnode -> data = x;
  pnode -> nextNode = NULL;
  if(IsEmpty(q))
    q -> front = pnode;//隊(duì)列為空數(shù)據(jù)插入隊(duì)首位置
  else
    q -> rear -> next = pnode;//隊(duì)列不為空，元素放在隊(duì)尾指針的下一個(gè)位置
  q -> rear = pnode;//隊(duì)列尾指針指向pnode節(jié)點(diǎn)
  q -> items++;//隊(duì)列項(xiàng)目數(shù)加1

  return;
}

/***出隊(duì)***/
void Dequeue(Queue q)
{
  if(IsEmpty(q))
    Error("隊(duì)列本身為空");

  Node* pnode;
  pnode = q -> rear;
  q -> front = q -> front -> nextNode;
  free(pnode);

  q -> items--;
  if(q -> items == 0)
    q -> rear = NULL;

  return;
}

/***返回隊(duì)列頭元素***/
ElementType Front(Queue q)
{
  if(!IsEmpty(q))
    return q -> front -> data;
  Error("隊(duì)列為空\n");

  return 0;
}

/***返回對(duì)頭元素并使對(duì)頭元素出隊(duì)***/
ElementType FrontAndDequeue(Queue q)
{
  ElementType x;
  
  if(IsEmpty(q))
    Error("隊(duì)列為空\n");
  else
  {
    q -> items--;
     x =q -> front -> data;
     q -> front = q -> front -> nextNode;
  }
  
  return x;
}

源代碼：http://pan.baidu.com/s/1o8jkZcI
截圖：

單鏈表實(shí)現(xiàn)隊(duì)列.png

3.不使用動(dòng)態(tài)創(chuàng)建內(nèi)存（malloc）而是申請固定地址來實(shí)現(xiàn)隊(duì)列

typedef struct qq_link_struct
{
  struct qq_link_struct *ptr;//相當(dāng)于nextNode下一個(gè)節(jié)點(diǎn)
}qq_link_type;

typedef struct qq_struct
{
  qq_link_type head;//隊(duì)列頭指針
  qq_link_type tail;//隊(duì)列尾指針
   int cnt;//記錄隊(duì)列數(shù)據(jù)個(gè)數(shù)
}qq_type;

（1）初始化隊(duì)列

qq_type* qq_init(qq_type *q_ptr)
{
  q_ptr -> head.ptr = &q_ptr -> head;//
  q_ptr -> tail.ptr = &q_ptr -> head;//初始時(shí)隊(duì)列為空，q_ptr的頭指針。尾指針都指向head
  q_ptr -> cnt = 0;
  return q_ptr;
}

（2）插入數(shù)據(jù)

/***隊(duì)列尾部只能進(jìn)行插入**/
void qq_put(qq_type *q_ptr,qq_link_type * link_ptr)
{
  link_ptr -> ptr = &q_ptr -> head;//link指向插入數(shù)據(jù)
  q_ptr -> tail.ptr -> ptr = link_ptr;//隊(duì)列尾部插入數(shù)據(jù)
  q_ptr -> tail.ptr = link_ptr;//改變隊(duì)列尾指針
  q_ptr -> cnt++;
}

（3）取出數(shù)據(jù)

/***隊(duì)列頭部只能取數(shù)據(jù)***/
void* qq_get(qq_type * q_ptr)
{
  qq_link_type *ret_ptr = 0;
  if(q_ptr -> cnt > 0 )//cnt大于0隊(duì)列才有數(shù)據(jù)可以取出來
  {
    ret_ptr = q_ptr -> head.ptr;//存放取出的數(shù)據(jù)
    q_ptr -> head.ptr = ret_ptr -> ptr;//改變隊(duì)列頭指針
    q_ptr -> cnt--;
    if(q_ptr -> cnt ==0)
    {
      q_ptr -> tail.ptr = &q_ptr -> head;//當(dāng)隊(duì)列中沒有數(shù)據(jù)尾指針指向隊(duì)列頭
    }
  }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容