前言

第一次学数据结构，代码写的可能不是很好，大神勿喷，指出来就行。

读本文之前建议先学下链表

• C 实现链表 (如果觉得写得不好请评论)

本文会和《C 链表实现队列》很相似，因为本身队列就是栈的链节点反一下而已。

队列

队列(queue)和栈是兄弟，也是很基本的数据结构。
队列，顾名思义，就是一条队伍，从尾巴进，头出，就好像水管一端进一端出。

下表便是一个简单的队列：

队尾元素 n
元素 n-1
元素 n-2
……
元素 2
元素 1
队首元素 0

操作

函数	操作
push()	向队尾添加元素
pop()	移除队首的元素
front()	读取队首的元素(是最早加进去的元素)
back()	读取队尾的元素(也就是刚加进去的元素)
size()	队列元素的数量
empty()	看队列是否为空

pop和push操作图解

实现

#include <stdio.h>
#include <stdlib.h>

// 每个节点
struct Node
{
    int data; // 数据
    struct Node *pNext; // 下一个数据的指针
};

// 队列结构体
struct Queue
{
    struct Node *pNode; // 当前元素的指针
    struct Node *pRoot; // 队列底部的元素指针
    int size; // 数量
};

// Operations

// 读取队列首部的元素
int front(struct Queue q)
{
    return (q.pRoot) -> data;
}

// 读取队列尾部的元素
int back(struct Queue q)
{
    return (q.pNode) -> data;
}

// 向队列尾部加入新的元素
int push(int data,struct Queue *q)
{
    struct Node *n = (struct Node*) malloc(sizeof(struct Node)); // 创建新的内存空间以便存放链表的元素
    n -> data = data; // 塞入数据
    n -> pNext = NULL; // 由于是从队尾元素的，所以队尾是没有元素的，指针为空
    if (q -> pNode != NULL) (q -> pNode) -> pNext = n; // 如果队列不为空，那就把前一个元素链上新的元素
    q -> pNode = n; // 把当前元素改为新的元素
    if (q -> pRoot == NULL) q -> pRoot = q -> pNode; // 如果队列是空的，那么首部元素和尾部元素是相同的
    (q -> size) ++; // 元素数量+1
    return data;
}

// 删除队列首部的元素
void pop(struct Queue *q)
{
    struct Node *root = q -> pRoot; // 获得首部节点
    if (root -> pNext != NULL) q -> pRoot = root -> pNext; // 如果首部元素的后面不为空，就是是说首部元素没有成为尾部元素时，那就把首部元素改为上一个
    free(root); // 释放移除元素的内存空间
    (q -> size) --; // 元素数量-1
}

// 看队列是否为空
int empty(struct Queue q)
{
    return q.size == 0;
}

// 测试
int main()
{
    struct Queue mQueue = {NULL, NULL, 0}; // 初始化一个队列
    printf("pushed + %d! size = %d\n", push(10, &mQueue), mQueue.size); // 给队列尾部压入新的元素10
    printf("pushed + %d! size = %d\n", push(3,&mQueue), mQueue.size); // 给队列尾部压入新的元素3
    printf("pushed + %d! size = %d\n\n", push(8,&mQueue), mQueue.size); // 给队列尾部压入新的元素8
    printf("front = %d back = %d\n", front(mQueue), back(mQueue)); // 输出此时队列首和尾部的元素
    pop(&mQueue); // 移除队列首部的元素
    printf("poped! size = %d\n", mQueue.size); // 输出元素个数
    printf("front = %d back = %d\n", front(mQueue), back(mQueue)); // 输出此时队列首和尾部的元素
    printf("pushed + %d! size = %d\n", push(9,&mQueue), mQueue.size); // 给队列尾部压入新的元素9
    printf("front = %d back = %d\n", front(mQueue), back(mQueue)); // 输出此时队列首和尾部的元素
    pop(&mQueue); // 移除队列首部的元素
    printf("poped! size = %d\n", mQueue.size); // 输出元素个数
    pop(&mQueue); // 移除队列首部的元素
    printf("poped! size = %d\n", mQueue.size); // 输出元素个数
    pop(&mQueue); // 移除队列首部的元素
    printf("poped! size = %d\n", mQueue.size); // 输出元素个数
    printf("isEmpty = %d\n", empty(mQueue));
    return 0;
}