L家新鲜电面题

刚刚搜了一搜， geeksforgeeks上有这道题。lz好赞， 能想到doubly linked list!

老妖zm 发表于 2015-10-7 07:16
数组的话，pop的时间复杂度和stack要求的O（1）不一样。要不这就太简单了

我觉得数组可以呀 多一个top 变量 记录top 元素的index 每次pop只要将该指针往左移就行了

treeguard 发表于 2016-12-2 12:20
我觉得数组可以呀 多一个top 变量 记录top 元素的index 每次pop只要将该指针往左移就行了

数组的话，比如 C++ 的vector，插入的时候如果需要re-allocation的话，就不是O(1)了，层主的方法确实是O(1)的