我必须仅使用一个队列从上到下按升序排序堆栈

Question

def stack_push(stack, a, size):
    if isfull(stack, size):
        print("Error, stack is full")
        return stack
    else:
        stack.append(a)
        return stack


def stack_pop(stack, size):
    if isempty(stack):
        return
    else:
        return stack.pop(0)


def isfull(stack, size):
    return len(stack)>=size

def isempty(stack):
    return len(stack)==0

s1=[20,20,17,99,8,88,3,10]
temp=[]
s1size=8

我必须编写代码的其余部分，但是我有0个线索如何从这里开始，在不使用插入或任何队列函数的情况下，我该怎么办？另外，如何将堆栈或值从int进行排队索引值进行比较？

Answer 1

这是一个有趣的。即使可能不是您要问的，但只有使用（FIFO）队列对（LIFO）堆栈进行分类的方式！从本质上讲，您只需按顺序排列的顺序保留队列，并在堆栈中对每个元素执行修改后的插入。这是一些可以执行操作的伪代码：

while (!stk.empty()):
    x = stk.pop() # item to insert
    first = q.peek() # first item in sorted queue

    if (q.peek() < x):
        # condition for new largest item
        q.push(x)
        # x will be new first in sorted queue
        first = x

    else:
        # condition for not-largest item
        q.push(q.pop())
        while (q.peek() > x && q.peek() != first):
            q.push(q.pop())
        q.push(x)

    # now loop so queue is back in it's sorted order
    while (q.peek() != first):
        q.push(q.pop())
 

不漂亮！但这应该完成工作。