栈模型

栈有时又叫做LIFO（先进后出）。

一般模型：存在某个元素位于栈顶，而该元素是唯一的可见元素。

栈可能是计算机科学中数组之后最基本的数据结构

栈的实现

栈的链表实现

1.#include 
     
      2.#include 
      
       3.4.struct Node;5.typedef struct Node *PtrToNode;6.typedef PtrToNode Stack;7.8.struct Node9.{10. int Element;11. PtrToNode Next;12.};13.14.int IsEmpty(Stack S)15.{16. return S->Next == NULL;17.}18.19.//压入栈20.void Push(int X, Stack S)21.{22. PtrToNode TmpCell;23.24. TmpCell = malloc(sizeof(struct Node));25. if(TmpCell==NULL)26. {27. printf("空间不足");28. }29. else30. {31. TmpCell->Element = X;32. TmpCell->Next = S->Next;33. S->Next = TmpCell;34. }35.}36.37.//返回栈顶元素38.int Top(Stack S)39.{40. if (!IsEmpty(S))41. return S->Next->Element;42. if ("栈空");43. return 0;44.}45.//弹出46.void Pop(Stack S)47.{48. PtrToNode Firstcell;49. if (IsEmpty(S))50. {51. printf("栈空");52. }53. else54. {55. Firstcell = S->Next;56. S->Next = S->Next->Next;57. free(Firstcell);58. }59.}60.61.62.void MakeEmpty(Stack S)63.{64. if(S==NULL)65. {66. printf("栈空");67. }68. else69. {70. while(!IsEmpty(S))71. {72. Pop(S);73. }74. }75.}76.//创建一个空栈77.Stack CreateStack(void)78.{79. Stack S;80.81. S = malloc(sizeof(struct Node));82. if (S == NULL)83. printf("空间不足");84. MakeEmpty(S);85. return S;86.}
      
     

优点：没有任何地方设计栈大小（空栈除外）

缺点：对malloc和free调用都是昂贵的。

栈的数组实现

每一个栈有一个TopOfStack,对于空栈它是-1。将X压入栈中，TopOfStack加1，置Stack[TopOfStack]=X,Stack代表具体的数组。

1.#include 
     
      2.#include 
      
       3.4.typedef struct StackRecord *Stack;5.6.#define EmptyTOS (-1)7.#define MinStackSize (5)8.9.struct StackRecord10.{11. int CapaCity;12. int TopOfStack;13. int *Array;14.};15.16.//创建一个空栈的例程17.void MakeEmpty(Stack S)18.{19. S->TopOfStack = EmptyTOS;20.}21.22.//栈的创建23.Stack CreatStack(int MaxElements)24.{25. Stack S;26. if(MaxElements
       
        Array = malloc(sizeof(int) * MaxElements);32. if(S->Array==NULL)33. {34. printf("Error");35. }36. S->CapaCity = MaxElements;37. MakeEmpty(S);38. return S;39.}40.41.42.//释放栈的例程43.void DisposeStack(Stack S)44.{45. if(S!=NULL)46. {47. free(S->Array);48. free(S);49. }50.}51.52.//检测一个栈是否空栈53.int IsEmpty(Stack S)54.{55. return S->TopOfStack == EmptyTOS;56.}57.58.//进栈59.void Push(int X,Stack S)60.{61. if( S==NULL)62. {63. printf("Error");64. }65. else66. {67. S->Array[++S->TopOfStack] = X;68. }69.70.}71.72.//栈顶返回元素73.int Top(Stack S)74.{75. if(!IsEmpty(S))76. {77. return S->Array[S->TopOfStack];78. }79. else80. {81. printf("Error");82. }83. return 0;84.}85.86.//从栈顶弹出元素87. void Pop(Stack S)88.{89. if(!IsEmpty(S))90. {91. printf("Error");92. }93. else94. {95. S->TopOfStack--;96. }97.}98.99. //返回并弹出元素100.int TopAndPop(Stack S)101.{102. if(!IsEmpty(S))103. {104. return S->Array[S->TopOfStack--];105. }106. else107. {108. printf("Error");109. }110. return 0;111.}
       
      
     

缺点：需要提前声明一个数组的大小

栈的应用

平衡符号

编译器检查对应的符号，比如（[]）。

做一个空栈，读入字符直到文件尾。如果字符式是一个开放符号，则将其推入栈中。如果字符是一个封闭符号，则当栈为空时报错。否则，将栈元素弹出。如果弹出符号不是对应的开放符号，则报错。在文件尾，如果栈非空则报错。

后缀表达式

又称逆波兰记法。

中缀到后缀的转换

a + b * c + ( d * e + f ) * g => a b c * + d e * f + g * +

1.char cArray[10];2. char cRArray[10];3. char a;4. Stack S=CreatStack(10);//初始化栈5. scanf_s("%c", &cArray[0]);6. int i = 0, j = 0;7. while(cArray[i]!='e')8. {9. i++;10. scanf_s("%c", &cArray[i]);11. }12. i = 0;13. for(int k=0;k<10;)14. {15. if(cArray[i]=='*'||cArray[i]=='+')//只做+和*的运算16. {17. if(cArray[i]=='+'&&GetStack(S)=='*')//当前元素+低于*优先级，将栈中元素都输出18. {19. for(;S->TopOfStack>-1;)20. {21. cRArray[k++] = GetStack(S);22. BackStack(S);23. }24. }25. else26. {27. InsertStack(S, cArray[i]);//插入栈28. }29. }30. else31. {32. cRArray[k++] = cArray[i];//数字输出33. }34. i++;35. }36.37. for(int l=0;l<10;l++)38. {39. printf("%c", cRArray[l]);40. }41. while(S->TopOfStack>=-1 )//输出栈尾剩余元素42. {43. printf("%c", GetStack(S));44. BackStack(S);45. }

函数调用

当系统调用函数的时候，需要存储重要信息，比如寄存器值，返回地址，他们都以抽象的方式置于一个堆顶部。然后控制转移到一个新函数，该函数自由的用它的一些值代替这些寄存器。这些工作可以一个栈完成。所存储的信息称为活动记录或栈帧。当前环境由栈顶描述。当存在太多同时运行着的函数时，用尽栈空间可能会发生。

尾递归

1.void PrintList(List L)2.{3. if(L!=NULL)4. {5. PrintElement(L->Element);6. PrintList(L->Next);7. }8.}

在数据足够大的情况下，上面的函数就可能会用尽栈空间。

在不用存储每次递归调用值的情况下可以像下面这样避免。

1.void PrintList(List L)2.{3. top:4. if(L!=NULL)5. {6. PrintElement(L->Element);7. L=L->Next;8. goto top;9. }10.}