练习1.3.45 ( Robert Sedgewick的算法第4版)问题

Question

1.3.45堆栈的通用性。假设我们有一系列混合的推送和弹出操作，就像我们的测试堆栈客户端一样，其中整数0，1，...，N-1的顺序(推送指令)与N个减号(pop指令)混合在一起。设计一种算法，确定混合序列是否会导致堆栈下溢。(您只能使用与N无关的空间量-您不能在数据结构中存储整数。)设计一个线性时间算法，确定给定的排列是否可以生成为我们的测试客户端的输出(取决于pop指令发生的位置)。

解决方案:堆栈不会溢出，除非存在一个整数k，使得前k个弹出操作发生在前k个推送操作之前。如果可以生成给定的排列，则按如下方式唯一地生成该排列:如果输出排列中的下一个整数位于堆栈的顶部，则将其取出；否则，将其推入堆栈。

我对理解这一部分只有一个问题:设计一个线性时间算法来确定给定的排列是否可以作为我们的测试客户端的输出生成(取决于pop指令发生的位置)。

我在google上看到了关于如何解决这个练习的解决方案，但我找不到如何解决它的解释。有谁能解释一下吗？谢谢

Answer 1

第一步非常简单。为了确定步骤序列是否导致溢出或下溢，我们使用以下算法，其中k是堆栈的大小限制，指令列表是推入或弹出的列表：

在Python中：

def undeflows(lst):
    count = 0
    for x in lst:
        if x == PUSH:
            count += 1
        else:
            # We know that x == POP
            if count == 0:
                return True
            count -= 1
    return False

对于第二部分，关键是我们可以推断出产生给定输出的操作序列。考虑以下算法：

在Python中：

def test_permutation(perm):
    stack = []
    next_to_read = 0
    for val in perm:
        if val >= next_to_read:
            # in this case, we haven't pushed val yet. We'll need to push
            # next_to_read to val inclusive, then pop val.
            stack.extend(range(next_to_read, val))
            next_to_read = val + 1
        # Otherwise, we must have already pushed val. We must check to make sure
        # we can pop it.
        elif stack and stack[-1] == val:
            stack.pop()
        else:
            return False
    # at this point, stack should be empty.
    return not stack

如果我们保证输入实际上是0，1，...，n-1的排列，那么我们可以将代码修改为

def test_permutation(perm):
    stack = []
    next_to_read = 0
    for val in perm:
        if val >= next_to_read:
            # in this case, we haven't pushed val yet. We'll need to push
            # next_to_read to val inclusive, then pop val.
            stack.extend(range(next_to_read, val))
            next_to_read = val + 1
        # Otherwise, we must have already pushed val. We must check to make sure
        # we can pop it.
        elif stack[-1] == val:
            stack.pop()
        else:
            return False
    # at this point, stack should be empty.
    return True