数据结构---队列的实现

在此之前,已经了解过顺序表和链表了,那么现在要了解的栈和队列,从本质上来说是基于上述俩个的,栈讲究“”后进先出”,而队列与之不同,要求“先进先出”,对于栈来说,根据规则,我们了解到,栈的“入栈”即为“尾插”,栈的出栈也要找到“尾数据”,考虑到实用性,我们的“栈“是基于顺序表完成的。这里就不细细展开了,而对于本次要讲的“队列”,根据使用规则,会发现,入队列类似“尾插”,出队列是“首”,因此,为了效率而言,“队列”会和单链表(此单链表具有尾指针,有尾指针弥补“尾插”效率)联系起来
下面我们来完成一个简单但通用的“队列”
1.首先呢,为了方便操作,我们建立一个自己的头文件·,(这个头文件后面会有引用),命名为 queue.h,顾名思义;
#pragma once
#include <stdlib.h>
#include <stdio.h>

typedef int QDataType;

typedef struct QNode//创建一个结构体来放需要用到的Node
{
    struct QNode* _next;//自己的指针
    QDataType _data;
}QNode;

typedef struct Queue
{
    QNode* _front;//首
    QNode* _rear;/尾
    QNode* _size;//此处size的创建便于后面检查队列满与空
}Queue;
void queueInit(Queue* q);//初始化一个队列
QNode* creatNode(QDataType data);//自己想使用的数据
void queuePush(Queue* q, QDataType data);//入队列
void queuePop(Queue* q);//出队列
QDataType queueFront(Queue* q)//获取头;
QDataType queueBack(Queue* q);//获取尾
int queueSize(Queue* q);//多大
int queueEmpty(Queue* q);//判空
void queueDestory(Queue* q);//销毁
2,这里是我们完成所需要的的函数的主要完成区域,我命名为 Queue.c,在这里完成函数,为test引用做准备;
#define _CRT_SECURE_NO_WARNINGS 1
#include "queue.h"

void queueInit(Queue* q)
{
    q->_front = q->_rear = NULL;
    q->_size = 0;

}
QNode* creatNode(QDataType data)
{
    QNode* node = (QNode*)malloc(sizeof(QNode));
    node->_data = data;
    node->_next = NULL;
    return node;
}
void queuePush(Queue* q,QDataType data)
{
    QNode* node = creatNode(data);
    if (q->_front == NULL)
        q->_front = q->_rear = node;
    else
    {
        q->_rear->_next = node;
        q->_rear = node;
        ++q->_size;
    }
}
void queuePop(Queue* q)
{
    /*if (q->_front == NULL)
        return;
    if (q->_front == q->_rear)
    {
        q->_front =  q ->_rear = NULL;
    }
    else{
        QNode* next = q->_front;
        free(q->_front);
        q->_front = next;
    }*/
    if (q->_front)
    {
        QNode* next = q->_front->_next;
        free(q->_front);
        q->_front = next;
        if (q->_front == NULL)
            q->_rear = NULL;
        --q->_size;
    }
}
QDataType queueFront(Queue* q)
{
    /*if (q->_front == NULL)
        return "NULL";*/
    return q->_front->_data;

}
QDataType queueBack(Queue* q)
{
    return q->_rear->_data;
}
int queueSize(Queue* q)
{
    return q->_size;
}
int queueEmpty(Queue* q)
{
    if (q->_front == NULL)
        return 1;
    return 0;
}
void queueDestory(Queue* q)
{
    QNode* cur = q->_front;
    while (cur)
    {
        QNode* next = cur->_next;
        free(cur);
        cur = next;
    }
    q->_front = q->_rear = NULL;
    q->_size = 0;
}

3,这里是我们自己的操作区域哈哈,通过测试函数test来检测你写函数是否可用,这里我只展示部分,其余的操作可以自己按照需求加上去;

#define _CRT_SECURE_NO_WARNINGS 1

#include "queue.h"

void test1()
{
    Queue q;
    queueInit(&q);
    queuePush(&q, 1);//接口处传&q,传的是已经创建好的队列,数字即为data,
    queuePush(&q, 2);
    queuePush(&q, 3);
    queuePush(&q, 4);
    queuePop(&q);
    queuePop(&q);
    queuePop(&q);
    queuePop(&q);

}

int main()
{
    test1();
    return 0;
}