2.1 如何实现栈

【出自ALBB面试题】

难度系数：★★★☆☆

被考察系数：★★★★☆

题目描述：

实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。

分析与解答：

栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

方法一：数组实现

在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示。

从上图中可以看出，可以把数组的首元素当作栈底，同时记录栈中元素的个数size，假设数组首地址为arr，压栈的操作其实是把待压栈的元素放到数组arr[size]中，然后执行size++操作；同理，弹栈操作其实是取数组arr[size-1]元素，然后执行size--操作。根据这个原理可以非常容易实现栈，实现代码如下：

方法二：链表实现

在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。

在上图中，在进行压栈操作时，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然后只需要（1）和（2）两步就实现了压栈操作（把新结点加到了链表首部）。同理，在弹栈的时候，只需要进行步骤（3）的操作就可以删除链表的第一个元素，从而实现弹栈操作。实现代码如下：

程序的运行结果为

两种方法的对比：

采用数组实现栈的优点：一个元素值占用一个存储空间；它的缺点：如果初始化申请的存储空间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时的操作，这样会造成性能的下降。

采用链表实现栈的优点：使用灵活方便，只有在需要的时候才会申请空间。它的缺点：除了要存储元素外，还需要额外的存储空间存储指针信息。

算法性能分析：

这两种方法压栈与弹栈的时间复杂度都为O（1）。