顺序队列的基本操作（入队出队遍历）及C/C++代码实现

144551 阅读 0 评论 0 点赞

1. 入队操作

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

队列结点

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

入队操作

其代码可以表示为：

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

出队操作

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

出队操作

其代码可以表示为：

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