数据结构之队列_队列 复杂度

友情提示：

本文参考了程杰的《大话数据结构》这本书，写的属实不错，里面介绍的概念相当的牛逼，通俗易懂，然后代码是听网课写的，然后加上了自己对于代码的思考！！！

本文参考了程杰的《大话数据结构》这本书，写的属实不错，里面介绍的概念相当的牛逼，通俗易懂，然后代码是听网课写的，然后加上了自己对于代码的思考！！！

本文参考了程杰的《大话数据结构》这本书，写的属实不错，里面介绍的概念相当的牛逼，通俗易懂，然后代码是听网课写的，然后加上了自己对于代码的思考！！！

1.1队列的定义

队列（Queue）是一种特殊类型的线性数据结构，它遵循特定的原则进行元素的插入和删除操作。队列的主要特性是先进先出（FIFO, First-In-First-Out），即最早进入队列的元素将最先被移除（或称为出队）。

队列只允许在一端进行插入操作，而在另一端进行删除操作。允许插入的一 端称为队尾，允许删除的一端称为队头。

1.2队列举例

假设在一个咖啡厅里，顾客们想要点咖啡。咖啡厅只有一个咖啡师，所以顾客们需要按照他们到达的先后顺序来等待咖啡师为他们制作咖啡。这个等待的过程就可以看作是一个队列。

• 第一个到达咖啡厅的顾客站在了队伍的最前面（入队操作），等待咖啡师为他制作咖啡。
• 当第二个顾客到达时，他站在了第一个顾客的后面（入队操作）。
• 随着时间的推移，更多的顾客加入队伍，每个人都站在了队伍的最后面。
• 当咖啡师完成第一个顾客的咖啡后，第一个顾客离开队伍去取咖啡（出队操作），此时队伍中的第二个顾客就移动到了队伍的最前面，等待取咖啡。

1.3队列顺序存储的不足

1.4循环队列的定义

1.5总结

队空： front == rear

队满： front == (rear + 1) % MAX

队列长度：（ rear - front + QueueSize ） % QueueSize

front 更新数据的方法： front = (front + 1) % MAX

rear 更新数据的方法： rear = (rear + 1) % MAX

1.6循环队列存储结构

#define MAX 5
typedef int data_t;
typedef struct {
    data_t buf[MAX];
    int front;
    int rear;
}loopqueue_t;

1.7循环队列的操作

1.创建空的循环队列

思路

首先，为循环队列的数据结构分配内存空间。然后，使用malloc函数来获取足够的内存来存储队列的信息（如队首和队尾的位置）。如果内存分配成功，则使用memset函数将这块内存的所有内容初始化为0，这样队列的初始状态（如队首和队尾指针）就被设置为了默认值，且队列中没有任何元素。如果内存分配失败，则返回一个空指针表示创建失败。

//创建空的循环队列
loopqueue_t *create(){
    loopqueue_t *q = NULL;
    q = (loopqueue_t*)malloc(sizeof(loopqueue_t));
    if(NULL == q){
        printf("malloc if fail\n");
        return NULL;
    }
    //相当于q->front = q->rear = 0;及数组元素也全为0
    memset(q,0,sizeof(loopqueue_t));
    return q;
}

2.判空

//判空
int isEmpty(loopqueue_t *q){
    return q->front == q->rear ? 1 : 0;
}

3.判满

//判满
int isFull(loopqueue_t *q){
    return q->front == (q->rear + 1) % MAX ? 1 : 0;
}

4.入队

注意：这里的入队和操作你可以自己在函数里面写一下，我这里是是在main函数中定义的如果满或者如果空这个条件的，如果满就不能入队，如果为空就不能出队，都一样，看你们自己的需求了。

//入队
void enter(loopqueue_t *q,data_t data){
    q->buf[q->rear] = data;
    //更新rear的值，因为其可能会出现越界的情况，所以是下面的代码，而不是简单的++操作
    q->rear = (q->rear + 1) % MAX;
}

//出队
data_t delete(loopqueue_t *q){
    data_t data;//存储取出的数据
    data = q->buf[q->front];
    //更新front的值，同入队
    q->front = (q->front + 1) % MAX;
    return data;
}

//计算队列长度
int length(loopqueue_t *q){
    return (q->rear - q->front + MAX) % MAX;
}

#include"head.h"
 
//创建空的循环队列
loopqueue_t *create(){
	loopqueue_t *q = NULL;
	q = (loopqueue_t*)malloc(sizeof(loopqueue_t));
	if(NULL == q){
		printf("malloc if fail\n");
		return NULL;
	}
	//相当于q->front = q->rear = 0;及数组元素也全为0
	memset(q,0,sizeof(loopqueue_t));
 
	return q;
}
 
//判空
int isEmpty(loopqueue_t *q){
	return q->front == q->rear ? 1 : 0; 
}
 
//判满
int isFull(loopqueue_t *q){
	return q->front == (q->rear + 1) % MAX ? 1 : 0;
}
 
//入队
void enter(loopqueue_t *q,data_t data){
 
 
	q->buf[q->rear] = data;
	//更新rear的值，因为其可能会出现越界的情况，所以是下面的代码，而不是简单的++操作
	q->rear = (q->rear + 1) % MAX;
}
 
//出队
data_t delete(loopqueue_t *q){
 
	data_t data;//存储取出的数据
	data = q->buf[q->front];
	//更新front的值，同入队
	q->front = (q->front + 1) % MAX;
 
	return data;
}
 
//计算队列长度
int length(loopqueue_t *q){
	return (q->rear - q->front + MAX) % MAX;
}

#ifndef __HEAD_H__
#define __HEAD_H__
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define MAX 5
 
typedef int data_t;
 
typedef struct {
	data_t buf[MAX];//定义数组存储数据
	int front;//队头元素下标
	int rear;//队尾元素下一个元素下标
}loopqueue_t;
 
 
extern loopqueue_t *create();
extern int isEmpty(loopqueue_t *q);
extern int isFull(loopqueue_t *q);
extern void enter(loopqueue_t *q,data_t data);
extern data_t delete(loopqueue_t *q);
extern int length(loopqueue_t *q);
 
 
#endif

#include"head.h"
 
int main(){
 
	int i = 0;
	
	loopqueue_t *q = NULL;
	q = create();
 
	//入队
	while(!isFull(q)){
		enter(q,i++);
	}
 
	//计长
	printf("原来的队列长度为:%d\n",length(q));
 
	//出队
	printf("出队的顺序为：");
	while(!isEmpty(q)){
		printf("%d ",delete(q));	
	}
	printf("\n");
 
	//计长
	printf("出队之后的队列长度为:%d\n",length(q));
 
	return 0;
}

1.8链式队列的定义

1.9链式队列存储结构                

//链表节点的设计
typedef struct node{
    data_t data;
    struct node *next;
}linknode_t;

//队列头的设计
typedef struct {
    linknode_t *front;
    linknode_t *rear;
}linkqueue_t;

// 定义一个函数用于创建一个空的链式队列  
linkqueue_t *create(){  
 
    //初始化一个指向队列头的指针q，初始化为NULL  
    //注意：这里的q实际上是队列结构体的指针，它指向整个队列，包括队列头和队列的尾节点  
    linkqueue_t *q = NULL;  
  
 
    //初始化一个指向链表头结点的指针head，初始化为NULL  
    //这个head实际上表示的是队列的头部（也就是链表的第一个节点），但它不存储数据，只是用作链表开始的标识  
    linknode_t *head = NULL;  
  
    //为链表的头结点分配内存空间  
    //链表的头结点不存储数据，只用于标识链表的开始，并指向链表的第一个实际存储数据的节点  
    head = (linknode_t *)malloc(sizeof(linknode_t));  
 
    //初始化头结点的next指针为NULL，表示当前链表为空  
    head->next = NULL;  
  
    //检查内存分配是否成功  
    //如果head为NULL，说明内存分配失败  
    if(head == NULL){  
        printf("为链表头结点分配内存失败.\n");  
        //内存分配失败，返回NULL  
        return NULL;  
    }  
  
    //为队列头分配内存空间  
    //队列头结构体包含了指向队列头和尾的指针，以及可能的其他信息（如队列长度等）  
    q = (linkqueue_t *)malloc(sizeof(linkqueue_t));  
  
    //初始化队列头的前端指针front和后端指针rear都指向链表的头结点head  
    //这是因为队列在创建时是空的，所以front和rear都指向同一个位置（即链表的头结点）  
    q->front = q->rear = head;  
  
    //检查内存分配是否成功  
    //如果q为NULL，说明内存分配失败  
    if(q == NULL){  
        printf("为队列头分配内存失败.\n");  
        //内存分配失败，释放之前为头结点分配的内存，并返回NULL  
        free(head); //释放头结点内存  
        return NULL;  
    }  
  
    //队列创建成功，返回队列头的指针  
    return q;  
}

//判空
int isEmpty(linkqueue_t *q){
        return q->front == q->rear ? 1 : 0;
}

//入队
void enter(linkqueue_t *q,data_t data){
        //先为入的节点分配空间
        linknode_t *temp = (linknode_t*)malloc(sizeof(linknode_t));
        if(NULL == temp){
                printf("malloc is fail");
                return ;
        }
        temp->data = data;
 
        //插入操作，操作rear
        temp->next = q->rear->next;
        //上一行或者写成
        //temp->next = NULL;
 
        //然后将temp传到head的后面
        q->rear->next = temp;
 
        //更新尾结点的地址
        q->rear = temp;
        return ;
}

//出队
data_t delete(linkqueue_t *q){
        //从队头出队
 
        //声明保存要删除的节点和数据
        linknode_t *temp = NULL;
        data_t data;
 
        //1.先保存要出队的数据和节点
        temp = q->front->next;
        data = temp->data;
 
        //2.释放节点
        //将删除节点的后一个节点传给链表头结点
        q->front->next = temp->next;
        //然后释放掉删除的节点
        free(temp);
        temp = NULL;
        //3.若是为NULL，即q->front->next == NULL
        if(q->front->next == NULL){
                //强制是他俩相等，不然不等的话会出现段错误
                q->rear = q->front;
        }
 
        return data;
}
 

5.完整代码

linkqueue.c

#include"head.h"
 
// 定义一个函数用于创建一个空的链式队列
linkqueue_t *create(){
    // 初始化一个指向队列头的指针q，初始化为NULL
    // 注意：这里的q实际上是队列结构体的指针，它指向整个队列，包括队列头和队列的尾节点
    linkqueue_t *q = NULL;
 
    // 初始化一个指向链表头结点的指针head，初始化为NULL
    // 这个head实际上表示的是队列的头部（也就是链表的第一个节点），但它不存储数据，只是用作链表开始的标识
    linknode_t *head = NULL;
 
    // 为链表的头结点分配内存空间
    // 链表的头结点不存储数据，只用于标识链表的开始，并指向链表的第一个实际存储数据的节点
    head = (linknode_t *)malloc(sizeof(linknode_t));
    // 初始化头结点的next指针为NULL，表示当前链表为空
    head->next = NULL;
 
    // 检查内存分配是否成功
    // 如果head为NULL，说明内存分配失败
    if(head == NULL){
        printf("为链表头结点分配内存失败.\n");
        // 内存分配失败，返回NULL
        return NULL;
    }
 
    // 为队列头分配内存空间
    // 队列头结构体包含了指向队列头和尾的指针，以及可能的其他信息（如队列长度等）
    q = (linkqueue_t *)malloc(sizeof(linkqueue_t));
 
    // 初始化队列头的前端指针front和后端指针rear都指向链表的头结点head
    // 这是因为队列在创建时是空的，所以front和rear都指向同一个位置（即链表的头结点）
    q->front = q->rear = head;
 
    // 检查内存分配是否成功
    // 如果q为NULL，说明内存分配失败
    if(q == NULL){
        printf("为队列头分配内存失败.\n");
        // 内存分配失败，释放之前为头结点分配的内存，并返回NULL
        free(head); // 释放头结点内存
        return NULL;
    }
 
    // 队列创建成功，返回队列头的指针
    return q;
}
 
//判空
int isEmpty(linkqueue_t *q){
	return q->front == q->rear ? 1 : 0;
}
 
//入队
void enter(linkqueue_t *q,data_t data){
	//先为入的节点分配空间
	linknode_t *temp = (linknode_t*)malloc(sizeof(linknode_t));
	if(NULL == temp){
		printf("malloc is fail");
		return ;
	}
	temp->data = data;
 
	//插入操作，操作rear
	temp->next = q->rear->next;
	//上一行或者写成
	//temp->next = NULL;
	
	//然后将temp传到head的后面
	q->rear->next = temp;
 
	//更新尾结点的地址
	q->rear = temp;
 
	return ;
}
 
//出队
data_t delete(linkqueue_t *q){
	//从队头出队
	
	//声明保存要删除的节点和数据
	linknode_t *temp = NULL;
	data_t data;
	
	//1.先保存要出队的数据和节点
	temp = q->front->next;
	data = temp->data;
 
	//2.释放节点
	//将删除节点的后一个节点传给链表头结点
	q->front->next = temp->next;
	//然后释放掉删除的节点
	free(temp);
	temp = NULL;
 
	//3.若是为NULL，即q->front->next == NULL
	if(q->front->next == NULL){
		//强制是他俩相等，不然不等的话会出现段错误
		q->rear = q->front;
	}
 
	return data;
}
 

#ifndef __HEAD_H__
#define __HEAD_H__
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
typedef int data_t;
 
//链表节点的设计
typedef struct  node{
	data_t data;
	struct node *next;
}linknode_t;
 
//队列头的设计
typedef struct {
	linknode_t *front;
	linknode_t *rear;
}linkqueue_t;
 
 
extern linkqueue_t *create();
extern int isEmpty(linkqueue_t *q);
extern void enter(linkqueue_t *q,data_t data);
extern data_t delete(linkqueue_t *q);
 
 
#endif

#include"head.h"
 
int main(){
 
	linkqueue_t *q = NULL;
	int i = 0;
	q = create();
 
	for(i = 0;i < 10;i++){
		enter(q,i);
	}
 
	while(!isEmpty(q)){
		printf("%d ",delete(q));
	}
	printf("\n");
 
	return 0;
}