队列

1、有序队列（10分）
题目内容：
一开始给出了一个由小写字母组成的字符串 S。我们规定每次移动中，选择最左侧的字母，将其从原位置移除，并加到字符串的末尾。这样的移动可以执行任意多次
返回我们移动之后可以拥有的最小字符串（注：在Python3中，字符串的大小可用不等号比较）。
输入格式:
S。S为仅含有小写字母的字符串，长度不超过100000。
输出格式：
一个与S等长的字符串。
输入样例：
"cba"
输出样例：
acb

代码模板(建议复制粘贴使用)：
def func(S):
# your code here
return output
S = eval(input())
print(func(S))
时间限制：500ms内存限制：32000kb

代码1
解题思路：用本章学的队列，依次循环比较字符串大小
但队列时间复杂度大，用例4未通过

class Queues:
    # 队列，为了不与自带函数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):
    string = Queues()
    minstr = S  # 初始最小为S，若小则替换
    n = 0
    for letter in S:
        string.enqueue(letter)
    while n < string.size()-1:
        string.enqueue(string.dequeue())
        midstr = ''.join(string.items)[::-1]
        if minstr > midstr:
            minstr = midstr
        n += 1

    return minstr

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

代码2
解题思路：直接切片重组字符串，进行比较大小

def func(S):
    minstr = S  # 初始最小为S，若小则替换
    for i in range(len(S)):
        S = S[1:]+S[0]
        if S < minstr:
            minstr = S
    return minstr


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

2、最近的请求次数（10分）
题目内容：
计算每个事件发生之时，往前算10000毫秒内有多少个事件发生，包含当事件；也即对于列表中的每个元素k，算出整个列表中有多少个元素介于k-10000和k（两端均含）之间。
输入格式:
一个已排序列表mylist，所有元素为非负整数，记录各个请求的发生时间，单位为毫秒。
输出格式：
一个与mylist等长的列表。
输入样例：
[0,10,100,1000,10000,20000,100000]
输出样例：
[1,2,3,4,5,2,1]

代码模板(建议复制粘贴使用)：
def func(mylist):
# your code here
return output

mylist = eval(input())
print(func(mylist))
时间限制：500ms内存限制：32000kb
解题思路：
队列，先入队的第一个元素进行计算，然后再加入新的元素入队，
同时循环判断队首元素-队尾元素是否大于10000
若大于，除去队尾元素；否则返回队列长度
此处存在坑：若存在相同元素，需要计入后面相同元素的个数
代码：

def func(mylist):
    """
    队列，先入队的第一个元素进行计算，然后再加入新的元素入队，
    同时循环判断队首元素-队尾元素是否大于10000
    若大于，除去队尾元素；否则返回队列长度
    坑：若存在相同元素，需要计入后面相同元素的个数
    """
    q = Queues()
    n = 0
    newlist = []
    output = []
    for num in mylist:
        q.enqueue(num)
    while n<len(mylist):
        first = q.dequeue()
        newlist.append(first)
        while newlist[-1] - newlist[0]>10000:
            newlist.pop(0)
        sum = 0
        for i in reversed(q.items):   #队列翻转，若第一个不是，直接退出
            if i == newlist[-1]:
                sum += 1
            else:
                break
        output.append(len(newlist)+sum)
        n += 1
    return output


mylist = eval(input())
print(func(mylist))

3、基数排序（10分）
题目内容：
实现一个基数排序算法，用于10进制的正整数从小到大的排序。
思路是保持10个队列(队列0、队列1......队列9、队列main)，开始，所有的数都在main队列，没有排序。
第一趟将所有的数根据其10进制个位(0_{9)，放入相应的队列0}9，全放好后，按照FIFO的顺序，将每个队列的数合并排到main队列。
第二趟再从main队列队首取数，根据其十位的数值，放入相应队列0~9，全放好后，仍然按照FIFO的顺序，将每个队列的数合并排到main队列。
第三趟放百位，再合并；第四趟放千位，再合并。
直到最多的位数放完，合并完，这样main队列里就是排好序的数列了。
输入格式:
一个列表mylist，其中mylist包含一些需要排序的正整数，正整数互不相同且均不超过100000，且个数在1至1000之间。
输出格式：
一个与mylist等长的列表。
输入样例：
[8, 91, 34, 22, 65, 30, 4, 55, 18]
输出样例：
[4, 8, 18, 22, 30, 34, 55, 65, 91]
代码模板(建议复制粘贴使用)：
def func(mylist):
# your code here
return output

mylist = eval(input())
print(func(mylist))

def func(mylist):
    i = 0  #初始为个位排序
    n = 1  #最小是1位数
    max_num = max(mylist)
    while max_num > 10 ** n:  # 最大数是几位数
        n += 1
    while i < n:
        bucket = {}  #构建桶
        for x in range(10):
            bucket.setdefault(x, [])  #每个桶都设置为空
        for x in mylist:  #每位数进行排序
            radix = int(x/(10**i)%10)   #基数位
            bucket[radix].append(x)  #元素放入对应基数位桶中
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:
                for y in bucket[k]:
                    mylist[j] = y
                    j += 1
        i += 1
    return mylist


mylist = eval(input())
print(func(mylist))

第3个用例没有通过，暂时没有找到原因

打印流程：
1、创建打印队列对象
a 时间按照秒的单位流逝
按照概率生成打印作业，加入打印队列
如果打印机空闲，且队列不空，则取出队首作业
打印，记录此作业等待时间
如果打印机忙，则按照打印速度进行1秒打印
如果当前作业打印完成，则打印机进入空闲
b 时间用尽， 开始统计平均等待时间
c 作业的等待时间
生成作业时，记录生成的时间戳
开始打印时，当前时间减去生成时间即可
d 作业的打印时间
生成作业时，记录作业的页数
开始打印时，页数除以打印速度即可

代码

import random

class Printer:
    """
    打印机初始状态、打印时间流逝、工作状态、新任务
    """
    def __init__(self, ppm):
        # 初始化，打印速度、当前任务、任务倒计时
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        # 打印1s
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None

    def busy(self):
        # 打印忙
        if self.currentTask != None:
            return True
        else:
            return False

    def startNext(self, newtask):
        # 新作业共需要的时间
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages()\
                             * 60/self.pagerate


class Task:
    """
    打印任务 生成此任务时间，页数1-20随机
    """
    def __init__(self, time):
        self.timestamp = time
        self.pages = random.randrange(1, 21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages

    def waitTime(self, currenttime):
        return currenttime - self.timestamp


def newPrintTask():
    # 1/180的概率生成任务
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False


def simulation(numSeconds, pagesPerMinute):
    # 打印模式，每min多少页
    labprinter = Printer(pagesPerMinute)
    printQueue = []
    waitingtimes = []
    for currentSecond in range(numSeconds):
        if newPrintTask():
            task = Task(currentSecond)
            printQueue.insert(0, task)

        if (not labprinter.busy()) and printQueue:
            nexttask = printQueue.pop()
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)

        labprinter.tick()
    averageWait = sum(waitingtimes)/len(waitingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining." %(averageWait, len(printQueue)))


for i in range(10):
    simulation(3600, 10)

双端队列
“回文词”指正读和反读都一样的词
判断是否是回文词

代码

def palchecker(astring):
    chardeque = []
    for ch in astring:
        chardeque.append(ch)

    stillEqual = True
    while len(chardeque) > 1 and stillEqual:
        first = chardeque.pop()
        last = chardeque.pop(0)
        if first != last:
            stillEqual = False
    return stillEqual

print(palchecker("lsdkdsl"))