0 
Push(A)
Push(B) 
Pop 
Pop 
Push(C) 
Push(A) 
Pop 
Push(X)

这将导致我最终得到这个线性列表：

X

C

但是，这看起来像一个数组吗？是 stack={X,C} 还是 stack={C,X}？

据我了解，这将是 X,C 因为堆栈的顶部是头部，而其他所有东西都是底部（尾部），所以在这种情况下 C 必须是尾部并且 X 是头部，给我们 X,C . 然而，在我接受这一点之前，我只是认为获得某人的第二意见是明智的，谢谢！

编辑：我只记得堆栈是 LIFO（后进先出）结构......这对我来说只是让事情变得更加复杂。如果“最后一个”是第一个被删除的，那么按照这种逻辑，数组看起来像 C,X 不是吗？由于 X 最后被添加到堆栈中..

4

3 回答 3

2

也可以是。这将是堆栈的实现细节。您甚至可以使用链表来实现它，而根本没有数组。

于 2013-05-03T20:38:28.780 回答
1

让我们看看你的堆栈在每一步中的样子，让我们试着想象一下数组的样子。为方便起见，数组的第一个条目将是最左边的条目

Push(A)  --> [A]
Push(B)  --> [B, A]
Pop      --> [A]
Pop      --> []
Push(C)  --> [C]
Push(A)  --> [A, C]
Pop      --> [C]
Push(X)  --> [X, C]

请注意，以这种方式在数组上实现堆栈有点复杂，因为您需要将已经存储在数组中的所有先前项移动一个位置（对于 each 来说，在右边，对于 each 来说push，在左边pop）。

我使用的“拇指规则”是：堆栈中的第一项总是将被弹出的项。在数组中，第一项具有索引0（或 1，取决于您使用的语言）。

如果您跟踪最后一个条目的索引，那么事情可能会更容易：

Push(A)  --> [A]      (lastIndex = 0)
Push(B)  --> [A, B]   (lastIndex = 1)
Pop      --> [A]      (lastIndex = 0)
Pop      --> []       (lastIndex = -1) # Empty stack
Push(C)  --> [C]      (lastIndex = 0)
Push(A)  --> [C, A]   (lastIndex = 1)
Pop      --> [C]      (lastIndex = 0)
Push(X)  --> [C, X]   (lastIndex = 1)

这是一种更简单的方法...权衡是您需要将lastIndex存储的内容保存在某个地方。

于 2013-05-03T20:51:29.260 回答
1

实现它的一种方法是将新条目添加到向量的末尾，并在弹出时从末尾删除它们：

template <typename T>
class MyStack
{
public:
  void push(const T& value) { m_stack.push_back(value); }
  void pop() { m_stack.pop_back(); }

private:
  vector<T> m_stack;
};

假设底层vector看起来像[] [] [] [] [] [] []：

推(A)

[A] [] [] [] [] [] []

推(B)

[A] [B] [] [] [] [] []

流行音乐

[A] [] [] [] [] [] []

流行音乐

[] [] [] [] [] [] []

推(C)

[C] [] [] [] [] [] []

推(A)

[C] [A] [] [] [] [] []

流行音乐

[C] [] [] [] [] [] []

推(X)

[C] [X] [] [] [] [] []

在 a 的末尾添加和删除vector通常非常有效。

于 2013-05-03T20:47:36.940 回答