Q: 如何设计一个特殊的栈,支持min()操作,返回栈中的最小元素.

这个问题来源于去年面试遇到的一道题目,面试官给了20分钟时间让设计这样一个栈.当时时间有限,虽然写出来了一个版本,但是那个版本还存在很多的问题,比如不够通用,只能支持int类型数据;同时,效率也不高, 存在大量的数据拷贝.

C++中引入的引用类型，给我们带来了很大的方便。通过向函数传递引用，我们既可以享受像传递指针一样直接修改变量值的优点，又避免了空指针和野指针造成的问题。在日常开发中我们应该尽量使用引用，避免使用指针。但是引用到底是什么，看起来好像引用跟指针有着千丝万缕的联系，同时两者又有很大的差别，那么引用跟指针到底是什么关系呢？教材上通常会说，引用就是变量的别名，但是光看这句话可能还是不太明白引用的本质。其实按照我的理解引用可以看做一种特殊的指针，在这里做一个总结。

0.指针和引用的区别

指针和引用的区别主要有以下几点：

1. 指针可以先定义后绑定到（指向）某个对象，并且可以置为NULL；引用必须在定义的时候绑定到某对象。
2. 指针可以改变指向的对象，引用在不能改变绑定的对象。（有没有觉得1、2两个特点跟const指针很像？）
3. 通过引用可以像被绑定的对象本身一样操作，指针不可以。
4. 对指针进行sizeof操作得到的是指针本身占用的内存大小，32位系统是4字节，64位系统是8个字节； 对引用进行sizeof操作得到的是被绑定到的变量占用的内存大小。
5. 指针可以有二级、三级等多级指针，引用没有。

在论坛上看到一个同学贴的一段代码如下：

1
2
3
4
5
6
7
8
9
10
11

#include<stdio.h>
int main()
{
    int num, cnt, sum = 0;
    cnt = scanf("%d", &num);
    while (cnt != 1) {
        printf("cnt = %d\n", cnt);
        cnt = scanf("%d", &num);
    }
    return 0;
}

设计算法，返回二叉树T的先序序列的最后一个节点，要求非递归，不能使用栈。

先序遍历先遍历根节点，然后遍历左子树，最后遍历右子树。因此如果有右子树的话，最后一个节点肯定在右子树里面，一直往右走就可以，如果没有右子树的话，最后一个节点肯定在左子树，往左走一步就可以，一直迭代下去直到没有子节点为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class TreeNode :
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x
class Solution:
    def getLastNodeOfPreorderTravel(self, root):
        tmp = root
        while(tmp):
            if tmp.right:
                tmp = tmp.right
            elif tmp.left:
                tmp = tmp.left
            else:
                break
        return tmp

那么相应的，我们可以设计出算法返回中序遍历序列的最后一个节点。

中序遍历就是先遍历左子树，然后遍历根节点，最后遍历右子树。因此如果没有右子树，那么根节点就是最后一个节点；如果有右子树，最后一个节点就在右子树中。迭代下去，找到没有子节点的节点返回即可。

1
2
3
4
5
6
7
8

def getLastNodeOfPreorderTravel(self, root):
    tmp = root
    while(tmp):
        if tmp.right:
            tmp = tmp.right
        else:    
            break
    return tmp

最后，你可能会想如何获得后序遍历的最后一个节点呢？后序遍历顺序是先遍历左子树，后遍历右子树，最后遍历根节点，因此最后一个节点必然是根节点。直接返回即可。

有了实现string的基础，在加上一点点模板的知识，就可以自己动手实现一个vector了。下面是我实现的代码，比较简单。有点犯懒了，讲解以后再写吧！

打开这篇文章的读者，我相信对函数调用的概念肯定不会陌生。函数调用在我们平常的开发过程中用的实在是太广泛了，只要稍微学过一点点计算机知识的人都不会认为这是一个很难理解的概念。但是不知道大家有没有想过，函数调用是CPU当中是怎么实现的呢？

这篇文章的目的就是希望能了解一下函数调用在汇编层面上是如何实现的。大家不要看到汇编两个字就害怕了，这篇文章涉及到的汇编指令并不多，加上几个例子，我相信大家可以很流畅的阅读下来。

上一篇文章当中讨论了C语言中static关键字的用法。这一篇来看一下C++中的static。C语言中的用法在C++中一样适用，但是C++中static又新增了一种用法，用来修饰类的成员，称为类的静态成员。

static关键字是C和C++中很重要的一个关键字，初学者往往搞不清楚这个关键字的真正含义。很多人把这个关键字与变量作用域混为一谈，这种认识是严重错误的！static确实跟变量的作用域有一些关系，但是这两者并不是一回事。这篇文章来探讨一下static关键字的含义，首先放结论：

上一篇文章实现了myString类的构造函数、拷贝构造函数和析构函数，并且重载了<<运算符。这篇文章来讨论一下赋值运算、下标操作和+=拼接字符串操作。