论坛 › C\C++交流 › 链表实现队列

wuxianbiao 发表于 2021-7-27 23:40:40

链表实现队列

#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
QNode * initQueue(){
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    queue->next=NULL;
    return queue;
}
QNode* enQueue(QNode * rear,int data){
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //使用尾插法向链队列中添加数据元素
    rear->next=enElem;
    rear=enElem;
    return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
    QNode * p = NULL;
    if (top->next==NULL) {
      printf("\n队列为空");
      return rear;
    }
    p=top->next;
    printf("%d ",p->data);
    top->next=p->next;
    if (rear==p) {
      rear=top;
    }
    free(p);
    return rear;
}
int main() {
    QNode * queue,*top,*rear;
    queue=top=rear=initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    return 0;
}




//整个程序实现的是通过链表实现队列的先进先出。我理解的是，程序中top->next一直为NULL，因为这个程序一直在维护rear指针。

wuxianbiao 发表于 2021-7-27 23:41:10

http://data.biancheng.net/view/174.html
这是程序的链接，麻烦大家看看。

wuxianbiao 发表于 2021-7-27 23:41:51

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_NUMBER 10
typedef struct NODE
{
        int data;
        struct NODE *next;
}node;
typedef struct QUEUE
{
        node *head;//头指针
        node *rear;//尾指针
        int number;//队列元素的个数
}queue;
//初始化队列
queue *initQueue(queue *Q)
{
        Q = (queue *)malloc(sizeof(queue));
        Q->head = (node *)malloc(sizeof(node));
        Q->rear = (node *)malloc(sizeof(node));
        Q->head->next = NULL;
        Q->rear->next = NULL;
        Q->number = 0;
        return Q;
}
queue *inQueue(queue *Q,int data)
{
        node *n = (node *)malloc(sizeof(node));
        n->data = data;
        n->next = NULL;
        if (Q->number == 0)
        {
                Q->head->next = n;
        }
        Q->rear->next = n;
        Q->rear = n;
        Q->number++;
        printf("进栈元素:%d\n", data);
        return Q;
}
queue *outQueue(queue *Q)
{
        node *temp = Q->head->next;
        printf("出队列元素:%d\n", Q->head->next->data);
        Q->head->next = Q->head->next->next;
        free(temp);
        Q->number--;
        return Q;
}
void main(void)
{
        queue *Q = NULL;
        Q = initQueue(Q);
        for (int i = 0; i < MAX_QUEUE_NUMBER; i++)
        {
                Q = inQueue(Q, i);
        }
        while (Q->number)
        {
                Q = outQueue(Q);
        }
        printf("队列为空");
}



这是我自己实现的，当进来一个元素时，头指针指向这个元素。

查看完整版本: 链表实现队列