当前位置：首页 > news >正文

实现一个队列

news 2025/5/24 8:21:58

操作：

push x：将 x 加入队尾，保证 x 为 int 型整数。

pop：输出队首，并让队首出队

front：输出队首：队首不出队

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MaxSize 100000  // 定义队列的最大容量为100,000char s[20];  // 用于存储输入的命令// 定义顺序队列结构体
struct SqQueue {int data[MaxSize]; // 存储队列元素的数组int front; // 队列头部的索引int rear;  // 队列尾部的索引
} Q;// 初始化队列，将队列头和尾指针都设为0，表示队列为空
void InitQueue(){ Q.front = Q.rear = 0;
}// 检查队列是否为空
int isEmpty(){ if(Q.rear == Q.front){  // 如果队列头尾指针相等，说明队列为空printf("error\n");  // 打印错误信息return 1;  // 返回1表示队列为空}return 0;  // 返回0表示队列非空
}// 入队操作，将输入的数字存入队列
void _push(char *s){ // 检查队列是否已满，如果满了就不进行任何操作if((Q.rear + 1) % MaxSize == Q.front){return;}int sl = strlen(s);  // 获取输入字符串的长度（可省略，未使用）char sr[10];  // 用于存储从命令中提取的数字字符串strcpy(sr, s + 5);  // 将字符串中从第6个字符开始的部分复制到sr中（跳过"push "部分）int m = atoi(sr);  // 将提取的字符串转换为整数Q.data[Q.rear] = m;  // 将整数存入队列尾部Q.rear = (Q.rear + 1) % MaxSize;  // 更新队列尾指针，循环队列特性
}// 出队操作，移除队列头部的元素并打印
void _pop(){ if(isEmpty() == 1){  // 如果队列为空，直接返回return;}int x = Q.data[Q.front];  // 获取队列头部元素Q.front = (Q.front + 1) % MaxSize;  // 更新队列头指针，循环队列特性printf("%d\n", x);  // 打印出队的元素
}// 查看队列头部的元素
void _front(){if(isEmpty() == 1){  // 如果队列为空，直接返回return;}printf("%d\n", Q.data[Q.front]);  // 打印队列头部的元素
}// 主函数，处理用户输入的命令并执行相应操作
int main(){InitQueue();  // 初始化队列int n;scanf("%d", &n);  // 读取命令的数量getchar();  // 吸收换行符for (int i = 0; i < n; i++){gets(s);  // 读取命令字符串if (s[1] == 'u'){  // 如果命令是"push"，执行入队操作_push(s);}else if(s[1] == 'o'){  // 如果命令是"pop"，执行出队操作_pop();}else if(s[1] == 'r'){  // 如果命令是"front"，查看队列头部元素_front();}}return 0;  // 程序结束
}

1. 头文件和宏定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MaxSize 100000

#include <stdio.h>：包含标准输入输出库，用于输入输出操作。
#include <stdlib.h>：包含标准库函数，如atoi，用于字符串转整数。
#include <string.h>：包含字符串处理函数，如strlen和strcpy。
#define MaxSize 100000：定义了队列的最大容量为100,000。

2. 全局变量和结构体定义

char s[20]; struct SqQueue{int data[MaxSize]; int front;int rear;
} Q;

char s[20]：定义一个字符数组 s用于存储输入的命令。
struct SqQueue：定义了一个顺序队列（SqQueue）的数据结构，包含：
- data[MaxSize]：用于存储队列元素的数组。
- front：指向队列头部元素的索引。
- rear：指向队列尾部元素的索引。

3. 初始化队列

void InitQueue(){ Q.front=Q.rear=0;
}

InitQueue函数将front和rear都初始化为0，表示队列为空。

4. 检查队列是否为空

int isEmpty(){ if(Q.rear==Q.front){printf("error\n"); return 1;}return 0;
}

isEmpty函数通过检查rear和front是否相等来判断队列是否为空。如果队列为空，返回1，并打印"error"。

5. 元素入队

void _push(char *s){ if((Q.rear+1)%MaxSize==Q.front){return;}int sl=strlen(s);char sr[10];strcpy(sr,s+5);int m=atoi(sr);Q.data[Q.rear]=m;Q.rear=(Q.rear+1)%MaxSize;
}

_push函数用于将一个元素加入队列。

首先检查队列是否已满，如果满了就直接返回。
从输入命令中提取数字部分，并将其转换为整数m。
将整数m存入data[rear]，然后更新rear指针。

6. 元素出队

void _pop(){ if(isEmpty()==1){return;}int x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;printf("%d\n",x);
}

_pop函数用于移除队列头部的元素并打印。
- 如果队列为空，则直接返回。
- 否则，取出front位置的元素，并更新front指针，然后打印该元素。

7. 获取队列头部元素

void _front(){if(isEmpty()==1){return;}printf("%d\n",Q.data[Q.front]);
}

_front函数用于打印队列头部的元素但不移除它。
- 如果队列为空，则直接返回。
- 否则，打印front位置的元素。

8. 主函数

int main(){InitQueue();int n;scanf("%d",&n);getchar();for (int i=0;i<n;i++){gets(s);if (s[1]=='u'){_push(s);}else if(s[1]=='o'){_pop();}else if(s[1]=='r'){_front();}}return 0;
}