最新消息:热烈庆祝IT小记上线!

数据结构(19)栈的线性实现

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

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

如图

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

l 创建栈

l 销毁栈

l 清空栈

l 压栈

l 出栈

l 返回栈顶元素

l 返回栈的大小

l 返回栈的最大长度

代码总分为三个文件:

SeqStack.h : 放置功能函数的声明,以及表的声明 

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

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

整体结构图为:

 

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

 

压栈操作:

如图:

  

出栈操作:

如图:

返回栈顶元素:

如图:

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

 

     OK! 上代码:

SeqStack.h : 

  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 :

  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 :

  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. }  


 

   

猜您喜欢

备案号:苏ICP备12016861号-4