【出自ALBB面试题】
难度系数:★★★☆☆ 被考察系数:★★★★☆
题目描述:
实现一个栈的数据结构,使其具有以下方法:压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。
分析与解答:
栈的实现有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
方法一:数组实现
在采用数组来实现栈的时候,栈空间是一段连续的空间。实现思路如下图所示:
从上图中可以看出,可以把数组的首元素当作栈底,同时记录栈中元素的个数size,假设数组首地址为arr,从上图可以看出,压栈的操作其实是把待压栈的元素放到数组arr[size]中,然后执行size++操作;同理,弹栈操作其实是取数组arr[size-1]元素,然后执行size--操作。根据这个原理可以非常容易实现栈,示例代码如下:
方法二:链表实现
在创建链表的时候经常采用一种从头结点插入新结点的方法,可以采用这种方法来实现栈,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下图所示:
在上图中,在进行压栈操作的时候,首先需要创建新的结点,把待压栈的元素放到新结点的数据域中,然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理,在弹栈的时候,只需要进行(3)的操作就可以删除链表的第一个元素,从而实现弹栈操作。实现代码如下:(www.xing528.com)
程序的运行结果如下:
栈顶元素为:1
栈大小为:1
弹栈成功
栈已经为空
两种方法的对比
采用数组实现栈的优点是:一个元素值占用一个存储空间;缺点是:如果初始化申请的存储空间太大,会造成空间的浪费;如果申请的存储空间太小,后期会经常需要扩充存储空间,扩充存储空间是个费时的操作,这样会造成性能的下降。
采用链表实现栈的优点是:使用灵活方便,只有在需要的时候才会申请空间。缺点是:除了要存储元素外,还需要额外的存储空间存储指针信息。
算法性能分析:
这两种方法压栈与弹栈的时间复杂度都为O(1)。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。