栈

栈是一种特殊形式的线性表。它的插入和删除操作只在表的一端进行，也就是表首或者表尾，我们称进行这两个操作的一端为栈顶，另一端为栈底。向栈顶插入数据的操作称为入栈(Push)，删除栈顶数据的操作称为出栈(Pop)。栈的这种入栈出栈机制，就会产生最后添加的数据最先被移除的效果，这就是所谓的后进先出特性，即Last-In, First-Out, LIFO。这就好像我们洗盘子一样，新洗好的盘子摞在最上面，相当于我们的栈顶。使用的时候，也是从最上面开始取用的。很显然，最先使用的盘子就是我们最后洗干净的那个。

本质上栈就是一种线性表，它所保存的数据之间的前驱和后继关系仍然存在。所以我们可以以数组或者链表的形式来实现它。链表本身就具有较高的插入和删除效率，无论是将表首还是表尾当做栈顶都没有什么影响。而数组的插入效率和删除效率要低很多，如果以表首作为栈顶，那么每次插入和删除都需要移动其它数据，所以一般都是以表尾作为栈顶。当然，如果额外使用一个指针来指示栈顶位置，也是可以以表首作为栈顶的。

本文中，我们先使用比较简单的链表形式来介绍栈的实现。再对数组进行一些扩展让它具有栈的特性。

1. 基于链表的栈

1.1 list_head的栈操作

首先，让我们再回到linux内核中的链表list_head。这个链表有一个哨兵节点，一方面可以用来简化边界问题，另一方面它可以用来标记线性表的表首和表尾。一般认为，哨兵节点的后继为表首，其前驱为表尾。我们就现在list_head的基础上实现一个以表首为栈顶的栈。

为了方便说明，我们定义一个嵌有list_head的数据类型double_node，来实现一个存储double类型数据的栈结构。他有两个字段，其中key保存实际的数据，list则是链表结构。我们可以通过宏定义list_entry来根据字段list的地址获取包含该链表节点的double_node的数据对象地址。

        struct double_node {
            double key;
            struct list_head list;
        };

接着，定义一个哨兵节点用于标记栈顶。我们通过函数init_list_head对其进行初始化，让其next和prev指针都指向自身，形成一个双向循环链表。

        struct list_head stack;
        init_list_head(&stack);

然后，创建一个double_node的数组，并依次对其进行初始化，之后通过函数list_add将它们依次插入表首也就是这里的栈顶的位置上。按照下面的for循环，我们依次入栈了5个数分别是 1.1, 1.2, 1.3, 1.4, 1.5。

        struct double_node *nodes = (struct double_node *)malloc(5 * sizeof(struct double_node));
        for (int i = 0; i < 5; i++) {
            nodes[i].key = 1.1 + 0.1 * i;
            init_list_head(&(nodes[i].list));
            list_add(&(nodes[i].list), &stack);
        }

因为栈的操作都是在同一端进行的，下面我们再依次将刚刚入栈的数据弹出。如果将这些代码写进一个C函数中，就可以看到它依次打印出1.5, 1.4, 1.3, 1.2, 1.1。其出栈的顺序与我们入栈的顺序相反。最后入栈的数据最先出栈，这正是栈结构的LIFO特性。

        for (int i = 0; i < 5; i++) {
            struct double_node *pnode = list_entry(stack.next, struct double_node, list);
            printf("%f\n", pnode->key);
            list_del(stack.next);
        }

我们也可以以表尾作为栈顶，此时需要调用函数list_add_tail把需要入栈的节点插入哨兵节点的前面，也就是表尾。如下面的红色语句所示。

        struct double_node *nodes = (struct double_node *)malloc(5 * sizeof(struct double_node));
        for (int i = 0; i < 5; i++) {
            nodes[i].key = 1.1 + 0.1 * i;
            init_list_head(&(nodes[i].list));
            list_add_tail(&(nodes[i].list), &stack);
        }

出栈时也需要注意，从表尾取数据，并把表尾的节点从链表中移除。

        for (int i = 0; i < 5; i++) {
            struct double_node *pnode = list_entry(stack.prev, struct double_node, list);
            printf("%f\n", pnode->key);
            list_del(stack.prev);
        }

1.2 DataList的栈操作

在介绍链表的时候，我们使用C++模板创建了链表节点类DataListNode，并使用DataList对其进行了封装。现在我们对DataList进行一些扩展，为之赋予栈的特性。

先实现其入栈函数push，我们以表首作为栈顶。该函数只有一个参数接收需要入栈的数据，在函数中通过DataList的接口函数insert将新的数据插入哨兵节点之后，也就是栈顶。

        DataListNode * push(T const & v) {
            return insert(&mHead, v);
        }

我们提供了两个版本的出栈函数pop，它们都是把栈顶中的数据保存到一个缓存中，再将栈顶的节点从链表中移除。左边的函数将缓存的数据作为函数的返回值，这种方式适用于比较简单的数据结构。对于一些复杂的数据结构它可能需要大量的拷贝工作，效率会很低。右边的函数，以一个引用作为输入，并在函数中把缓存的数据直接写道这个引用中。它没有显式的返回，而是通过引用来输出出栈的数据，效率上会高一点，但是使用起来不是很直接，适用于那些比较复杂的数据结构。

        T pop() {
            T re = mHead.next->key;
            remove(mHead.next);
            return re;
        }

        void pop(T & re) {
            re = mHead.next->key;
            remove(mHead.next);
        }

2. 基于数组的栈

基于数组的栈需要注意边界的处理，当没有足够的空间来存储新的数据时，需要重新申请内存，或者报错退出。对于动态数组，我们可以动态的申请内存，所以在每次入栈数据时，只需要把当前的大小增大一个单元就可以保存新的数据了。

        int TEMPLATE_FUNCTION(array, push)(TEMPLATE_TYPE(array) *a, T v) {
            int size = TEMPLATE_FUNCTION(array, size)(a);
            TEMPLATE_FUNCTION(array, resize)(a, size + 1);
        
            a->stor_begin[size] = v;
            return 0;
        }

出栈的时候，需要先查询一下数组，如果数组为空就报错退出。否则先调整一下表尾位置然后填充缓存数据。

        int TEMPLATE_FUNCTION(array, pop)(TEMPLATE_TYPE(array) *a, T *v) {
            if (TEMPLATE_FUNCTION(array, empty)(a))
                return 1;
            a->end--;
            *v = a->end[0];
            return 0;
        }

对于静态数组，其存储空间在初始化的时候就已经确定了，所以每次入栈的时候，都需要先检查数组是否已经写满，然后再填充数据调整边界。其出栈形式与动态数组一致，不再列举。

        int TEMPLATE_FUNCTION(s_array, push)(TEMPLATE_TYPE(s_array) *a, T v) {
            if (TEMPLATE_FUNCTION(s_array, full)(a))
                return 1;
        
            a->end[0] = v;
            a->end++;
            return 0;
        }

下面是对C++模板形式的数组的栈操作扩展。左边是入栈操作，每当没有足够的空间保存新数据的时候，就将当前的容量扩展一倍。右边则是出栈操作，与动态数组和静态数组没有什么本质区别。

        int push(T const & e) {
            if (full()) {
                int ncap = this->capacity() * 2;
                if (ncap == 0) ncap = 1;
                int err = adjust_capacity(ncap);
                if (0 != err)
                    return err;
            }
            mEnd[0] = e;
            mEnd++;
            return 0;
        }

        int pop(T & buf) {
            if (empty())
                return 1;
            mEnd--;
            buf = mEnd[0];
            return 0;
        }

3. 完

栈只在线性表的一端进行入栈和出栈操作，它所保存的数据具有后进先出的特性。链表具有较高的插入和删除效率，实现起来比较简单，不需要过多的讨论边界问题。数组的实现方式，如果以表首为栈顶，就需要很多额外的拷贝工作，效率较低。一般都是以表尾作为栈顶，但是需要考虑边界问题。