文章目录1 .链表是什么？ 2 .队列和堆栈3 .插头法和插尾法4 .实践堆栈和队列(各部分代码) 4.1用定义链表的结构4.2main函数定义链表的一系列指针4.3 for循环实现插尾法链表4.4 for循环实现
1 .链表是什么？
链表是物理存储单元上的非连续、非顺序存储结构，数据元素的逻辑顺序通过链表中指针链接的顺序来实现。 链表由一系列节点组成，链表中的每个元素都称为节点，节点可以在运行时动态生成。 每个节点包含两个部分：数据域，用于存储数据元素；指针域，用于存储下一个节点地址。
绘制简单易懂的概要图如下。 矩形必须是数据，椭圆必须是指针，链表的开头必须是指针。
使用链表结构可以克服数组需要提前知道数据大小的缺点，链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理。 但是，链表失去了随机读取数组的优点，链表增加了节点的指针字段，因此空间开销很大。 链表最明显的优点是，普通数组的放置方式与这些数据项在内存或磁盘上的顺序不同。 对数据的访问往往按不同的数组顺序进行转换。 链表允许插入和删除表中任意位置的节点，但不允许随机访问。
上图显示了链表的原理。 以下是链表的存储方法。 链表在内存中是非连续的、按顺序的。 这意味着链表中的节点并不是一个接一个地存储在内存中。
这里可以看出，如果想要访问有链表的节点，就必须从head开始寻找，没有数组那么方便。
2 .队列和堆栈队列是限制仅在表的一端插入和在另一端删除操作的线性表；
堆栈是只能在表的一端进行插入和删除操作的线性表。
简单来说，队列是数据的先入先出(first in first out，FIFO )； 堆栈是先入后出(first in last out，FILO )
3 .插头法、插尾法、插尾法顾名思义，就是在链表中添加新节点时是插入头部还是尾部。
简单的印象如下。 黑色箭头是插入新节点前的链表的顺序，红线是插入新节点后的链表的顺序。
可见，尾部插入法在不改变链表原有顺序的情况下，遍历链表时正好对应了队列的先入先出特性； 插头法是改变链表本来的顺序，遍历链表时也正好对应堆栈先进后出的特性。
所以我们用插头法的链表实现堆栈； 用末尾插入法的链表实现队列。 理论存在，实践开始！
4 .定义堆栈和队列(实践各部分代码的制作) 4.1链表的结构体typedef struct node_s//定义链表的结构体({intdata； //数据字段struct node_s*next//指针字段}node_t； 4.2main函数定义链表的一系列指针node_t *head=NULL； //初始化头指针为空指针node_t*new_node； //创建新节点的指针node_t*tail； //制作链表末尾指针node_t*front制作链表的开头指针int count； //计数器4.3 for循环实现末尾插入法，制作链表for (count=0； 郡10； count//1通过一个for循环循环创建新节点。 {new_node=malloc(sizeof ) node_t )； //malloc向新节点请求内存，并且指针中存在memset(new_node，0，sizeof ) new_node )； //新节点存储器new_node-next=NULL； //新节点的指针字段为空new_node-data=i 1； //在新节点的数据字段中输入数值/*，至此即可完成新节点的构建。 其次，末尾插入法的逻辑实现*/if(head==null ) ) {head=new_node； //如果头指针为空，则在第一个节点上，直接用头指针(else(tail-next=new_node； //否则尾节点的指针字段指向新节点}tail=new_node； //末尾指针指向新插入的节点(} 4.4 for循环实现了头插入法，在链表for(I=0； i 10； I )//在一个for循环中循环创建新节点。 {new_node=malloc(sizeof ) node_t )； //malloc向新节点请求内存，并且指针中存在memset(new_node，0，sizeof ) new_node )； //新节点存储器new_node-next=NULL； //新节点的指针字段为空new_node-data=i 1； //在新节点的数据字段中输入数值/*至此，新节点的构建完成。 其次，头插入法的逻辑实现*/if(head==null ) ) {head=new_node； //如果头指针为空，则为第一个节点，直接用头指针指向它(else )；front=head； //用前端保留前一个链表地址new_node-next=front新链表的末尾指向前一个链表的开头的head=new_node； //head指新链表的头}} 4.5 for跟踪
环实现遍历链表 for(prt = head; prt != NULL; prt = prt->next)//循环实现遍历{printf("%dn", prt->data); //打印每个节点的数据} 5.实践创建栈和队列（完整代码）整合上面各部分的代码，包含malloc、memset和printf的头文件，再用上条件编译，完整的代码如下：
#include <stdio.h>#include <string.h>#include <stdlib.h>#define INSERT_BEHIND//定义了这行就用尾插擦，注释这行就用头插法typedef struct node_s//定义链表结构{int data;//链表的数据域struct node_s *next;//链表的指针域} node_t;//重定义结构体node_s为node_tint main (int argc, char **argv){node_t*head = NULL;//初始化链表的头指向nowherenode_t*new_node;//新结点的指针node_t*tail;//链表的尾指针node_t*front;//链表的头指针int MagnetoF;// 计数器（author of this passage: MagnetoF）#ifdefINSERT_BEHIND//条件编译：定义了INSTER_BEHIND就使用尾插法实现队列的数据结构for( MagnetoF = 0; MagnetoF < 8; MagnetoF++)//循环创建链表{new_node = malloc(sizeof(node_t) );//创建一块内存，并用new_node指针标记memset(new_node, 0, sizeof(*new_node) );//清空申请的内存new_node->next = NULL;//新链表的尾部指向nowherenew_node->data = MagnetoF+1;//把数据域放入相应的值if(head == NULL){head = new_node;//若头指针为空，则是第一个结点，头指针指向新结点}else{tail->next = new_node;//非首个结点，尾结点的指针域指向新结点}tail = new_node;//尾指针指向新的结点}#else //未定义INSERT_BEHIND时，使用头插法for( MagnetoF = 0; MagnetoF < 8; MagnetoF++)//这里创建新链表的for循环和尾插法一样{new_node = malloc(sizeof(node_t) );memset(new_node, 0, sizeof(*new_node) );new_node->next = NULL;new_node->data = MagnetoF+1;if(head == NULL)//这里开始是头插法的关键{head = new_node;}else{front = head;//用front保留住上一个链表的地址new_node->next = front;//新链表的尾部指向上一个链表的头head = new_node;//head指向新建链表的头}}#endifnode_t*prt;for(prt = head; prt != NULL; prt = prt->next)//循环实现遍历printf("%dn", prt->data);return 0;} 在Ubuntu18.04下用gcc编译分别生成“list_FIFO”（尾插法实现队列）和“list_FILO”（头插法实现栈）。两者运行的结果如下：