链式队列：用C语言实现简单链式队列结构

jackxiang 2012-2-15 17:11

最近在看C指针编程之道，于是否涉及到队列，简单介绍了下，是以指针为原型的，在网上找了一篇文章，发现其写法和书上差不多，做下备案，代码如下,有时间用gdb跟踪学习一下：

/*
 *用链式结构实现的队列称为链队。根据队列的FIFO原则，为了操作上的方便，可以用带头指针font和尾指针rear的单链表来实现队列。链队结构描述：
 *typedef struct node
 *{
 *    valuetype data;
 *    struct node *next;
 *}QNode;   [>链队结点的类型<]
 *typedef struct
 *{
 *    QNode *font, *rear;
 *}LQueue;    [>将头尾指针封装在一起的链队<]
 *
 *设q是一个指向链队的指针，即LQueue *q. 各函数的功能如下：
 *（1）LQueue * Init_LQueue(): 创建并返回一个带头尾结点的空链队
 *（2）int Empty_LQueue(LQueue *q): 判断链队是否为空
 *（3）void In_LQueue(LQueue *q, valuetype x) : 将数据x压入链队q
 *（4）int Out_LQueue(LQueue *q, valuetype *x) : 弹出链队q的第一个元素x, 若成功则返回1否则返回0
 * By Guv 2011.06.10
 */

/*程序代码：*/

#include <stdio.h>
#include <malloc.h>

typedef int valuetype;

typedef struct node
{
    valuetype data;
    struct node *next;
}QNode;   
typedef struct
{
    QNode *font, *rear;
}LQueue;

LQueue * Init_LQueue()
{
    LQueue *q;
    QNode *p;
    q = (LQueue*)malloc(sizeof(LQueue));    /*申请链队指针*/
    p = (QNode*)malloc(sizeof(QNode));  /*申请头尾指针结点*/
    p->next = NULL;
    
    q->font = q->rear = p;
    return q;
}

int Empty_LQueue(LQueue *q)
{
    if(q->font != q->rear)  return 0;
    else    return 1;
}

void In_LQueue(LQueue *q, valuetype x)
{
    QNode *p = (QNode *)malloc(sizeof(QNode));  /*申请新结点*/
    p->data = x;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

int Out_LQueue(LQueue *q, valuetype *x)
{
    if(Empty_LQueue(q)) return 0;   /*空链队*/
    else{
        QNode *p = q->font->next;
        *x = p->data;
        q->font->next = p->next;
        free(p);
        if (q->font->next == NULL)
            q->rear = q->font;

return 1;
    }
}

int main()
{
    LQueue *queue = Init_LQueue();
    int i;
    for (i=0;i<10;++i)
    {
        In_LQueue(queue, i);
    }
    while(!Empty_LQueue(queue))
    {
        int k=0;
        Out_LQueue(queue, &k);
        printf("%d ",k);
    }
    printf("\n");
    return 0;
}

来自:http://hi.baidu.com/linccn/blog/item/4b0156348f82500990ef39b9.html

作者：jackxiang@向东博客专注WEB应用构架之美 --- 构架之美，在于尽态极妍 | 应用之美，在于药到病除
地址：http://jackxiang.com/post/4986/
版权所有。转载时必须以链接形式注明作者和原始出处及本声明！

phpmyadmin(参见允许密码为空) 的设置方