我们当然可以根据栈的特性，向实现链表一样实现栈。但是，如果能够复用已经经过实践证明的可靠数据结构来实现栈，不是可以更加高效吗？
so，今天我们就复用Linux内核链表，实现栈这样的数据结构。
要实现的功能很简单，如下（项目中如需更多功能，可自行添加）：
/* stack.h */ #ifndef _STACK_H_ #define _STACK_H_ #include "list.h" #define get_stack_top(pos, head, member) list_entry((head)->prev, typeof(*pos), member)
void stack_creat(struct list_head *list); void stack_push(struct list_head *new, struct list_head *head); void stack_pop(struct list_head *entry); int get_satck_size(struct list_head *head); #endif /* _STACK_H_ */
/* stack.c */ #include "stack.h" void list_del_tail(struct list_head *head) { __list_del(head->prev->prev,head); } void stack_creat(struct list_head *list) { INIT_LIST_HEAD(list); } void stack_push(struct list_head *new, struct list_head *head) { list_add_tail(new,head); } void stack_pop(struct list_head *head) { struct list_head *list = head->prev; /* 保存链表的最后节点 */ list_del_tail(head); /* 尾删法 */ INIT_LIST_HEAD(list); /* 重新初始化删除的最后节点，使其指向自身 */ } int get_satck_size(struct list_head *head) { struct list_head *pos; int size = 0; if (head == NULL) { return -1; } list_for_each(pos,head) { size++; } return size; }
我们先来说，栈的创建：
非常简单，和内核链表一样，仅仅是将链表指针指向自身。
栈的push（入栈）操作：
也非常得简单，根据栈的先进后出特性，我们采用尾插法，这样最后插入的节点也就位于最后，也就是栈顶。
栈的pop（出栈）操作：
出栈只能操作栈顶元素，所以我们使用尾删法，将内核链表的尾部节点删除，就实现了出栈操作，但是内核链表没有直接实现尾删法，不过，我们已经在前面的随笔中对内核链表进行了分析，显然可以利用内核已经实现了的__list_del函数，稍微改变一下参数，就可以实现尾删法了。
获取栈的大小：
原理也非常简单，循环遍历链表，计数增加即可。
得到栈顶元素：
为什么这里我没有使用函数，而是使用宏呢？这和内核链表的逻辑是一致的。因为如果要写成函数，我必须知道使用栈的人定义的数据类型，如果我定义成void *，又不能使用内核链表的list_entry获取容器结构地址的宏了，所以，我将获取栈顶元素设计为宏，这样我可以不定义数据类型，靠用户输入。
现在，我们通过非常简单的一点代码复用内核链表实现了栈，下面看看测试用例：
#include <stdio.h> #include <stdlib.h> #include "stack.h" #include "list.h" struct person { int age; struct list_head list; }; int main(int argc,char **argv) { int i; int num =5; struct person *p; struct person head; struct person *pos,*n; stack_creat(&head.list); p = (struct person *)malloc(sizeof(struct person )*num); for (i = 0;i < num;i++) { p->age = i*10; stack_push(&p->list,&head.list); p++; } struct person test; test.age = 100; stack_pop(&head.list); stack_pop(&head.list); stack_push(&test.list,&head.list); printf("==========> "); list_for_each_entry_safe_reverse(pos,n,&head.list,list) { printf("%p age = %d ",pos,pos->age); } printf("栈顶节点：%p age = %d ",get_stack_top(pos,&head.list,list), get_stack_top(pos,&head.list,list)->age); printf("size = %d ",get_satck_size(&head.list)); return 0; }
运行结果：
通过复用内核链表，可以非常快速高效地实现很多其他数据结构，所以内核链表一定要充分掌握。
增加判断栈是否为空的函数：
bool is_empt_stack(struct list_head *head) { return list_empty(head); }
c语言中bool可以包含#include <stdbool.h>，c99可以直接使用_Bool。