使用python的排队系统问题

Question

我有一个名字数组:队列Andrew，队列Alex，队列Amy, Alex John, Alex Peter, John Jamie, Jamie Jack, John Adam

我试图做的函数将这些名称排队。名字中有"排队"的名字会正常加入，前面有别人名字的名字会排在前面的名字后面。因此，上面给出的数组的答案将是Andrew, Alex, John, Jamie, Jack, Adam, Peter, Amy。

这是我用来做这件事的函数:

def test(arr):
timer =0
usedname ="pop"
newlist=[]
for i in arr:
new_string = i.replace("MainQueue ","")
newlist.append(new_string)
ans=newlist
for i in range(len(newlist)):
if (len(newlist[i].split()) > 1):
x = newlist[i].split() 
y = ans.index(x[0])  
name=x[1]  
if x[0] == usedname:
timer+=1
newlist.remove(newlist[i])
ans.insert(y+timer,name)
else:
timer =1
newlist.remove(newlist[i])
ans.insert(y+timer,name)
usedname = x[0];
print(' '.join(ans))

但是我得到的结果是Andrew Alex John Adam Jamie Jack Peter Amy

我不知道我需要改变什么才能做到这一点，我觉得我尝试的解决方案可能太复杂了。

Answer 1

我发现这个函数满足您的要求:

input_array = ["Queue Andrew", "Queue Alex", "Queue Amy", "Alex John", "Alex Peter", "John Jamie", "Jamie Jack", "John Adam"]
def test(arr):
result = []
for elem in arr[:]:
a, b = elem.split()
if a == "Queue":
result.append(b)
arr.remove(elem)
i = len(arr) #starts at the end of the list (for iterating in reverse)
while 0 < len(arr): # only as long as there are names left
i -= 1 # next element (normally i += 1 but reversed)
if i < 0: # if loop reached the front of the list, start over from the end.
i = len(arr)-1 #start again from the end
a, b = arr[i].split()
if a in result:
result.insert(result.index(a) + 1, b)
arr.remove(arr[i])
return result
print(test(input_array))
#prints ['Andrew', 'Alex', 'John', 'Jamie', 'Jack', 'Adam', 'Peter', 'Amy']

首先它添加了所有的"队列名称"元素到列表中。然后，它迭代其余的条目，直到arr为空(顺序相反，以便结果是正确的)，将名称(result.insert())插入到另一个名称(result.index(a)+1)的索引后面

如果我没记错的话，这个算法有最坏情况O(n^2)和最好情况O(n)。

编辑

以相反的顺序遍历列表会使它稍微复杂一些。不是从i=0开始，我们需要从i=len(arr)开始。然后在每次迭代中，我们将i减1。循环在数组上迭代多次，直到数组为空。因此，如果i到达第0个元素，它需要从arr的末尾开始。