在不使用临时堆栈的情况下以原始顺序返回元素到堆栈

Question

我有一个包含 n 个元素的堆栈 S 和一个最初为空的队列 Q。我必须实现一个算法，该算法使用 Q 来扫描 S 以查看它是否包含某个元素 x，附加约束是我的算法必须 return 将元素返回到 S按照他们原来的顺序。强制性是我可能只使用S，Q和其他变量的常数。

我已经实现了这个算法，它使用一个临时堆栈来保存元素，然后 return 它们以原来的顺序进入原始堆栈，但是我如何在不使用临时堆栈的情况下完成这个任务？

if __name__ == '__main__':
    
    def scan(S, Q, x):
        
        for i in range(10):
            S.push(i)
        
        S1 = ArrayStack()
        flag = False
        
        for i in range(len(S)):
            Q.enqueue(S.pop())
            if Q.first() == x:
                flag = True
                print("Your desired element has been found:", Q.first())
                S1.push(Q.dequeue())
                break
            else:
                S1.push(Q.dequeue())
                
        if flag == False: 
            print("Sadly, your desired element could not be found.")
                
        
        for i in range(len(S1)):
            S.push(S1.pop())
         
        
    scan(ArrayStack(), LinkedQueue(), 9)

Answer 1

诀窍是首先将队列中的元素放回堆栈——这将使它们以相反的顺序放置——但然后对相同数量的值再次重复该过程：将它们从堆栈弹出到队列，然后再次将队列刷新回堆栈。现在他们将回到原来的顺序。

不确定函数的签名是否已经像那样给了你，但我不会将 Q 作为参数传递，因为它只服务于函数的算法，而不是调用者。另一方面，我不会在函数内部初始化堆栈，而是让调用者处理堆栈填充。这样调用者就可以控制使用哪些堆栈数据来调用函数。

所以这就是你可以做的：

def scan(S, x):
    Q = LinkedQueue()  # Create the queue here
    
    found = False
    for i in range(len(S)):
        Q.enqueue(S.pop())
        found = Q.first() == x
        if found:
            break
    i += 1  # The number of values that are currently in the queue
    # Flush the queue on the stack
    for j in range(i):
        S.push(Q.dequeue())
    # They are reversed on the stack, so remove them again
    for j in range(i):
        Q.enqueue(S.pop())
    # and finally flush the queue again
    for j in range(i):
        S.push(Q.dequeue())
    return found

这样调用：

S = ArrayStack()
# Initialise the stack here
for i in range(10):
    S.push(i)    
# Get the boolean result from the function call
found = scan(S, 12)
# Use it to display a message
if found:
    print("Your desired element has been found")
else:
    print("Sadly, your desired element could not be found.")

在不使用临时堆栈的情况下以原始顺序返回元素到堆栈

Returning elements to stack in original order without using temporary stack

python-3.x

data-structures

queue

stack