Python:带队列的selectionsort算法

我遇到了一个Python练习:

1. 读入一些字符串并将其放入队列中
2. 按字典顺序将字符串排序到新队列中,但不应更改原始队列。我应该从头开始编写函数(例如,排序后的函数无法使用)
3. 不允许使用数组

我想我已经为步骤1找到了一个函数,但我为步骤2挣扎了几个小时。我真的很感激任何帮助!

以下是我的第1步代码片段:

q1 = []

def DisplayQueue(queue):
    for Item in queue:
        print(Item)

def PushQueue(queue):
    x = True
    while x:
        user_input = input("Please enter a string (for exit type: exit): ")
        if user_input == "exit":
            x = False
        else:
           queue.append(user_input)
    return queue

queue = PushQueue(q1)