首页  /  数据结构教程  /  顺序队列二  /  

顺序队列二

点击打开在线编译器,边学边练

1.   入队操作

如图,进行入队(push)操作的时候,我们首先需要特判一下队列是否为空,如果队列为空的话,需要将头指针和尾指针一同指向第一个结点,即front=n;rear=n。


402.png

当如果队列不为空的时候,我们只需要将尾结点向后移动,通过不断移动next指针指向新的结点构成队列即可。

4022.png

其代码可以表示为:

//入队操作
void push(queue *q,int data){
    node *n =init_node();
    n->data=data;
    n->next=NULL;   //采用尾插入法
    //if(q->rear==NULL){     //使用此方法也可以
    if(empty(q)){
        q->front=n;
        q->rear=n;
    }else{
        q->rear->next=n;    //n成为当前尾结点的下一结点
        q->rear=n;  //让尾指针指向n
    }
}


2.   出队操作

出队(pop)操作,是指在队列不为空的情况下(请注意一定要进行队列判空的操作),进行一个判断,如图,如果队列只有一个元素了(即头尾指针均指向了同一个结点),直接将头尾两指针制空(NULL)并释放这一个结点即可。

4023.png

如图,当队列含有二以上个元素时,我们需要将队列的头指针指向头指针当前指向的下一个元素并释放掉当前元素即可。

4024.png

其代码可以表示为:

//出队操作
void pop(queue *q){
    node *n=q->front;
    if(empty(q)){
        return ;    //此时队列为空,直接返回函数结束
    }
    if(q->front==q->rear){
        q->front=NULL;  //只有一个元素时直接将两端指向制空即可
        q->rear=NULL;
        free(n);        //记得归还内存空间
    }else{
        q->front=q->front->next;
        free(n);
    }
}

3.   打印队列元素(遍历)

打印队列的全部元素是在队列不为空的情况下,通过结点的next指向依次遍历并输出元素既可以。

其代码可以表示为

//打印队列元素
void print_queue(queue *q){
    node *n = init_node();
    n=q->front;
    if(empty(q)){
        return ;    //此时队列为空,直接返回函数结束
    }
    while (n!=NULL){
        printf("%d\t",n->data);
        n=n->next;
    }
    printf("\n");   //记得换行
}

遍历操作还有很多变形,比如说进行计算队列中含有多少元素。

int calac(queue *q){
    node *n = init_node();
    n=q->front;
    int cnt=0;    //计数器设计
    if(empty(q)){
        return 0;    //此时队列为空,直接返回函数结束
    }
    while (n!=NULL)
    {
        n=n->next;
        cnt++;
    }
    return cnt;
}

4.   本文代码

#include<stdio.h>
#include<stdlib.h>
//结点定义
typedef struct node{
    int data;
    struct node *next;
}node;
//队列定义,队首指针和队尾指针
typedef struct queue{
    node *front;
    node *rear;
}queue;

//初始化结点
node *init_node(){
    node *n=(node*)malloc(sizeof(node));
    if(n==NULL){    //建立失败,退出
        exit(0);
    }
    return n;
}

//初始化队列
queue *init_queue(){
    queue *q=(queue*)malloc(sizeof(queue));
    if(q==NULL){    //建立失败,退出
        exit(0);
    }
    //头尾结点均赋值NULL
    q->front=NULL;  
    q->rear=NULL;
    return q;
}

//队列判空
int empty(queue *q){
    if(q->front==NULL){
        return 1;   //1--表示真,说明队列非空
    }else{
        return 0;   //0--表示假,说明队列为空
    }
}

//入队操作
void push(queue *q,int data){
    node *n =init_node();
    n->data=data;
    n->next=NULL;   //采用尾插入法
    //if(q->rear==NULL){  
    if(empty(q)){
        q->front=n;
        q->rear=n;
    }else{
        q->rear->next=n;    //n成为当前尾结点的下一结点
        q->rear=n;  //让尾指针指向n
    }
}

//出队操作
void pop(queue *q){
    node *n=q->front;
    if(empty(q)){
        return ;    //此时队列为空,直接返回函数结束
    }
    if(q->front==q->rear){
        q->front=NULL;  //只有一个元素时直接将两端指向制空即可
        q->rear=NULL;
        free(n);        //记得归还内存空间
    }else{
        q->front=q->front->next;
        free(n);
    }
}

//打印队列元素
void print_queue(queue *q){
    node *n = init_node();
    n=q->front;
    if(empty(q)){
        return ;    //此时队列为空,直接返回函数结束
    }
    while (n!=NULL)
    {
        printf("%d\t",n->data);
        n=n->next;
    }
    printf("\n");   //记得换行
}

//主函数调用,这里只是简单介绍用法
int main(){
    queue *q=init_queue();
    ///////////////入队操作/////////////////
    printf("入队\n");
    for(int i=1;i<=5;i++){
        push(q,i);
        print_queue(q);
    }
    ///////////////出队操作/////////////////
    printf("出队\n");
    for(int i=1;i<=5;i++){
        pop(q);
        print_queue(q);
    }
    return 0;
}


5.   题目推荐

对于基本的操作,可以同链表的题目测试,自定义一些数据集来测试,这里不再提供直接的问题链接,其次可以试着去做一些基本的队列操作的题目,如:

1895题

接着,队列的操作会在很多的算法设计中使用到,尤其是BFS(广度优先搜索)算法的设计和一些图论的算法设计几乎无法离开各种类型的队列的灵活使用。

对于本样例代码,同学们可以试将队列元素数量设计入结构体中,这样每次询问队列中含有多少元素时就不必在进行依次遍历出元素数量而直接出答案了。


上一课:顺序队列一 下一课:循环队列一
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记