队列重点操作代码集锦_队列出队代码

目录

队列的介绍

链队列的重点操作

1.队列的创建和初始化

2.入队

3.出队

4.取队头元素

5.输出队列

6.全部操作代码

循环队列的重点操作

1.队列的创建和初始化

2.入队

3.出队

4.取队头元素

5.求队列长度

6.输出队列

7.全部操作代码

队列的应用

1.编写一个打印二项式系数表（即杨辉三角）

2.运动会划分子集问题

队列的介绍

队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性表。

在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。

链队列的重点操作

1.队列的创建和初始化

typedef struct {
	int data;
	struct QNode* next;
}QNode;
 
typedef struct {
	QNode* front;//队头指针
	QNode* rear;//队尾指针
}LinkQueue;
 
//初始化
LinkQueue* InitQueue() {
	LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针
	Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点
	Q->rear = Q->front;
	Q->front->next = NULL;//头结点指针域置空
	return Q;
}

2.入队

//入队
void EnQueue(LinkQueue* Q, int e) {
	QNode* p = malloc(sizeof(QNode));//生成新结点
	p->data = e;//新结点数据域置为e，指针域置空
	p->next = NULL;
	Q->rear->next = p;//新结点插入队尾
	Q->rear = p;//修改队尾指针
}

3.出队

//出队
bool DeQueue(LinkQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;//p指向队头元素
	*e = p->data;//e保存队头元素
	Q->front->next = p->next;//修改头结点指针域
	if (Q->rear == p)	Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点
	free(p);//释放队头元素空间
	return true;
}

4.取队头元素

//取队头元素
bool GetHead(LinkQueue* Q, int* e) {
	//返回队头元素，不修改队头指针
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;
	*e = p->data;//用e返回队头元素值
	return true;
}

5.输出队列

//输出
void print(LinkQueue* Q) {
	//前提为队不为空
	printf("(front) ");
	if (Q->front != Q->rear) {
		QNode* p = Q->front->next;
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
	}
	printf("(rear)\n");
}

6.全部操作代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//使用bool类型的头文件 
 
typedef struct {
	int data;
	struct QNode* next;
}QNode;
 
typedef struct {
	QNode* front;//队头指针
	QNode* rear;//队尾指针
}LinkQueue;
 
//初始化
LinkQueue* InitQueue() {
	LinkQueue* Q = malloc(sizeof(LinkQueue));//生成队头队尾指针
	Q->front = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头队尾指针指向该结点
	Q->rear = Q->front;
	Q->front->next = NULL;//头结点指针域置空
	return Q;
}
//入队
void EnQueue(LinkQueue* Q, int e) {
	QNode* p = malloc(sizeof(QNode));//生成新结点
	p->data = e;//新结点数据域置为e，指针域置空
	p->next = NULL;
	Q->rear->next = p;//新结点插入队尾
	Q->rear = p;//修改队尾指针
}
//出队
bool DeQueue(LinkQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;//p指向队头元素
	*e = p->data;//e保存队头元素
	Q->front->next = p->next;//修改头结点指针域
	if (Q->rear == p)	Q->rear = Q->front;//最后一个元素被删，队尾指针指向头结点
	free(p);//释放队头元素空间
	return true;
}
//取队头元素
bool GetHead(LinkQueue* Q, int* e) {
	//返回队头元素，不修改队头指针
	if (Q->front == Q->rear)	return false;//判断队列是否为空
	QNode* p = Q->front->next;
	*e = p->data;//用e返回队头元素值
	return true;
}
//输出
void print(LinkQueue* Q) {
	//前提为队不为空
	printf("(front) ");
	if (Q->front != Q->rear) {
		QNode* p = Q->front->next;
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
	}
	printf("(rear)\n");
}
int main() {
	LinkQueue* Q = InitQueue();
	int i, n, e;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
	DeQueue(Q, &e);
	printf("%d\n", e);
	print(Q);
	return 0;
}

循环队列的重点操作

1.队列的创建和初始化

typedef struct {
	int* base;//储存空间的基地址
	int front;//头指针
	int rear;//尾指针
	int maxsize;//队列最大长度
}SqQueue;
 
//初始化
SqQueue* InitQueue(int size) {
	SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针
	Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间
	//队列最大长度置为size，头指针尾指针置为0，队列为空
	Q->maxsize = size;
	Q->front = 0;
	Q->rear = 0;
	return Q;
}

2.入队

//入队
bool EnQueue(SqQueue* Q, int e) {
	//插入e作为新队尾元素
	if ((Q->rear + 1) % Q->maxsize == Q->front)	return false;//尾指针在循环意义上加1后等于头指针说明队满
	Q->base[Q->rear] = e;//将元素e插入队尾
	Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1
	return true;
}

3.出队

//出队
bool DeQueue(SqQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];//用e保存队头元素
	Q->front = (Q->front + 1) % Q->maxsize;//头指针加1
	return true;
}

4.取队头元素

//取队头元素
bool GetHead(SqQueue* Q, int* e) {
	//返回队头元素，不修改头指针
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];
	return true;
}

5.求队列长度

//取队头元素
bool GetHead(SqQueue* Q, int* e) {
	//返回队头元素，不修改头指针
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];
	return true;
}

6.输出队列

//输出
void print(SqQueue* Q) {
	printf("(front) ");
	int i;
	//跟遍历数组差不多，就是要通过模运算防止越界
	for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {
		printf("%d ", Q->base[i]);
	}
	printf("(rear)\n");
}

7.全部操作代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef struct {
	int* base;//储存空间的基地址
	int front;//头指针
	int rear;//尾指针
	int maxsize;//队列最大长度
}SqQueue;
 
//初始化
SqQueue* InitQueue(int size) {
	SqQueue* Q = malloc(sizeof(SqQueue));//先创建队列结构体指针
	Q->base = (int*)malloc(sizeof(int) * size);//为队列分配一个最大容量为size的数组空间
	//队列最大长度置为size，头指针尾指针置为0，队列为空
	Q->maxsize = size;
	Q->front = 0;
	Q->rear = 0;
	return Q;
}
//输出
void print(SqQueue* Q) {
	printf("(front) ");
	int i;
	//跟遍历数组差不多，就是要通过模运算防止越界
	for (i = Q->front; i != Q->rear; i = (i + 1) % Q->maxsize) {
		printf("%d ", Q->base[i]);
	}
	printf("(rear)\n");
}
//入队
bool EnQueue(SqQueue* Q, int e) {
	//插入e作为新队尾元素
	if ((Q->rear + 1) % Q->maxsize == Q->front)	return false;//尾指针在循环意义上加1后等于头指针说明队满
	Q->base[Q->rear] = e;//将元素e插入队尾
	Q->rear = (Q->rear + 1) % Q->maxsize;//尾指针加1
	return true;
}
//出队
bool DeQueue(SqQueue* Q, int* e) {
	//删除队头元素，用e返回其值
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];//用e保存队头元素
	Q->front = (Q->front + 1) % Q->maxsize;//头指针加1
	return true;
}
//取队头元素
bool GetHead(SqQueue* Q, int* e) {
	//返回队头元素，不修改头指针
	if (Q->front == Q->rear)	return false;//队空
	*e = Q->base[Q->front];
	return true;
}
//求队列长度
int QueueLength(SqQueue* Q) {
	//返回队列元素个数
	return (Q->rear - Q->front + Q->maxsize) % Q->maxsize;
}
int main() {
	int i, n, e;
	SqQueue* Q = InitQueue(5);
	scanf("%d",&n);
	for (i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	DeQueue(Q, &e);
	printf("e=%d\n", e);
	scanf("%d",&n);
	for (i = 0; i < n; i++) {
		scanf("%d", &e);
		EnQueue(Q, e);
	}
	print(Q);
}

队列的应用

1.编写一个打印二项式系数表（即杨辉三角）

#include<stdio.h>
#include<stdbool.h>
// 假设队列的结构体定义如下，根据需要进行调整
#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
} SqQueue;
 
// 初始化队列
void InitQueue_Sq(SqQueue *Q, int size) {
    Q->front = Q->rear = 0;
}
 
// 入队
bool EnQueue_Sq(SqQueue *Q, int x) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return false;  // 队列已满
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return true;
}
 
// 出队
bool DeQueue_Sq(SqQueue *Q, int *x) {
    if (Q->front == Q->rear) {
        return false;  // 队列为空
    }
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return true;
}
 
// 获取队头元素
bool GetHead_Sq(SqQueue *Q, int *x) {
    if (Q->front == Q->rear) {
        return false;  // 队列为空
    }
    *x = Q->data[Q->front];
    return true;
}
 
// 判断队列是否为空
bool QueueEmpty(SqQueue *Q) {
    return Q->front == Q->rear;
}
 
void Yanghui(int n) {
    SqQueue Q;
    int i, k, s, e;
    for(i=1;i<=n;i++){
    	printf(" ");
	}
	printf("1\n");
    InitQueue_Sq(&Q, n + 2);
    EnQueue_Sq(&Q, 0);
    EnQueue_Sq(&Q, 1);
    EnQueue_Sq(&Q, 1);
    k = 1;
    while (k < n) {
        for (i = 1; i <= n - k; i++) {
            printf(" ");
        }
        EnQueue_Sq(&Q, 0);
        do {
            DeQueue_Sq(&Q, &s);
            GetHead_Sq(&Q, &e);
            if (e != 0) {
                printf("%d ", e);
            } else {
                printf("\n");
            }
            EnQueue_Sq(&Q, s + e);
        } while (e != 0);
        k++;
    }
}
 
int main() {
    Yanghui(5);  // 打印5行的杨辉三角
    return 0;
}

2.运动会划分子集问题

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
 
typedef struct SqQueue{
    int *base;// 队列元素
    int front;// 队首
    int rear;// 队尾
}SqQueue;
 
//队列的初始化
void InitQueue(SqQueue *Q){
    Q->base = (int*)malloc(MAXSIZE *sizeof(int));
    if(Q->base == NULL){
        printf("内存分配失败");
    }
    Q->front = Q->rear = 0;
}
// 判断队列是否为空
int IsEmpty(SqQueue q){
    if(q.rear == q.front){
        return 1;
    }
    return 0;
}
 
int IsFull(SqQueue q){
    if((q.rear+1)%MAXSIZE ==q.front){
        return 1;
    }
    return 0;
}
//队列元素的增加
int EnQueue(SqQueue *q,int e){
    if((q->rear + 1)%MAXSIZE == q->front){
        return 0;
    }
    q->base[q->rear] = e;
    q->rear = (q->rear + 1)%MAXSIZE;
    return 1;
}
//队列元素的删除
int DeQueue(SqQueue *q,int *x){
    if(q->front == q->rear){
        return 0;
    }
    *x = q->base[q->front];
    q->front = (q->front + 1)%MAXSIZE;
    return 1;
}
 
void PrintQueue(SqQueue q){
    int len = (q.rear-q.front+MAXSIZE)%MAXSIZE;
    int i,j;
    for(i = 0,j = q.front;i<len;i++,j = (j+1)%MAXSIZE){
        printf("%d ",q.base[j]);
    }
}
// 分类的实现
void DivdeQueue(int R[][9]){
    int result[9] = {0};// 结果矩阵，存放分组结果
    int Group = 0;// 组号
 
    // 创建循环队列同时初始化
    SqQueue q;
    InitQueue(&q);
 
    // 将元素排入队列
    int i;
    for(i= 0;i<9;i++){
        EnQueue(&q,i);
    }
 
    int PreItem = q.rear;
    int CurItem;
 
    int newr[9] = {0};
 
    while(!IsEmpty(q)){
        Group += 1;
        for(i = 0;i<9;i++){
            newr[i] = R[q.base[q.front]][i];
        }
        while(q.front!=PreItem){
            DeQueue(&q,&CurItem);
            if(newr[CurItem]==0){
                result[CurItem] = Group;
                for(i = 0;i<9;i++){
                    newr[i] += R[i][CurItem];
                }
            }else{
                EnQueue(&q,CurItem);
            }
        }
        PreItem = q.rear;
    }
    printf("开始输出结果");
    printf("\n");
    int p;
    for(p = 1;p<=Group;p++){
        int q;
        for(q = 0;q<9;q++){
            if(result[q]==p){
                printf("%d ",q+1);
            }
        }
        printf("\n");
    }
}
 
int main(){
    int R[9][9] = {
        0,1,0,0,0,0,0,0,0,
        1,0,0,0,1,1,0,1,1,
        0,0,0,0,0,1,1,0,0,
        0,0,0,0,1,0,0,0,1,
        0,1,0,1,0,1,1,0,1,
        0,1,1,0,1,0,1,0,0,
        0,0,1,0,1,1,0,0,0,
        0,1,0,0,0,0,0,0,0,
        0,1,0,1,1,0,0,0,0
    };
    DivdeQueue(R);
    return 0;
}