数据结构栈--单链表实现

这次给大家介绍用单链表实现的栈。

如图

 

这里介绍双向链表的常用操作：

l 创建栈

l 销毁栈

l 清空栈

l 压栈

l 出栈

l 返回栈顶元素

l 返回栈的大小

代码总分为三个文件：

LinkStack.h ： 放置功能函数的声明，以及表的声明 

LinkStack.c ： 放置功能函数的定义

Main.c     ： 主函数，使用功能函数完成各种需求，一般用作测试

整体结构图为：

 

这里详细说下插入压栈，出栈操作和返回栈顶元素操作：

 

压栈操作：

如图：

  

出栈操作：

返回栈顶元素：

如图：

 

        如果（表首用作栈顶，表尾用作栈底）时，每次压栈和出栈操作时就不会遍历表，因为两个操作都是在栈顶（表首）进行。

如果（表首用作栈底，表尾用作栈顶）时，每次压栈和出栈操作时都要遍历表。

所以第一种方案较合适。

 

OK! 上代码：

LinkStack.h ：

 

[cpp] view plain copy

1. #ifndef _LINKSTACK_H_  
2. #define _LINKSTACK_H_  
3.   
4. typedef void LinkStack;  
5.   
6. LinkStack* LinkStack_Create();  
7.   
8. void LinkStack_Destroy(LinkStack* stack);  
9.   
10. void LinkStack_Clear(LinkStack* stack);  
11.   
12. int LinkStack_Push(LinkStack* stack, void* item);  
13.   
14. void* LinkStack_Pop(LinkStack* stack);  
15.   
16. void* LinkStack_Top(LinkStack* stack);  
17.   
18. int LinkStack_Size(LinkStack* stack);  
19.   
20. #endif  

 

LinkStack.c ：

 

[cpp] view plain copy

1. #include <malloc.h>  
2. #include "LinkList.h"  
3. #include "LinkStack.h"  
4.   
5. typedef struct _tag_LinkStackNode  
6. {  
7.     LinkListNode header;  
8.     void* item;  
9. }TLinkStackNode;  
10.   
11. LinkStack* LinkStack_Create()  
12. {  
13.     return LinkList_Create();  
14. }  
15.   
16. void LinkStack_Destroy(LinkStack* stack)  
17. {  
18.     LinkStack_Clear(stack);  
19.       
20.     LinkList_Destroy(stack);  
21. }  
22.   
23. void LinkStack_Clear(LinkStack* stack)  
24. {  
25.     while(LinkStack_Size(stack) > 0)  
26.     {  
27.         LinkStack_Pop(stack);  
28.     }  
29. }  
30.   
31. int LinkStack_Push(LinkStack* stack, void* item)  
32. {  
33.     TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));  
34.       
35.     int ret = (NULL!=node) && (NULL!=item) && (NULL!=stack);  
36.       
37.     if(ret)  
38.     {  
39.         node->item = item;  
40.           
41.         ret = LinkList_Insert(stack, (LinkListNode*)node, 0);  
42.     }  
43.       
44.     if(!ret)  
45.     {  
46.         free(node);  
47.     }  
48.       
49.     return ret;  
50. }  
51.   
52. void* LinkStack_Pop(LinkStack* stack)  
53. {  
54.     TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);  
55.       
56.     void* ret = NULL;  
57.       
58.     if(NULL!=node)  
59.     {  
60.         ret = node->item;  
61.           
62.         free(node);   
63.     }  
64.       
65.     return ret;  
66. }  
67.   
68. void* LinkStack_Top(LinkStack* stack)  
69. {  
70.     TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);  
71.       
72.     void* ret = NULL;  
73.       
74.     if(NULL!=node)  
75.     {  
76.         ret = node->item;  
77.     }  
78.       
79.     return ret;  
80. }  
81.   
82. int LinkStack_Size(LinkStack* stack)  
83. {  
84.     return LinkList_Length(stack);  
85. }  

 

Main.c ：

[cpp] view plain copy

1. #include <stdio.h>  
2. #include "LinkStack.h"  
3.   
4. int main(void)  
5. {  
6.     LinkStack* stack = LinkStack_Create();  
7.       
8.     int a[10];  
9.     int i = 0;  
10.       
11.     for(i=0; i<10; i++)  
12.     {  
13.         a[i] = i;  
14.           
15.         LinkStack_Push(stack, a+i);  
16.     }  
17.       
18.     printf("Top:    %d\n", *(int*)LinkStack_Top(stack));  
19.     printf("Length: %d\n", LinkStack_Size(stack));  
20.       
21.     while(LinkStack_Size(stack) > 0)  
22.     {  
23.         printf("%d \n", *(int*)LinkStack_Pop(stack));  
24.     }  
25.       
26.     LinkStack_Destroy(stack);  
27.   
28.     return 0;  
29. }