栈是一种后进先出的限定性线性表，它与递归关系紧密，在实际生产中被广泛使用，本场Chat就栈的定义及其实现做一次分享。
本场Chat内容如下：
- 栈的定义；
- 顺序栈及链栈的结构定义；
- 栈的七种基本操作。
栈是一种限定性线性表，其特殊在于插入与删除均仅在表的一端进行，被称为栈顶（top），与之相反的一端称为栈底（bottom）。栈是由 $n≥0$ 个元素构成的，当 $n=0$ 时，称为空栈。为了描述的便利，人们将栈的插入操作，形象地称为入栈或是进栈；删除操作则是出栈或是退栈。
正是因为栈的插入与删除仅在 top 进行，因此栈也被称作后进先出（LIFO）表。
栈有三个基本特性：同一性、线性、有穷性。在链接方式上，栈被分作顺序栈与链栈。在一点上，可以类比之前讲的顺序表与链表。
当然正是因为栈的后进先出，导致了它有一个极为出名的应用：递归——在定义自身的同时，又对自身做出了调用。递归又分为线性递归与尾递归。对于尾递归的描述，在之前的《每周 Lisp：从四则运算到条件、循环、宏定义》一文中有着完备的描述。那现在着重讲一下栈是如何实现递归操作的，当然也顺带涉及线性递归。
线性递归相较于尾递归而言，线性递归是一种繁复的操作，但用途极大。比如在解决汉塔诺、树的遍历等等问题上，均有线性递归的身影（下文均以递归指代线性递归）。
递归是将一个非常大的问题分解为几个较大问题，再分解为几个小问题，然后解决小问题，回溯解决较大问题，最后解决了最大的问题。
就比如说阶乘问题，我想计算 $ 10！$，那我就用递归的思路不停地把 10 分解成 $ 9！ * 10 $，……，一直到 $ 1 * 2 * 3 * ... * 9 * 10 $，然后回溯再将各个小问题的值整合起来，就是最后 $10！$ 的答案了。
相比较于循环操作，递归确乎是繁复了。
栈是如何实现递归的呢？栈实现递归操作，完全仰赖其后进先出的特性，图解如下。
与顺序表相同，顺序栈同样也使用一维数组作为数据存放的方式，其结构与七种基本操作如下：
Java 示例：class MyStack{ int Maxsize=5; int data[]=new int[Maxsize]; int top; //新建空栈 void Stack_init(MyStack S){ S.top=0;//有些地方习惯于以top=-1为空栈标志，我习惯于用0； } //入栈 void Stack_push(MyStack S,int e){ if(S.top0){ System.out.println("Pop data is :"+S.data[S.top-1]); S.top--; }else{ System.out.println("Error!"); } } } //判满 boolean Stack_Full(MyStack S){ if(S.top==S.Maxsize){ System.out.println("The Stack is Full"); return true; }else{ System.out.println("Unfull"); return false; } } //获取栈顶元素 void Stack_get_Top(MyStack S){ if(S.Stack_empty(S)==true){ System.out.println("Empty Stack"); }else{ System.out.println("The top data is "+S.data[S.top-1]); } } //清空栈内元素 void Stack_clean(MyStack S){ while(S.Stack_empty(S)==false){ S.Stack_pop(S); } System.out.println("重置成功"); }}public class Stack{ public static void main(String []args){ MyStack S=new MyStack(); S.Stack_push(S, 1); S.Stack_push(S, 2); S.Stack_push(S, 3); S.Stack_push(S, 4); S.Stack_push(S, 5); S.Stack_clean(S); }}
链栈是一种较为重要的栈结构类型，其形式和链表接近，我们来看看其结构定义与出入栈操作的实现。
C 示例：//结构定义 typedef struct node{ int data; struct node *next;}*LinkStack;//入栈操作 int Push(LinkStack top,int e){ node *temp; temp=(node *)malloc(sizeof(node)); if(temp==NULL){ return(false); } temp->data=e; temp->next=top->next; top->next=temp; return(true);}//出栈操作 int Pop(LinkStack top){ node *temp; temp=top->next; if(temp==NULL){ return(false); } top->next=temp->next; printf("出栈元素为：%d\n",temp->data); free(temp); return(true);}- 中国大学MOOC《数据结构·华中农业大学》
- 《数据结构C++版·王红梅》
本文首发于GitChat，未经授权不得转载，转载需与GitChat联系。
阅读全文: http://gitbook.cn/gitchat/activity/5b5ad1b7597ecb7add3f5347
您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ，阅读更多 GitChat 专享技术内容哦。
