队列—顺序结构

╰半夏微凉° 2024-04-17 16:03 154阅读 0赞

### 队列—顺序结构 ###

*  1、定义
 *  2、相关术语
 *  3、假溢出
 *  4、解决假溢出的方法
 *  5、循环队列
 *  6、循环队列代码

# 1、定义 #

只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表

![在这里插入图片描述][20190828131451168.png]

特点：  
\*先进先出  
\*存储单元逻辑上连续，地址也连续

# 2、相关术语 #

\*队头：允许删除数据的一端  
\*队尾：允许插入数据的一端  
\*头指针：指向队头元素的指针  
\*尾指针：指向队尾元素的下一个位置的指针

# 3、假溢出 #

顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况

例如：  
![图1][1]  
如上图所示可以存储5个元素的队列，若在下标为4的位置插入一个元素后，则rear指针向后移动一个位置，就会出现如下图所示的情况：  
![图2][2]  
看似队列已满，但实际上0、1位置还是空的，这种情况就叫做假溢出。

# 4、解决假溢出的方法 #

1）采用顺序循环队列；  
2）按最大可能的进队操作次数设置顺序队列的最大的元素个数；（最差的方法）  
3）修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；  
4）修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。

# 5、循环队列 #

\->定义：

即队列采用头尾相接的顺序存储结构

\->循环队列队满和队空的判断：

由于循环队列存在当队列为空或者队列为满时头指针（front）等于尾指针（rear）的问题，故可以通过以下三种方法解决。  
1）设置一个flag。当front=rear时，若队列为空，则令flag=0；若队列已满，则令flag=1。

2）设置一个计数器counter。当front=rear时，若队列为空，则counter=0；若队列已满，则counter>0。

3）始终留一个元素空间来放尾指针。当队列满时（rear+1）%MAXSIZE=front；若队列未满，则等式不成立；若队列为空，则rear=front。

注：

\*QueueSize是队列能存储元素的最大个数。  
\*由于rear可能比front大，也可能比front小，虽然它们只相差一个元素就说明队列已满，但是有可能相差整整一圈。故（rear+1）%QueueSize=front中的%就是为了解决rear与front的大小问题的。  
\*前两种方法不会造成一个存储空间“浪费”，第三种方法会造成一个元素空间“浪费”。

如图：队列满的情况（QueueSize=5）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]  
\->循环队列的元素个数：

1）如下图所示，当rear>front时，队列的元素个数为：rear-front  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 1]  
2）如下图所示，当rear<front时，队列的元素个数分为两部分：第一部分为0+rear；第二部分为QueueSize-front，则整个队列的长度为两部分之和：（0+rear）+（QueueSize-front）= rear-front+QueueSize  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 2]  
综合以上两种情况，可得队列长度的计算公式为：（rear-front+QueueSize）% QueueSize

# 6、循环队列代码 #

注：根据循环队列队满和队空的判断方法中的第二种方法编写。

queue.h

#ifndef Queue_H
    #define Queue_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 10
    
    typedef int Status;
    typedef int DataType;
    typedef struct SeqQueue{ 
        DataType data[MAXSIZE];
        int front;
        int rear;
        int counter;
    }Queue;
    
    int GetQueueLength(Queue queue);                     //获取队列的长度
    Status InitiateQueue(Queue *queue);                  //初始化队列
    Status IfQueueIsEmpty(Queue queue);                  //判断队列是否为空
    Status EnterQueueData(Queue *queue, DataType elem);  //入队列
    Status OutQueueData(Queue *queue, DataType *elem);   //出队列
    Status GetQueueElement(Queue *queue, DataType *elem);//取队头元素
    
    #endif // MAINWINDOW_H

queue.c

#include "queue.h"
    
    //初始化队列
    Status InitiateQueue(Queue *queue)
    { 
        queue->front = 0;
        queue->rear = 0;
        queue->counter = 0;
    
        return TRUE;
    }
    
    //判断队列是否为空
    Status IfQueueIsEmpty(Queue queue)
    { 
        if (queue.counter == 0)
        { 
            printf("队列已空！\n");
            return FALSE;
        }
        else
            return TRUE;
    }
    
    //获取队列的长度
    int GetQueueLength(Queue queue)
    { 
        return queue.counter;
    }
    
    //入队列
    Status EnterQueueData(Queue *queue, DataType elem)
    { 
        if (queue->counter > 0 && queue->rear == queue->front) //队列满的判断
        { 
            printf("队列已满无法插入! \n");
            return FALSE;
        }
        else
        { 
            queue->data[queue->rear] = elem;
            queue->rear = (queue->rear + 1) % MAXSIZE; //将rear指针向后移一位置，若到最后则转到数组头部
            queue->counter++;
            return TRUE;
        }
    }
    
    //出队列
    Status OutQueueData(Queue *queue, DataType *elem)
    { 
        if (queue->counter == 0) //队列为空的判断
        { 
            printf("队列已空！\n");
            return FALSE;
        }
        else
        { 
            *elem = queue->data[queue->front];
            queue->front = (queue->front + 1) % MAXSIZE;
            queue->counter--;
            return TRUE;
        }
    }
    
    //取队头元素
    Status GetQueueElement(Queue *queue, DataType *elem)
    { 
        if (queue->counter == 0)
        { 
            printf("队列已空无数据元素可取! \n");
            return FALSE;
        }
        else
        { 
            *elem = queue->data[queue->front];
            return TRUE;
        }
    }

main.c

#include "queue.h"
    
    int main()
    { 
        Queue myQueue;
        int x = 0;
        InitiateQueue(&myQueue);
    
        for(int i = 0; i < 10; i++)
        { 
            EnterQueueData(&myQueue, i+1);
        }
    
        GetQueueElement(&myQueue, &x);
        printf("当前队头元素为：%d\n", x);
    
        printf("依次出队列的元素序列如下：\n");
        while(IfQueueIsEmpty(myQueue))
        { 
            OutQueueData(&myQueue, &x);
            printf("%d ", x);
        }
    
        return 0;
    }

注：根据循环队列队满和队空的判断方法中的第三种方法编写。  
queue.h

#ifndef Queue_H
    #define Queue_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 10
    
    typedef int Status;
    typedef int DataType;
    typedef struct SeqQueue{ 
        DataType data[MAXSIZE];
        int front;
        int rear;
    }Queue;
    
    int GetQueueLength(Queue queue);                     //获取队列的长度
    Status InitiateQueue(Queue *queue);                  //初始化队列
    Status IfQueueIsEmpty(Queue queue);                  //判断队列是否为空
    Status EnterQueueData(Queue *queue, DataType elem);  //入队列
    Status OutQueueData(Queue *queue, DataType *elem);   //出队列
    Status GetQueueElement(Queue *queue, DataType *elem);//取队头元素
    
    #endif // MAINWINDOW_H

queue.c

#include "queue.h"
    
    //初始化队列
    Status InitiateQueue(Queue *queue)
    { 
        queue->front = 0;
        queue->rear = 0;
    
        return TRUE;
    }
    
    //获取队列的长度
    int GetQueueLength(Queue queue)
    { 
        return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
    }
    
    //入队列
    Status EnterQueueData(Queue *queue, DataType elem)
    { 
        if ((queue->rear + 1) % MAXSIZE == queue->front) //队列满的判断
        { 
            printf("队列已满无法插入! \n");
            return FALSE;
        }
        else
        { 
            queue->data[queue->rear] = elem;
            queue->rear = (queue->rear + 1) % MAXSIZE; //将rear指针向后移一位置，若到最后则转到数组头部
            return TRUE;
        }
    }
    
    //出队列
    Status OutQueueData(Queue *queue, DataType *elem)
    { 
        if (queue->front == queue->rear) //队列为空的判断
        { 
            printf("队列已空！\n");
            return FALSE;
        }
        else
        { 
            *elem = queue->data[queue->front];
            queue->front = (queue->front + 1) % MAXSIZE;
            return TRUE;
        }
    }
    
    //判断队列是否为空
    Status IfQueueIsEmpty(Queue queue)
    { 
        if (queue.front == queue.rear)
        { 
            printf("队列已空！\n");
            return FALSE;
        }
        else
            return TRUE;
    }
    
    //取队头元素
    Status GetQueueElement(Queue *queue, DataType *elem)
    { 
        if (queue->front == queue->rear)
        { 
            printf("队列已空！\n");
            return FALSE;
        }
        else
        { 
            *elem = queue->data[queue->front];
            return TRUE;
        }
    }

main.c

#include "queue.h"
    
    int main()
    { 
        Queue myQueue;
        int x = 0;
        InitiateQueue(&myQueue);
    
        for(int i = 0; i < 9; i++)
        { 
            EnterQueueData(&myQueue, i+1);
        }
    
        GetQueueElement(&myQueue, &x);
        printf("当前队头元素为：%d\n", x);
    
        printf("依次出队列的元素序列如下：\n");
        while(IfQueueIsEmpty(myQueue))
        { 
            OutQueueData(&myQueue, &x);
            printf("%d ", x);
        }
    
        return 0;
    }

[20190828131451168.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/89d696e644814ce78b9b1ebf770f3ae2.png
[1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/309291fa726b47b59992307ee06402c8.png
[2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d81bf1b0ce1846b4868845bb016a5fc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/9125b239f1a54f70aab2a36426d73a9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/91400988c06446219e4f2f6fb9f6c559.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcwNDA5MA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/246b9f65b08646d397f6db59bf749d36.png