0

此外，您不能使用指针

这个问题是一个面试问题，听起来让我很困惑，因为给出了堆栈 ADT 并询问了队列上的操作......

4

1 回答 1

0

在队列中，排队总是在最右边的填充位置插入数据，在堆栈中，数据也被插入到最后（顶部）。因此，在堆栈上模拟入队操作并不困难。一个 push() 操作就足够了。问题在于出队操作。模拟出队的一种方法是使用堆栈的两个实例，并在出队时请求空堆栈 1 进入堆栈 2，然后从堆栈 2 中弹出，然后使用堆栈 2 恢复堆栈 1。

入队操作的时间复杂度为 O(1)（与队列相同），但出队操作的时间复杂度为 O(n)，其中 n 是堆栈中的项目数，大于队列的 O(1) .

于 2012-07-13T11:54:05.810 回答