数据结构七线性表

  栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。 

        而本次给大家介绍用线性表实现的栈。

如图

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

l 创建栈

l 销毁栈

l 清空栈

l 压栈

l 出栈

l 返回栈顶元素

l 返回栈的大小

l 返回栈的最大长度

代码总分为三个文件：

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

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

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

整体结构图为：

 

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

 

压栈操作：

如图：

  

出栈操作：

如图：

返回栈顶元素：

如图：

    如果（表头用作栈底，表尾用作栈顶）时，每次操作都在表尾部操作，不会移动元素，如果（表头用作栈顶，表尾用作栈底）时，每次操作都会移动表元素，所以第一种方案较合适。

     OK! 上代码：

SeqStack.h ： 

[cpp] view plain copy

1. #ifndef _SEQSTACK_H_  
2. #define _SEQSTACK_H_  
3.   
4. typedef void SeqStack;  
5.   
6. SeqStack* SeqStack_Create(int capacity);  
7.   
8. void SeqStack_Destroy(SeqStack* stack);  
9.   
10. void SeqStack_Clear(SeqStack* stack);  
11.   
12. int SeqStack_Push(SeqStack* stack, void* item);  
13.   
14. void* SeqStack_Pop(SeqStack* stack);  
15.   
16. void* SeqStack_Top(SeqStack* stack);  
17.   
18. int SeqStack_Size(SeqStack* stack);  
19.   
20. int SeqStack_Capacity(SeqStack* stack);  
21.   
22. #endif  

 

SeqStack.c ：

[cpp] view plain copy

1. #include "Seqlist.h"  
2. #include "SeqStack.h"  
3.   
4. SeqStack* SeqStack_Create(int capacity)  
5. {  
6.     return SeqList_Create(capacity);  
7. }  
8.   
9. void SeqStack_Destroy(SeqStack* stack)  
10. {  
11.     SeqList_Destroy(stack);  
12. }  
13.   
14. void SeqStack_Clear(SeqStack* stack)  
15. {  
16.     return SeqList_Clear(stack);  
17. }  
18.   
19. int SeqStack_Push(SeqStack* stack, void* item)  
20. {  
21.     return SeqList_Insert(stack, (SeqListNode*)item, SeqList_Length(stack));  
22. }  
23.   
24. void* SeqStack_Pop(SeqStack* stack)  
25. {  
26.     return SeqList_Delete(stack, SeqList_Length(stack)-1);  
27. }  
28.   
29. void* SeqStack_Top(SeqStack* stack)  
30. {  
31.     return SeqList_Get(stack, SeqList_Length(stack)-1);  
32. }  
33.   
34. int SeqStack_Size(SeqStack* stack)  
35. {  
36.     return SeqList_Length(stack);  
37. }  
38.   
39. int SeqStack_Capacity(SeqStack* stack)  
40. {  
41.     return SeqList_Capacity(stack);  
42. }  

 

Main.c ：

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include "SeqStack.h"  
4.   
5. int main(void)  
6. {  
7.     SeqStack* stack = SeqStack_Create(20);  
8.       
9.     int a[10];  
10.     int i = 0;  
11.       
12.     for(i=0; i<10; i++)  
13.     {  
14.         a[i] = i;  
15.           
16.         SeqStack_Push(stack, a+i);  
17.     }  
18.       
19.     printf("Top:      %d\n", *(int*)SeqStack_Top(stack));  
20.     printf("Capacity: %d\n", SeqStack_Capacity(stack));  
21.     printf("Length:   %d\n", SeqStack_Size(stack));  
22.       
23.     while(SeqStack_Size(stack) > 0)  
24.     {  
25.         printf("%d ", *(int*)SeqStack_Pop(stack));  
26.     }  
27.     printf("\n");  
28.       
29.     SeqStack_Destroy(stack);  
30.       
31.     return 0;  
32. }