如何仅使用 python 中的堆栈操作对堆栈进行排序？

Question

我有三叠。第一个里面有元素。其他的只是为了帮助。如何仅使用 push、pop、peek 和 empty 运算符对堆栈进行排序？这就是我所做的。

def sort(stack1, stack2, stack3):
    while not stack1.empty():
        temp = stack1.pop()
        while not stack2.empty() and stack2.peek() > temp:
            stack1.push(stack2.pop())
            stack2.push(temp)
    return stack1

Answer 1

您似乎没有使用 stack3，它本来是 stack2 中大于 temp 的项目的临时容器。另外，不要修改stack1，除了它只是包含源未排序的项目之外，你正在推入它然后弹出，这将是一个无限循环。

以下是堆栈的作用，供您参考：

stack1 - 包含原始数据。就是这样，仅此而已。你应该弹出它的项目直到空。但是当然，在获取每个项目时，请确保您的其他堆栈保持一组排序的项目。
stack2 - 包含排序后的数据。这是你应该return。此处的物品必须按顺序排列。
stack3 - stack2 中已排序项目的临时持有者。假设 stack2 有项目 1->4->5。对于我们在保持顺序的同时插入 3，我们不能只是将它推到顶部，因为那样会使它成为 1->4->5->3。相反，我们将继续弹出已经排序的数据并将其暂时放入 stack3，直到我们已经可以插入 3 为止。因此，stack2 将是 1 而 stack3 将是 5->4（这也是按顺序排列的，特别是降序）。一旦我们推送 3 使 stack2 成为 1->3，我们就可以 return 我们临时存储在 stack3 中的项目，从而将其带回 1->3->4->5.

class Stack(list):
    def empty(self):
        return len(self) == 0
    def push(self, value):
        self.append(value)
    def peek(self):
        return self[-1]

def sort(stack1, stack2, stack3):
    while not stack1.empty():
        temp = stack1.pop()
        while not stack2.empty() and stack2.peek() > temp:
            stack3.push(stack2.pop())
        stack2.push(temp)
        while not stack3.empty():
            stack2.push(stack3.pop())
    return stack2

print(sort(Stack([1,5,4,2,3]), Stack(), Stack()))
print(sort(Stack([5,4,3,1,2]), Stack(), Stack()))
print(sort(Stack([1,2,3,5,4]), Stack(), Stack()))

输出：

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

如何仅使用 python 中的堆栈操作对堆栈进行排序？

How to sort a stack using only stack operations in python?

python

algorithm

sorting

stack