2023-03-02
原文作者:返回主页亦小海 原文地址:https://www.cnblogs.com/lisen10

队列

队列的定义

  • 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。
  • 队列的修改是依先进先出的原则进行的。

202303022154330781.png

队列的基本操作

1.初始化队列 InitQueue(&Q) 将队列Q设置成一个空队列。

2.入队列 EnQueue(&Q,X) 将元素X插入到队尾中,也称“进队” ,“插入”。

3.出队列 OutQueue(&Q,&e) 将队列Q的队头元素删除,并用e返回其值,也称“退队”、“删除”。

4.取队头元素 GetHead(Q,&e) 得到队列Q的队头元素之值,并用e返回其值。 5.判队空 QueueEmpty(Q) 判断队列Q是否为空,若为空返回1,否则返回0。

队列的顺序实现

在非空队列里,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一位置。

    #define MaxSize  100
    typedef int DataType;
    typedef struct{
       DataType data[MaxSize];
       int front,rear;
     }Queue;

顺序队列( MaxSize=4 )的几种状态:

202303022154336012.png

(1)表示空队列, rear==front==0。 (4)A出队后,rear==front==3。再插入元素时,会出现假溢出的情况。

克服假溢出的方法:

(1)将队列中的所有元素均向最前端的位置移动;

(2)采用循环队列。

循环队列

循环队列的物理存储未发生任何改变,其只是充分利用数组空间,想象将数组的首尾连接起来,形成一个循环队列。

202303022154340823.png

(a)表示空队列, rear==front==0。

(b)元素A入队后, rear==1, front==0。

(c)B,C依次入队后, rear==3, front==0。

(d)A,B,C出队后, front==3 ,rear==3。队列又为空

所以,循环队列为空的判定条件为:front==rear;

基本实现

    #include"stdio.h"
    #include"stdlib.h"
    
    #define Maxsize 100
    typedef int DataType;
    
    typedef struct {
        DataType data[Maxsize];
        int front,rear;
    }Queue;
    
    //初始化队列
    void InitQueue(Queue *Q)
    {
        Q->front=Q->rear=0;
    }
    //入队
    int InQueue(Queue *Q,DataType x)
    {
        if((Q->rear+1)%Maxsize==Q->front)
            return 0;
        Q->rear=(Q->rear+1)%Maxsize; //if (Q->rear+1)==Maxsize,Q->rear=0
        Q->data[Q->rear]=x;
        return 1;
    }
    //判断空队列
    int EmptyQueue(Queue *Q)
    {
        if(Q->rear==Q->front)
            return 1;
        else
            return 0;
    }
    //出队
    int OutQueue(Queue *Q,DataType *x)
    {
        if(EmptyQueue(Q))
            return 0;
        Q->front=(Q->front+1)%Maxsize;
        *x=Q->data[Q->front];
        return 1;
    }
    //取队头元素
    int GetHead(Queue *pQ,DataType *px)
    { 
        if(EmptyQueue(pQ))
          {    printf("\n Queue is free");
                return 0;
          }
          *px=pQ->data[(pQ->front+1)%MaxSize];
              return 1;
    }

循环队列中的常用判断语句

(1)队列判空条件:rear==front;

(2)队列判满条件:(rear+1)%MaxSize==front;

(3)入队操作:

第①步,先判断队列是否已满;

第②步,rear=(rear+1)%MaxSize;

第③步:尾指针位置赋值相应元素;

(4)出队操作:

第①步,先判断队列是否已空;

第②步,front=(front+1)%MaxSize;

(5)计算循环队列中元素的个数: 分两种情况讨论,如图所示:

202303022154345574.png

所以:(rear-front+MaxSize)%MaxSize。

队列的链式表示和实现

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点,而尾指针则指向队尾元素。

链队结构示意图:

202303022154349775.png

链队的数据类型定义如下:

    typedef int DataType;
    typedef struct qnode{
        DataType data;
        struct qnode *next;
    }Qtype;
    typedef struct qptr{
        Qtype *front,*rear;
    }LinkQueue;
    LinkQueue LQ;

链队运算指针变化情况:

202303022154353476.png

202303022154357647.png

202303022154362788.png

202303022154367539.png

c语言实现:

2023030221543716510.png

2023030221543758711.png

    #include"stdio.h"
    #include"malloc.h"
    typedef int DataType; //定义队列类型
    //定义队结点
    typedef struct node
    {
        DataType data;
        struct node *next;
    }qnode; //链队结点类型
     
    typedef struct
    {
        qnode *front; //定义qnode *类型的指针成员
        qnode *rear;
    }LinkQueue;
     
    //初始化队
    int InitQueue(LinkQueue *Q)
    {
        Q->front=Q->rear=(qnode *)malloc(sizeof(qnode)); //申请空间作头结点,头结点不存放数据
        if(!Q->front)  //if Q->front NULL
            return 0;
        Q->front->next=NULL; //使队头结点的指针域为NULL
        return 1;
    }
    //判断队空
    int EmptyQueue(LinkQueue *Q)
    {
        if(Q->front==Q->rear)
            return 1;
        else
            return 0;
    }
    //进队
    void InQueue(LinkQueue *Q,DataType x)
    {
        qnode *s;
        s=(qnode *)malloc(sizeof(qnode)); //申请一结点空间
        s->data=x;
        s->next=NULL; 
        Q->rear->next=s; //使s结点连上前一个结点
        Q->rear=s;  //尾指针指向结点,即最后一个结点
    }
    //出队
    int OutQueue(LinkQueue *Q,DataType *e)
    {
        qnode *q;
        if(EmptyQueue(Q))
            return 0;
        q=Q->front->next; //取头结点地址
        *e=q->data;  //返回头结点数据
        Q->front->next=q->next;  //头结点指针域存原第二结点地址
         if(Q->rear==q)  //if(Q->front->next==NULL) 若队列中只有1个元素,则出队后队列为空
             Q->rear=Q->front; 
         free(q); //释放q指向的结点,即队头结点 
        return 1;
    }

View Code

队列的应用:

  • CPU资源的竞争问题。
  • 服务、排队问题。
  • 迷宫求解。

线性表、栈与队的异同点

相同点

逻辑结构相同,都是线性的;都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表(只是对插入、删除运算加以限制)。

不同点

①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入和删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。

②用途不同,线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、多道作业处理和简化设计等。

阅读全文