顺序队列入队、出队、遍历打印基本操作及C/C++代码实现

2022年7月17日12:21:40数据结构与算法评论238 views字数 3231阅读模式

1.   入队操作

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

 

顺序队列入队、出队、遍历打印基本操作及C/C++代码实现

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

顺序队列入队、出队、遍历打印基本操作及C/C++代码实现

其代码可以表示为:

//入队操作
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)并释放这一个结点即可。

顺序队列入队、出队、遍历打印基本操作及C/C++代码实现

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

顺序队列入队、出队、遍历打印基本操作及C/C++代码实现

其代码可以表示为:

//出队操作
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;
}

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25100.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定