C语言数据结构之队列的实现（链表实现）-蒲公英云

C语言数据结构之队列的实现（链表实现）

tips：前些天学习了链表和栈，今天来看看c语言数据结构之队列的实现以及队列的各种操作。

队列的特点是先进先出，后进后出，因此我们很容易就能够想到用单链表的尾插法，和头部删除法去实现队列的入队和出队的操作。

首先我们来看一下队列的各种操作的实现思路以及具体实现过程
准备工作：

创建队列元素的结构体

//定义结点
typedef struct tag
{
```
int val;//队列(链表)的值
struct  tag *pNext;
```
}Node,*pNode;
创建队列的结构体

//定义队列
typedef struct tagQueue
{
```
pNode phead, ptail;//队头队尾指针,分别指向头结点和尾结点
```
}Queue,*pQueue;

准备队列的打印输出函数

//测试输出队列元素
void print_queue(pQueue p)
{

pNode pcur = p->phead;//定义工具人，保存当前结点信息
while (pcur!=NULL)
{
    printf("%d\n", pcur->val);
    pcur = pcur->pNext;
}
printf("------------------------------------------\n");

}

1、入队（enQueue）

思路：

为链表创建新的结点，并将其初始化；
采用尾部插入法将新结点入队；

具体实现：

//入队
void enQueue(pQueue p,int val)
{
    pNode pnew = (pNode)calloc(1,sizeof(Node));//为新结点申请空间并初始化
    pnew->val = val;//插入的值
    //入队
    if (p->phead == NULL)//判断队列是否为空
    {
        //为空，头尾指针指向第一个结点
        p->phead = pnew;
        p->ptail = pnew;
    }
    else
    {
        //不为空，尾插法
        p->ptail->pNext = pnew;//新结点放在原来尾结点后面
        p->ptail = pnew;//新结点变成尾结点
    }
}

2、出队（deQueue）

思路：

采用头部删除法，删除头结点（即队头元素），完成出队操作；
出队后，释放出队元素所占用的空间；

具体实现：

//出队
void deQueue(pQueue p)
{
    //出队，头部删除法
    pNode pcur;//工具人，指向当前结点
    pcur = p->phead;
    if (p->phead == NULL)
    {
        //队列为空
        printf("队列为空!\n");
    }
    else
    {
        //头部删除法
        p->phead = p->phead->pNext;//头结点后移
        //释放空间
        free(pcur);
    }
}

3、判断队列是否为空（isEmpty）

思路：

当队头指针为空时，队列即为空（当头指针=尾指针不为空时，就剩最后一个元素）；

总之判断方法很多，大家可以尽情发挥。

具体实现：

//判断队列是否为空
int isEmpty(pQueue p)
{
    if (p->phead == NULL)
        return 1;//为空
    else
        return 0;
}

至此队列的基本操作我们已经全部实现了，接下来我们在main()函数中测试一下：

int main()
{
    //定义一个队列,并初始化
    //队列是先进先出，用尾插法和头部删除法实现进队和出队
    Queue que;
    int val;
    char panduan;//判断是否出队(y/n)
    memset(&que,0,sizeof(Queue));//memset主要是用来对空间初始化的
    //循环入队
    while (scanf("%d", &val) != EOF)
    {
        //入队
        enQueue(&que, val);
    }
    //打印队列元素
    printf("队列中的元素为：\n");
    print_queue(&que);
    //判断队列是否为空
    if (isEmpty(&que))
    {
        printf("队列为空！\n");
    }
    else
    {
        printf("队列不为空！\n");
    }
    printf("------------------------------------------\n");
    while (printf("是否出队？y/n："), scanf("%c", &panduan) != NULL)
    {
        if (panduan == 'y')
        {
            //出队
            deQueue(&que);
            //打印元素
            print_queue(&que);
            //判断队列是否为空
            if (isEmpty(&que))
            {
                printf("队列为空！\n");
            }
            else
            {
                printf("队列不为空！\n");
            }
            printf("---------------------------------\n");
        }
        else if (panduan == 'n')
        {
            break;
        }
    }
    return 0;
}