1.有序队列
思路：利用对字符串切片处理，直接将最后一个字母拼接到后面，然后进行比较得最小字符串。

def func(S):
    min_str = S
    for i in range(len(S)):
        S = S[1:] + S[0]
        if S < min_str:
            min_str = S
    return min_str
S = eval(input())
print(func(S))

思路：应用队列的先进先出特点，设置最开始的字符串为最小值，不断的将最后一个字母出队列，然后再将这个字母入队列，与设置的字符串进行比较，若小于的话，则替换最小值，若大于的话，继续出队列、入队列。直到将字符串的所有情况都遍历一遍。

# 超出内存限制了
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
 
def func(S):
    li = []
    q = Queue()
    
    for i in S:
        q.enqueue(i)
    
    k=0
    while k <= q.size():
        first = q.dequeue()
        q.enqueue(first)
        astr = ''.join(q.items)[::-1]

        if astr not in li:
            li.append(astr)
        k = k + 1

    output = min(li)
    return output

S = eval(input())
print(func(S))

2.最近的请求次数
第一版思路：

• 就采用两个循环，对每一个元素都用列表的元素去比对；
• 结果就很显然易见，时间复杂度为O(n^2)，这一条思路时间超出了限制

# 运行时间超出限制
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
    
def func(mylist):
    # your code here
    q = Queue()
    
    for k in mylist:
        q.enqueue(k)
    
    output = []
    for i in mylist:
        cnt = 0
        n = 0
        while cnt < q.size():
            e = q.dequeue()
            if e <= i and e >= i-10000:
                n = n + 1
            q.enqueue(e)
            cnt = cnt + 1
        output.append(n)
        
    return output
     
mylist = eval(input())
print(func(mylist))

第二版改进
思路：Python构造队列这一个类，使列表右端为队列尾，列表左端为队列头；题给样例为从左到右依次递增的有序列表，则右端减掉左端小于10000的元素的个数就是需要求的；

• 将mylist列表中的元素一个一个添加进去
• 每添加一个元素mylist[k]，循环判断新元素与队头元素相减是否大于10000，如果大于10000则将队尾元素出队；
• 余下的队列长度就是满足题给要求的元素个数

# 用例3未通过，注意检查特殊值
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)

def func(mylist):
    # your code here
    q = Queue()
    cnum = []
    
    for k in mylist:
        q.enqueue(k)
        while q.items[-1]-q.items[0]>10000:
            q.dequeue()
        cnum.append(q.size())
    return cnum
     
mylist = eval(input())
print(func(mylist))

第三版全部通过。。真的。。写完发现自己是个智障。。┭┮﹏┭┮
思路：思路还是第二版的思路，就是当时没想通是运行结果提示注意检查特殊值是怎么去知道这个特殊值是啥，于是参考了一些别人的做法，然后知道了被我忽略的是列表中如果有重复元素应该怎么解决，最简单的，我在输入样例里多加了一个0，查看运行结果就知道了是自己没有对列表后第k个元素后与第k个元素值相等的元素进行计数；

class Queue:
    def __init__(self):
        self.items = [] 
    def isEmpty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)
 
def func(mylist):
    # your code here
    q = Queue()
    cnum = []
    
    for k in range(len(mylist)):
        q.enqueue(mylist[k])
        # print(q.items)
        while q.items[-1]-q.items[0]>10000:
            q.dequeue()
            # print(q.items)
        cnt = 0
        for i in range(k+1,len(mylist)):
            if mylist[i] == mylist[k]:
                cnt = cnt+1
            else:
                break
        cnum.append(q.size()+cnt)
        # print(cnum)
        # print('--------------')
    return cnum
     
mylist = [0,0,10,100,1000,10000,20000,100000]
print(func(mylist))

3.基数排序
思路题目已经给出来了，代码实现参考了老师b站的讲解；
采用了“队列”这种数据结构实现，巧用字符型这种数据类型

class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self,item):
        return self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
        

def func(mylist):
    # your code here
    q_main = Queue()
    
    for x in mylist:
        q_main.enqueue(x)
    
    d = len(str(max(mylist)))
    dstr = "%%0%dd" % d
    
    q_num = [Queue() for _ in range(10)]
    
    for i in range(-1,-d-1,-1):
        while not q_main.isEmpty():
            e = q_main.dequeue()
            de = (dstr % e)[i]  # de取位数 
            q_num[int(de)].enqueue(e)
        
        for k in range(10):
            while not q_num[k].isEmpty():
                q_main.enqueue(q_num[k].dequeue())
    output = []
    while not q_main.isEmpty():
        output.append(q_main.dequeue())
    
    return output
     
mylist = eval(input())
print(func(mylist))