为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果20的。后缀表达式：9 3 1-3*+ 10 2/+，规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

阅读全文 >>

栈的现实应用也很多，我们再来重点讲一个比较常见的应用：数学表达式的求值。20世纪50年代，波兰逻辑学家Jan tukasiewicz想到了一种不需要括号的后缀表达法，我们也把它称为逆波兰（Reverse Polish Notation, RPN)表示。这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

阅读全文 >>

数据结构是算法的基石，算法是软件灵魂。数据结构的很多概念真的是很莫名其妙，很多坑爹的定义，笔者开始很搞不明白，为什么学数据结构？为什么用哪个拗口词语？这些概念到底用在什么地方？笔者试图用自己简单的话来阐述这些问题，希望能对这些感觉不是很好理解的同学有帮助。

阅读全文 >>

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。

阅读全文 >>

栈有一个很重要的应用：在程序设计语言中实现了递归。那么什么是递归呢？当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个 “化身”。一连串的“像中像” 这是一种递归现象。

阅读全文 >>

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。所以现在的许多高级语言，比如Java、C#等都有对栈结构的封装，你可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。

阅读全文 >>

判断链栈是否为空很简单，还记得结构体定义时的那个 count 吗？如果那个 count 为0，就说明链栈为空。置空链栈就没有置空顺序栈那么简单了。置空顺序栈只要一步 S->top=-1; 即可，但是对于链栈却不是那么回事了。方法是设置两个工作结点，开始循环。在释放p之前，让q成为p的后继。还是那个比喻，在皇帝死之前，册封皇子。free(p); 皇帝死了，p=q; 皇子就成了新皇帝。

阅读全文 >>

前面讨论了链栈的进栈操作，这里接下来讨论链栈的出栈操作。至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除 的栈顶结点，将栈顶指针下移一位，最后释放p即可。首先设定一个工作结点 p，并且将栈顶结点赋值给它。然后将栈顶指针下移一位，指向下一结点。代码表示为 S->top=S->top->next;

阅读全文 >>

我们在定义完一个数据结构的结构体之后，需要初始化才能使用。比如顺序栈的初始化，也就是构造一个空栈就行了。那么链栈如何初始化呢？链栈初始化的目标也是要构造一个空栈。根据结构体定义，空栈是什么一个状况呢？就是栈的count = 0，并且栈的 top 为 null。所以知道这两点，我们就可以写出链栈的初始化函数了。

阅读全文 >>

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。假设元素值为e的新结点是s, top为桟顶指针……那么我分析下过程，首先开辟一个内存空间给 s，然后 s的data就是e，再将新结点s 的后继赋值为当前结点 S->top。最后将栈顶指针指向结点 s。

阅读全文 >>

前面讲完了栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢，所以比较好的办法是把栈顶放在单链表的头部。

阅读全文 >>

根据前面定义的栈ADT，我们还有几个操作要完成。比如获取顺序栈的栈顶元素 GetTop (S,*e)：若栈存在且非空，用e返回S的栈顶元素。这个操作的函数设计思路如何呢？参考之前线性表的话，就是设一个存储栈顶的变量 e，然后通过地址传递，用 *e 来保存指针为 top 的数组元素。

阅读全文 >>

昨天我们讲了顺序栈的进栈操作，那么今天我们来看一下与进栈相对应的出栈操作吧。进栈是先自增再赋值，出栈则反过来。先把要出栈的元素获取到，然后再指针自减，把空间释放出来。

阅读全文 >>

对于栈来说，最重要的操作之一就是进栈。我们今天来看看如何实现顺序栈的进栈操作。进栈操作push大概分为两步。栈顶指针 S->top 先自增1，给需要进栈的元素腾出内存空间。再赋值。就是给对应的数组元素赋值：S->data[S->top]=e

阅读全文 >>

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们将其简称为顺序栈。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好？下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

阅读全文 >>

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop,英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

阅读全文 >>