2

我正在阅读The C Programming Language并学习了如何使用堆栈制作逆波兰计算器。以下是其后的练习之一：

练习 4-4。添加命令以打印堆栈的顶部元素而不弹出，复制它，并交换顶部的两个元素。添加清除堆栈的命令。

他们所说的“重复”是什么意思？这意味着打印出整个堆栈，还是将整个堆栈压入自身（例如，“1 2 3”将变为“1 2 3 1 2 3”），还是什么？

4

2 回答 2

6

不，在堆栈顶部复制单个元素更有意义。我怀疑“打印顶部元素”是一个错字，应该是单数的“打印顶部元素”。

这种情况更有可能发生的原因是因为打印“顶级元素”本身没有任何意义。如果它是堆栈的某个子集而不仅仅是顶部元素，则需要指定一个计数（并且它不需要），或者，如果它意味着它们全部，则根本不需要“顶部”限定符。

这意味着在这种情况下，主题“它”是指“堆栈的顶部元素”，而不是“堆栈”。

因此，如果您的堆栈是：

[1,2,3,4,5]

1作为第一个被推送的元素和最后一个元素5，复制会给你：

[1,2,3,4,5,5].

假设您已经具备基本操作push，pop您可能需要添加count和peek，这将分别为您提供当前元素计数和堆栈的顶部元素（基本上是 apop但不删除它）。

然后可以从这些基本操作（伪代码）构建其余代码，例如：

def printTop(stack):
    print stack.peek()

def duplicateTop(stack):
    stack.push(stack.peek())

def swapTopTwo(stack):
    one = stack.pop()
    two = stack.pop()
    stack.push(one)
    stack.push(two)

def clear(stack):
    while stack.count() > 0:
        junk = stack.pop()

这可能是实现它们的最简单方法，尽管如果您编写函数并假设您拥有比调用基本操作更多的功能，则可能会提高效率。例如，您可以swapTopTwo通过就地交换两个元素而不是弹出和推送（以 开头的变量_是以下实现的内部变量）：

def swapTopTwo(stack):
    if stack._count < 2: raise error
    temp = stack.data[_count - 2]
    stack.data[_count - 2] = stack.data[_count - 1]
    stack.data[_count - 1] = temp
于 2009-02-08T07:38:15.250 回答
2

维基百科中面向堆栈的编程语言条目包含对堆栈操作操作的描述：

堆栈操作

由于堆栈是面向堆栈的编程语言中数据操作的关键手段，因此这些语言通常提供某种堆栈操作运算符。常用的有dup，复制栈顶元素，exch（或swap），交换栈顶元素（第一个变成第二个，第二个变成第一个），roll，循环置换堆栈中的元素或堆栈的一部分，pop（或drop），丢弃堆栈顶部的元素（push是隐式的），以及其他。这些成为学习程序的关键。

于 2009-02-08T07:43:08.987 回答