数据结构实验之队列（文末附完整代码）

目录

（1）队的定义

（2）队的基本操作：

 完整代码：

main.c部分：

 SeqQueue.c部分

SeqQueue.h部分

---

队列是一种线性数据结构，用于在程序中按照特定顺序组织和操作元素。它遵循先进先出（First-In-First-Out，FIFO）的原则，即最先进入队列的元素最先被处理，而最后进入的元素最后被处理。

队列可以类比为现实生活中的排队场景，人们按照到达的先后顺序排队等待服务。类似地，队列中的元素也按照顺序加入队列并离开队列。

队列有两个主要操作：

1. 入队（enqueue）：将元素添加到队列的尾部。
2. 出队（dequeue）：从队列的头部移除并返回元素。

这两个操作使得队列满足了先进先出的特性。新元素总是被添加到队列的末尾，而从队列中移除元素时，总是从队列的开头进行。

除了入队和出队操作之外，队列还可以提供其他一些常见的操作，如：

• 获取队列的长度
• 检查队列是否为空
• 获取队列的头部元素，但不删除它

队列的应用非常广泛，例如：

• 高级语言编译器中的编译错误消息队列
• 操作系统中的进程调度
• 网络通信中的数据包缓冲区
• 广度优先搜索算法（BFS）
• 银行柜台的客户排队等待服务

（1）队的定义

这段代码定义了一个顺序队列（Sequential Queue）的数据结构。以下是对每个部分的解释：

1. typedef int ElemType;：这段代码定义了队列中元素的类型为整数（int）。你可以根据需求将其修改为其他类型。

2. #define MAXSIZE 100：这段代码定义了队列的初始存储空间大小，该队列最多可以容纳100个元素。你可以根据实际需要修改这个值。

3. typedef struct SeqQueue：这是定义顺序队列的开始。

4. ElemType *base：这是队列存储空间的基地址，它是一个指向元素类型（ElemType）的指针。

5. int front：这是队列的头部指针，指向队列中第一个元素。

6. int rear：这是队列的尾部指针，指向队列中最后一个元素的下一个位置。

7. int size：这是队列中元素的数量。通过front和rear之间的位置关系可以计算得出。

 

（2）队的基本操作：

void initQueue(SeqQueue *s);//初始化队列

代码：

这个函数可以用来初始化一个队列。它会为队列分配一块存储空间，并将队列的头部指针、尾部指针和元素数量都设置为初始值，使得队列处于空的状态。你可以调用这个函数来初始化一个队列，然后就可以对这个队列进行入队和出队操作了 

bool isQueueFull(SeqQueue *s);//判断队列是否已满

代码：

这段代码是一个函数，用于判断队列是否已满的函数。该函数接受一个指向 SeqQueue 结构的指针作为参数，并返回布尔值 (true 或 false)。以下是对每行代码的解释：

bool isQueueFull(SeqQueue *q) 

 

这是函数的声明，它定义了一个名为 isQueueFull 的函数，该函数接受一个指向 SeqQueue 结构的指针作为参数，并返回布尔值 (true 或 false)。

if(q->size==MAXSIZE)；

这行代码判断队列中元素的数量 (size) 是否等于队列的最大容量 (MAXSIZE)。如果相等，表示队列已满，执行下面的代码块。

如果队列已满，返回 true。

如果队列未满，返回 false。

bool isQueueEmpty(SeqQueue *s);//判断队列是否为空

代码：

 

用于判断队列是否为空的函数。以下是对代码的解释：

这是函数的声明，它定义了一个名为 isQueueEmpty 的函数，该函数接受一个指向 SeqQueue 结构的指针作为参数，并返回布尔值 (true 或 false)。

这行代码判断队列中元素的数量 (size) 是否等于 0。如果相等，表示队列为空，执行下面的代码块。

如果队列为空，返回 true。

如果队列不为空，返回 false。

void enqueue(SeqQueue *s,ElemType x);//入队

代码：

该函数接受一个指向 SeqQueue 结构的指针 q 和一个要入队的元素 item。它将元素 item 存储在队列的 rear 所指向的位置，并将队列的 rear 值加一。然后，它将队列中元素的数量 size 加一表示队列长度增加了一个元素。

这个函数用于往队列中添加元素，实现了队列的入队操作。调用这个函数可以将指定元素添加到队列的末尾。

 

ElemType dequeue(SeqQueue *s);//出队

代码：

该函数接受一个指向 SeqQueue 结构的指针 q。它将队列中的元素移除，实现了出队操作。这里的实现方式并不严格符合队列的操作规定，因为这个函数没有返回出队元素的值，而是直接返回了 0。正确的做法应该是在函数体内将出队元素的值返回。

具体来说，这个函数将队列中头元素（即下标为 front 的元素）置为 0，并将队列的 front 值加一表示头指针向后移动了一位。然后，它将队列中元素的数量 size 减一表示队列长度减少了一个元素。

这个函数用于从队列中移除元素，实现了队列的出队操作。调用这个函数可以将队列中的头元素移除。

ElemType getFront(SeqQueue *s); //获得队头元素

代码：

这个函数接受一个指向 SeqQueue 结构的指针 q。它返回队列头部元素的值，即队列中下标为 front 的位置上的元素。

通过调用这个函数，你可以获取到队列的头部元素，而不进行出队操作。这个函数不改变队列的状态，只返回队列头部元素的值。

ElemType getRear(SeqQueue *s); //获得队尾元素

代码：

这个函数接受一个指向 SeqQueue 结构的指针 q。它返回队列尾部元素的值，即队列中下标为 rear-1 的位置上的元素。

通过调用这个函数，你可以获取到队列的尾部元素，而不进行出队操作。这个函数不改变队列的状态，只返回队列尾部元素的值。

void destroyQueue(SeqQueue *s);//销毁队列

代码：

该函数接受一个指向 SeqQueue 结构的指针 q。它用于销毁队列，将队列恢复到初始状态。

具体来说，这个函数将队列中元素的数量 size、头指针 front 和尾指针 rear 都设置为 0，表示队列为空，没有任何元素。

通过调用这个函数，你可以销毁队列及其内部的数据结构，并释放相关的内存资源。注意，这段代码只是将队列状态重置，实际的内存释放工作可能需要在外部进行。

 

 完整代码：

main.c部分：

#include "SeqQueue.h"
 
int main()
{
 /*   SeqQueue q0; SeqQueue q1; SeqQueue q2;
    initQueue(&q0);initQueue(&q1);initQueue(&q2);*/
    SeqQueue q;
    initQueue(&q);
 if(isQueueFull(&q)){
    printf("队列已满！\n");
 }
 else printf("队列未满！\n");
 if(isQueueEmpty(&q)){
    printf("队列空\n");
 }
 else printf("队列不空\n");
    int n;
    printf("输入要入队的n个元素：\n");
    scanf("%d",&n);
    for(int i=0;i
    {
        int item;
        scanf("%d",&item);
        enqueue(&q, item);
    }
    printf("输入要出队的n个元素：\n");
    scanf("%d",&n);
    for(int i=0;i
    {
        dequeue(&q);
    }
    printf("队头元素为：%d\n",getFront(&q));
    printf("队尾元素为：%d\n",getRear(&q));
    /*char k[101],l;
        gets(k);
    l=strlen(k);
    for(int i=0;i
    {
        if(k[i]=='{')
            {
                enqueue(&q0, k[i]);
            }
        else  if(k[i]=='(')
            {
                enqueue(&q1, k[i]);
            }
        else if(k[i]=='[')
            {
                enqueue(&q2, k[i]);
            }
        else if(!isQueueEmpty(&q0)&&k[i]=='}'){
            dequeue(&q0);
        }
        else if(!isQueueEmpty(&q1)&&k[i]==')'){
            dequeue(&q1);
        }
        else if(!isQueueEmpty(&q2)&&k[i]==']'){
            dequeue(&q2);
        }
        else if(isQueueEmpty(&q0)&&k[i]=='}'){
            printf("括号序列错误！\n");return 0;
        }
        else if(isQueueEmpty(&q1)&&k[i]==')'){
           printf("括号序列错误！\n");return 0;
        }
        else if(isQueueEmpty(&q2)&&k[i]==']'){
            printf("括号序列错误！\n");return 0;
        }
    }
    if(isQueueEmpty(&q0)&&isQueueEmpty(&q1)&&isQueueEmpty(&q2))
    {
        printf("括号序列正确！\n");
    }
    else {
        printf("括号序列错误！\n");
    }
    destroyQueue(&q0);destroyQueue(&q1);destroyQueue(&q2);*/
    return 0;
}

 SeqQueue.c部分

#include "SeqQueue.h"
 
// 初始化队列
void initQueue(SeqQueue *q) {
    q->base=(QElemType *)malloc(sizeof(QElemType)*MAXSIZE);
    q->front=q->rear=0;
    q->size=0;
}
 
// 判断队列是否已满
bool isQueueFull(SeqQueue *q) {
    if(q->size==MAXSIZE){
        return true;
    }
    else return false;
}
 
// 判断队列是否为空
bool isQueueEmpty(SeqQueue *q) {
    if(q->size==0){
        return true;
    }
    else return false;
}
 
// 入队操作
void enqueue(SeqQueue *q, QElemType item) {
    q->base[q->rear++]=item;
    q->size++;
}
 
// 出队操作
QElemType dequeue(SeqQueue *q) {
    q->base[q->front++]=0;
    q->size--;
    return 0;
}
 
// 获取队列头元素
QElemType getFront(SeqQueue *q) {
    return q->base[q->front];
}
 
// 获取队列尾元素
QElemType getRear(SeqQueue *q) {
    return q->base[q->rear-1];
}
 
void destroyQueue(SeqQueue *q) {
    q->size=0;
    q->front=q->rear=0;
}

SeqQueue.h部分

#include 
#include 
#include 
#include 
#include 
 
typedef char QElemType;//定义栈中元素类型
#define MAXSIZE 100 //定义顺序栈初始存储空间大小
 
typedef struct SeqQueue  //定义栈结构
{
    QElemType *base; //顺序栈存储空间基地址
    int front;  // 队列头
    int rear;  // 队列尾
    int size;  // 队列中元素数量
} SeqQueue;
 
void initQueue(SeqQueue *s);//初始化队列
bool isQueueFull(SeqQueue *s);//判断队列是否已满
bool isQueueEmpty(SeqQueue *s);//判断队列是否为空
void enqueue(SeqQueue *s,QElemType x);//入队
QElemType dequeue(SeqQueue *s);//出队
QElemType getFront(SeqQueue *s); //获得队头元素
QElemType getRear(SeqQueue *s); //获得队尾元素
void destroyQueue(SeqQueue *s);//销毁队列

感谢大家观看，有疑问评论区留言哈，感谢大家动动小手点个赞哦！！！