c语言实现链队列的基本功能-蒲公英云

c语言实现链队列的基本功能

链队列，实际上是一个带有头指针和尾指针的单链表，头指针指向头节点（不存放数据），尾指针指向队尾节点，虽然用头指针可以确定一个单链表，但是插入操作是在队尾进行，如果没有尾指针，会变得复杂

初始化：

void init(pQueue pq){
    pq->front=pq->rear=(pNode)malloc(sizeof(Node));
}

注意：（1）.为头指针和尾指针申请内存

入队:

void enqueue(pQueue pq,int x){
    pNode pNew=(pNode)malloc(sizeof(Node));
    pNew->data=x;
    pNew->next=NULL;
    pq->rear->next=pNew;
    pq->rear=pNew;
}

注意：（1）.入队是在队尾进行，所以需要尾指针

出队:

void dequeue(pQueue pq,int *e){
    pNode pTemp=(pNode)malloc(sizeof(Node));
    pTemp=pq->front->next;
    *e=pTemp->data;
    pq->front->next=pTemp->next;
    free(pTemp);
}

注意：（1）.出队是在队头进行

（2）.记得free（pTemp），因为一开始申请了一块内存

（3）.用e来存储数据，方便在main函数中处理，int *p是定义一个指针p，p是一个地址，所以p=&a（或者一开始就用int *p=&a），然后printf（“%d”，*p）,是输出变量a的值，printf（”%d”,&p），是输出一个地址，因为指针p也是一个变量，也有自己的地址

求队列长度:

int QueueLength(pQueue pq){
    int count=0;
    pNode p=pq->front->next;
    while(p!=NULL){
    count++;
    p=p->next;
    }
    printf("\n");
    return count;
}

注意：（1）.while循环要跳出，p要等于null，这就需要入队把pNew->next=NULL

遍历队列:

void show_queue(pQueue pq){
    pNode p=pq->front->next;
    printf(" 当前元素从头到尾:");
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
}

main函数:

void main(){
    int count;
    int x;
    int e;
    Queue q;
    init(&q);
    printf("_____入队10个元素_____");
    for(int i=0;i<10;i++){
        enqueue(&q,i);
        count=QueueLength(&q);
        printf("%d入队,当前队列元素个数:%d ",i,count);
        show_queue(&q);
    }
    printf("\n_____出队5个元素_____");
    for(int i=0;i<5;i++){
        dequeue(&q,&x);
        count=QueueLength(&q);
        printf("%d出队,当前队列元素个数:%d ",x,count);
        show_queue(&q);
    }
    GetHead(&q,&e);
    printf("\n当前队头为:%d\n",e);
    system("pause");
}

注意：（1）.如果定义的是结构体指针，比如pQueue pq（pq是地址），就应该申请一块内存，也可以用Queue q，然后&q取地址传入函数，这样就不用申请内存了

（2）.入队出队可以用for循环提高效率，同时通过传入&x，把x的值传出到main函数，方便调用

（3）.xx删除，当前还有xx个元素，从头到尾是xx，这样一目了然

完整代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{
int data;
node *next;
}Node,*pNode;
typedef struct{
    pNode front;
    pNode rear;
}Queue,*pQueue;
void init(pQueue pq){
    pq->front=pq->rear=(pNode)malloc(sizeof(Node));
    //pq->rear->next=NULL;
}
int QueueLength(pQueue pq){
    int count=0;
    pNode p=pq->front->next;
    while(p!=NULL){
    count++;
    p=p->next;
    }
    printf("\n");
    return count;
}
void enqueue(pQueue pq,int x){
    pNode pNew=(pNode)malloc(sizeof(Node));
    pNew->data=x;
    pNew->next=NULL;
    pq->rear->next=pNew;
    pq->rear=pNew;
}
void dequeue(pQueue pq,int *e){
    pNode pTemp=(pNode)malloc(sizeof(Node));
    pTemp=pq->front->next;
    *e=pTemp->data;
    pq->front->next=pTemp->next;
    free(pTemp);
}
void show_queue(pQueue pq){
    pNode p=pq->front->next;
    printf(" 当前元素从头到尾:");
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
}
void GetHead(pQueue pq,int *e){
    *e=pq->front->next->data;
}
void main(){
    int count;
    int x;
    int e;
    Queue q;
    init(&q);
    printf("_____入队10个元素_____");
    for(int i=0;i<10;i++){
        enqueue(&q,i);
        count=QueueLength(&q);
        printf("%d入队,当前队列元素个数:%d ",i,count);
        show_queue(&q);
    }
    printf("\n_____出队5个元素_____");
    for(int i=0;i<5;i++){
        dequeue(&q,&x);
        count=QueueLength(&q);
        printf("%d出队,当前队列元素个数:%d ",x,count);
        show_queue(&q);
    }
    GetHead(&q,&e);
    printf("\n当前队头为:%d\n",e);
    system("pause");
}