什么是队列?        

        队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

        链式队列是用单链表的形式来表示队列,但是要符合队列“尾进头出”的规则

链式队列的构建:

链式队列=单链表+队列

如下代码是对一个队列的链式存储的定义:首先定义一个构成单链表基本单元的结点,然后定义由指向结点的头指针、指向结点的尾指针和表示队列长度的变量组成的队列

//链式队列    链式结构+队列
//链式结构体 =单链表的基本单元:结点 
struct Node{
    int data;//数据域 
    struct Node* next;     //指针域 
}; 
//队列结构体=头指针+尾指针+队列大小 
 struct Queue{
    struct Node* front;//指向结点的头指针 
    struct Node* rear;//指向结点的尾指针 
    int queueSize; //队列大小/长度 
}; 

创建结点:

队列是由一个一个结点通过指针链接起来的

//创建结点
struct Node* createNode(int data){
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->next=NULL;
    newNode->data=data;
    return newNode;    
}; 

队列的初始化:

首先使用malloc函数为队列分配一块内存,初始状态队列的头指针和尾指针在一起都为空(不带头结点),然后设置队列的大小为0。这样队列的初始化操作就完成了。

//队列初始化
struct Queue* createQueue(){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配内存空间 
    queue->front=queue->rear=NULL;//头指针和尾指针在一起为空 
    queue->queueSize=0;//队列大小为0 
    return queue;
} 

入队操作:

准备工作:首先创建入队函数push()传入两个参数,一个是需要插入那个队列另一个是需要插入的数据。然后调用createNode()函数创建一个新的结点,保存插入的数据。

准备工作完成后:先判断队列是否是空队列,如果为空队列直接将front和rear指针指向这个新建结点即可,若不为空,则将尾指针的下一个位置指向新建结点,然后再将尾指针修改为这个新建结点。(这个地方我个人感觉比较难懂,我的理解是 先告诉这个新建结点在哪里,然后在移动rear指针到新建结点把他设为队尾)。

最后别忘记queueSize自增,表示队列长度的增加。

 

void push(struct Queue* queue,int data){
    struct Node* newNode=createNode(data);
    if(queue->queueSize==0)
        queue->front=newNode;
        else
        queue->rear->next=newNode;
        queue->rear=newNode;
        queue->queueSize++;
    
} 

 获取对头元素:

首先判断队列queueSize是否为0如果为0说明队列为空,如果不为空直接返回队列头指针的data值。

//获取对头元素
int queryFront(struct Queue* queue) {
    if(queue->queueSize==0){
        printf("队列为空无法获取对头元素");
        printf("\n"); 
        return -1; 
    }
    return queue->front->data;
}

判断队列是否为空:

 代码很简单就不一一解释了。

//判断队列是否为空
int empty(struct Queue* queue){
    if(queue->queueSize==0)
    return 0;
    else
    return 1;
} 

出队操作:

新建头结点指针指向队列front指针所指结点的下一个位置(因为出队操作是在对头进行的),然后释放原来的队头结点,最后设置这个新的头结点为队头。最后队列的大小减1.

 

 

//出队操作
void pop (struct Queue* queue){
    if(queue->queueSize==0){

    printf("队列为空不能出队");
    exit(0);
     }else{
         struct Node* newFrontNode=queue->front->next;
         free(queue->front); 
         queue->front=newFrontNode;
         queue->queueSize--;
     }
}

 最后附上完整代码:

#include <stdio.h>
#include <stdlib.h>
//链式队列    链式结构+队列
//链式结构体 =单链表的基本单元:结点 
struct Node{
    int data;//数据域 
    struct Node* next;     //指针域 
}; 
//队列结构体=头指针+尾指针+队列大小 
 struct Queue{
    struct Node* front;//指向结点的头指针 
    struct Node* rear;//指向结点的尾指针 
    int queueSize; //队列大小/长度 
}; 
//创建结点
struct Node* createNode(int data){
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->next=NULL;
    newNode->data=data;
    return newNode;    
}; 
//队列初始化
struct Queue* createQueue(){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配内存空间 
    queue->front=queue->rear=NULL;//头指针和尾指针在一起为空 
    queue->queueSize=0;//队列大小为0 
    return queue;
} 
//入队
void push(struct Queue* queue,int data){
    struct Node* newNode=createNode(data);
    if(queue->queueSize==0)
        queue->front=newNode;
        else
        queue->rear->next=newNode;
        queue->rear=newNode;
        queue->queueSize++;
    
} 
//获取对头元素
int queryFront(struct Queue* queue) {
    if(queue->queueSize==0){
        printf("队列为空无法获取对头元素");
        printf("\n"); 
        return -1; 
    }
    return queue->front->data;
}
//判断队列是否为空
int empty(struct Queue* queue){
    if(queue->queueSize==0)
    return 0;
    else
    return 1;
} 
//出队操作
void pop (struct Queue* queue){
    if(queue->queueSize==0){

    printf("队列为空不能出队");
    exit(0);
     }else{
         struct Node* newFrontNode=queue->front->next;
         free(queue->front); 
         queue->front=newFrontNode;
         queue->queueSize--;
     }
}
int main(){
    struct Queue* myQueue=createQueue();
    push(myQueue,1);
    push(myQueue,2);
    push(myQueue,3);
    while(empty(myQueue)){
        printf("%d\t",queryFront(myQueue));
        pop(myQueue);
    }
    printf("\n");
    system("pause");
return 0;
}