数据结构(五)队列

一、概念

队列是一种先入先出的结构(FIFO — first in first out)

二、逻辑结构:线性结构

三、存储结构

(一)顺序队列

顺序队列是基于 一个数组配合着两个下标(队列头front、队列尾rear)来实现的
顺序队列的本质就是对顺序表操作的一个约束:只能在一端插入 另一端删除
图片1

这种队列我们一般不直接使用,因为 入队列时rear++ 出队列时front++
相当于每块空间只使用了一次,即使数据出队列了,空间也不会被复用了,相当于一次性的队列

(二)循环队列

循环队列相当于顺序队列的一个小优化,目的是让空间复用起来
循环队列相当于是对顺序队列的一个小的优化,目的是让空间能复用起来。
图片

这种队列就能让空间复用起来了。
每次数据入队列后,不要直接执行 rear++ 而是改成 rear = (rear+1)%N
每次数据出队列后,不要直接执行 front++ 而是改成 front = (front+1)%N

判断队列为空 front == rear ,如下图,即认为队列空
在这里插入图片描述

判断队列为满 (rear+1)%N == front (浪费了一个存储空间 方便区分队列满 和 队列空),如下图,即认为队列已满
在这里插入图片描述

1. 结构体定义

typedef struct _Queue{
    int s[N];
    int front;
    int rear;
}queue_t;

2. 创建队列

(1)函数定义

int create_queue(queue_t **my_queue);

(2)注意点
(3)代码实现
int create_queue(queue_t **my_queue){
    if(NULL==my_queue) return -1;
    *my_queue=(queue_t *)malloc(sizeof(queue_t));
    if(NULL==*my_queue) return -1;
    //初始化
    (*my_queue)->front=0;
    (*my_queue)->rear=0;
    return 0;
}

3. 入队列

(1)函数定义

int is_full(queue_t *my_queue);
int push_queue(queue_t *my_queue,int num);

(2)注意点
(3)代码实现
//满为1,空为0
int is_full(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    return (my_queue->rear+1)%N==my_queue->front?1:0;
}

//入队列
int push_queue(queue_t *my_queue,int num){
    if(NULL==my_queue) return -1;
    if(is_full(my_queue)){
        printf("队列满n");
        return -1;
    }
    my_queue->s[my_queue->rear]=num;
    my_queue->rear=(my_queue->rear+1)%N;
    return 0;
}

4. 出队列

(1)函数定义

int is_empty(queue_t *my_queue);
int pop_queue(queue_t *my_queue,int num);

(2)注意点
(3)代码实现
//空为1,不空为0
int is_empty(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    return my_queue->rear==my_queue->front?1:0;
}

int pop_queue(queue_t *my_queue,int *num){
    if(NULL==my_queue || NULL==num) return -1;
    if(is_empty(my_queue)){
        printf("队列空n");
        return -1;
    }
    *num=my_queue->s[my_queue->front];
    my_queue->front=(my_queue->front+1)%N;
}

5. 清空和销毁

(1)函数定义

int clean_queue(queue_t *my_queue)
int destroy_queue(queue_t **my_queue);

(2)注意点
(3)代码实现
int clean_queue(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    my_queue->rear=my_queue->front;
    return 0;
}

int destroy_queue(queue_t **my_queue){
    if(NULL==my_queue || NULL==*my_queue) return -1;
    free(*my_queue);
    *my_queue=NULL;
    return 0;
}

6. 打印

(1)函数定义

int print_queue(queue_t *my_queue);

(2)注意点
(3)代码实现
int print_queue(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    /**也可以写成这种形式
    *for(int i=my_queue->front;i!=my_queue->rear;i=(i+1)%N){
    *	printf("%d ",my_queue->s[i]);
    *}
    **/
    int temp=my_queue->front;
    while(temp!=my_queue->rear){
        printf("%d ",my_queue->s[temp]);
        temp=(temp+1)%N;
    }
    putchar(10);
    return 0;
}

(三)链式队列

逻辑结构:线性结构
存储结构:链式存储,在内存中不连续

1. 结构体定义

//数据元素的结构体
typedef struct _Node{
    int data;
    struct _Node *next;
}node_t;

//队列的结构体
typedef struct _Queue{
    node_t *front;
    node_t *rear;
}queue_t;

2. 创建队列

(1)函数定义

int create_queue(queue_t **my_queue);

申请一块数据对象的内存空间
初始化

(2)注意点
  1. 初始化时,front和rear指针均为NULL
(3)代码实现
int create_queue(queue_t **my_queue){
    if(NULL==my_queue) return -1;
    *my_queue=(queue_t *)malloc(sizeof(queue_t));
    if(NULL==*my_queue) return -1;
    //初始化
    (*my_queue)->front=NULL;
    (*my_queue)->rear=NULL;

    return 0;
}

3. 入队列

(1)函数定义

int push_queue(queue_t *my_queue,int num);

申请一块数据元素的内存空间
采用尾插

(2)注意点
  1. 插入第一个节点时,需要将front和rear都指向第一个节点
  2. 其他节点采用尾插的方法,front无需改变
(3)代码实现
//尾插,无需判断是否满
int push_queue(queue_t *my_queue,int num){
    if(NULL==my_queue) return -1;
    node_t *p=(node_t *)malloc(sizeof(node_t));
    if(NULL==p) return -1;
    p->next=NULL;
    p->data=num;
    //插入第一个节点
    if(NULL==my_queue->front){
        my_queue->front=p;
        my_queue->rear=p;
        return 0;
    }
    //插入其他节点,头节点不变
    my_queue->rear->next=p;
    my_queue->rear=p;
    return 0;
}

4. 出队列

(1)函数定义

int is_empty(queue_t *my_queue);
int pop_queue(queue_t *my_queue,int num);

(2)注意点
  1. 头删,需要判断队列是否为空,当my_queue->front为NULL时说明队列空
  2. 只有一个元素时,删除它时front和rear指针均需要置NULL
(3)代码实现
int is_empty(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    return my_queue->front==NULL?1:0;
}
int pop_queue(queue_t *my_queue,int *num){
    if(NULL==my_queue||NULL==num) return -1;
    if(is_empty(my_queue)){
        printf("栈空n");
        return -1;
    }
    //只有一个元素
    if(my_queue->front==my_queue->rear){
        *num=my_queue->front->data;
        free(my_queue->front);
        my_queue->front=NULL;
        my_queue->rear=NULL;
        return 0;
    }
    //有多个元素
    node_t *ptemp=my_queue->front;
    *num=my_queue->front->data;
    my_queue->front=my_queue->front->next;
    free(ptemp);
    ptemp=NULL;
    return 0;
}

5. 清空和销毁

(1)函数定义

int clean_queue(queue_t *my_queue)
int destroy_queue(queue_t **my_queue);

(2)注意点
  1. 清空是释放所有元素的节点空间
  2. 销毁是先清空,然后释放数据对象的空间
(3)代码实现
int clean_queue(queue_t *my_queue){
    if(NULL==my_queue) return -1;
    node_t *ptemp=NULL;
    while(my_queue->front!=NULL){
        ptemp=my_queue->front;
        my_queue->front=my_queue->front->next;
        free(ptemp);
    }
    ptemp=NULL;
    my_queue->rear=NULL;
    return 0;
}

int destroy_queue(queue_t **my_queue){
    if(NULL==my_queue||NULL==*my_queue) return -1;
    clean_queue(*my_queue);
    free(*my_queue);
    *my_queue=NULL;
    return 0;
}

6. 打印

(1)函数定义

int print_queue(queue_t *my_queue);

(2)注意点
  1. 链式队列与顺序队列不同的一点是,链式队列的rear指向的是最后一个已存入数据的节点,顺序队列rear指向的是最后一个已存入数据的空间的下一个空间。
  2. 先打印除了最后一个节点以外所有节点,此时还有最后一个节点没打印
(3)代码实现
int print_queue(queue_t *my_queue){
    if(NULL==my_queue||NULL==my_queue->front) return -1;
    node_t *ptemp=my_queue->front;
    //打印除了最后一个节点之外所有节点
    while(ptemp!=NULL){
        printf("%d ",ptemp->data);
        ptemp=ptemp->next;
    }
    putchar(10);
    return 0;
}

四、所有源代码已上传至我的资源

下载链接:
C语言实现循环队列
C语言实现链式队列

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>