# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
# 
#queue.py
 
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 inDataProcess(lis):
    max_lengh = max([len(lis[i]) for i in range(len(lis))])  # 查詢記錄中最長(zhǎng)的字符串
    return [x.zfill(max_lengh) for x in lis]  # 將每一個(gè)記錄都通過(guò)添加前導(dǎo)0的方式轉(zhuǎn)化為一樣的長(zhǎng)度

def radixSort(seq:list):
    source_data = inDataProcess(seq)  # 輸入處理
    res = []  # 用于保存結(jié)果列表
    big_queue = Queue()  # 用于轉(zhuǎn)化的隊(duì)列
    for ele in source_data:
        big_queue.enqueue(ele)
 
    for i in range(len(source_data[0])-1,-1,-1):
        buckets = []  # 用于保存每一趟的10各基數(shù)桶
        for num  in range(10):  # 建立10個(gè)基數(shù)桶
            bucket = Queue()
            buckets.append(bucket)
        # 在基數(shù)桶中插入數(shù)據(jù)
        while not big_queue.isEmpty():
            currentEle = big_queue.dequeue()  # 大隊(duì)列中出隊(duì)一個(gè)元素
            index = int(currentEle[i])  # 根據(jù)元素對(duì)應(yīng)位上的值添加進(jìn)對(duì)應(yīng)的基數(shù)桶中
            buckets[index].enqueue(currentEle)
 
        # 把基數(shù)桶串聯(lián)起來(lái)
        new_big_queue = Queue()
        for bucket in buckets:
            while not bucket.isEmpty():
                out = bucket.dequeue()
                new_big_queue.enqueue(out)
                # print(new_big_queue.size())
        # 修改big_queue
        big_queue = new_big_queue
    # 將大隊(duì)列中的元素保存到結(jié)果列表中
    while not big_queue.isEmpty():
        res.append(big_queue.dequeue().lstrip('0'))  # 利用lstrip('0')去掉前導(dǎo)0
    return res

if __name__ == '__main__':
 
    lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
    lis = [str(i) for i in lis]
    print(radixSort(lis))
    ''' 結(jié)果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
    '843', '856', '923', '932', '999']'''