Smarter Python数据结构：用队列实现一个排序系统（关于人员入队列与出队列）

"""
目标：写一个程序，设计一个排队系统
能让每个进入队伍的用户都能看到自己在队列中所处位置的变化。
输入：进入a, b
输出：：id: 1 name: a  id: 2 name: b
Goal: write a program and design a queuing system
It enables each user entering the queue to see the change of their
 position in the queue.
Input: enter a, B
Output:: ID: 1 Name: a ID: 2 Name: B
"""

from StackQueueHash.b_2_implementation_queue import LinkQueue

"""
Method One : 基本法-List队列
核心思想：这个题不难，我们之前动手实现的队列即可完成对应功能，难在如何优化，
方法一是基本方法，我们用List队列，方便实现随机用户离队。
Method one: Basic Law list queue
Core idea: this problem is not difficult. The queue we implemented
 before can complete the corresponding functions. The difficulty
 lies in how to optimize. The first method is the basic method.
 We use list queue to facilitate the implementation of random user
 departure.
"""

class User:# 一个用户类
    def __init__(self, id, name):
        self.id = id  # 用户id，唯一不可变
        self.name = name  # 用户名
        self.seq = 0# 用户入队序号
    # set，get方法
    def get_name(self):
        return self.name
    def set_name(self, name):
        self.name = name
    def get_id(self):
        return self.id
    def get_seq(self):
        return self.seq
    def set_seq(self, seq):
        self.seq = seq
    # 返回人员完整信息
    def to_string(self):
        return"id：" + str(self.id) + " " + "name：" + self.name + " " + "seq：" + str(self.seq)
class MyQueue:# 排序系统队列
    def __init__(self):
        self.q = ListQueue()  # 初始化一个队列
    def enter_queue(self, u):# 入队列
        u.set_seq(self.q.queue_len() + 1)  # 元素序列号
        self.q.queue_push(u)  # 添加元素
    def pop_queue(self, u):# 出队列，不一定是队首
        self.q.queue.remove(u)  # 出队列
        self.update_seq()  # 更新队列
    def update_seq(self):# 更新元素序列号
        i = 1
        for u in self.q.queue:
            u.set_seq(i)  # 重新设置队列序号
            i = i + 1
    # 打印队列信息
    def print_queue(self):
        for i in self.q.queue:  # 遍历打印人员信息
            print(i.to_string())
# 初始化队列，让人员入队列
def init_user_queue(user_dict, my_queue):
    for k, v in user_dict.items():  # 遍历存储了队列人员信息的字典
        user = User(v, k)  # 初始化人员对象
        my_queue.enter_queue(user)  # 入队列

# 当然，也许还有别的方法，比如建一个辅助的链表
# 欢迎你说出你的想法
# 程序入口，测试函数功能
if __name__ == "__main__":
    user_dict = {"Hadoop": 1, "Spark": 2, "Hive": 3, "SQL": 4}  # 方便书写，我们把user信息写到字典里
    my_queue = MyQueue()  # 初始化一个队列
    init_user_queue(user_dict, my_queue)   # 初始化队列元素，人员入队列
    print("当前队列人员信息：")
    my_queue.print_queue()  # 打印入队列后所有人员
    import random
    queue_len = my_queue.q.queue_len()
    seq = random.randint(0, queue_len-1)
    user = my_queue.q.queue[seq]
    # 获取到一个随机人员
    print("离开人员信息：")
    print(user.to_string())   # 打印离队人员信息
    my_queue.pop_queue(user)  # 让获取到的随机人员出队列
    print("剩余人员信息：")    # 打印剩余人员信息
    my_queue.print_queue()

"""
优化1：前面我们用的是List实现的队列，但其效率较低，特别是当队列元素变多，
再要随机删除时，List 的底层是数组（array），其最大的时间空间消耗出现在存
储元素增长超过当前数组分配的大小时，所有元素都必须移动到新的位置，尤其对于
头部的插入与删除（O(n)），其实Python里有种数据结构叫：deque，双队列，
Python 中的 List 类型（使用其内部的 append：尾部进，和 pop 成员函数：尾
部出，左端受限）能胜任 stack 的角色，但其在前端的 pop（或 insert）的操作
时间都是线性级的，下面我们用deque来代替list。
参考链接：https://blog.csdn.net/lanchunhui/article/details/50958069
Optimization 1: We used the queue implemented by list before, but
 its efficiency is low. Especially when there are more queue elements
 and they need to be deleted randomly, the bottom layer of list is array.
 The largest time and space consumption occurs when the storage elements
 grow larger than the current array allocation. All elements must be moved
 to a new location, especially for the insertion and deletion of the header
 (o(n)), in fact, there is a data structure in Python called deque, double
 queue. The list type in python (using its internal append: tail in, and pop
 member function: tail out, left end Limited) is competent for the role of stack,
 but the operation time of its pop (or insert) in the front end is linear. Next,
 we use deque to replace list.
Reference link: https://blog.csdn.net/lanchunhui/article/details/50958069
"""

from collections import deque
class MyQueue1:# 排序系统队列
    def __init__(self):
        self.q = deque()  # 初始化一个队列,双向队列
    def enter_queue(self, u):# 入队列
        u.set_seq(len(self.q) + 1)  # 元素序列号
        self.q.append(u)  # 添加元素
    def pop_queue(self):# 出队列
        self.q.popleft()  # 出队列,左边出（队首）
        self.update_seq()  # 更新队列
    def random_pop_queue(self, u):# 随机出队列
        self.q.remove(u)  # 出队列
        self.update_seq()  # 更新队列
    def update_seq(self):# 更新元素序列号
        i = 1
        for u in self.q:
            u.set_seq(i)  # 重新设置队列序号
            i = i + 1
    # 打印队列信息
    def print_queue(self):
        for i in self.q:  # 遍历打印人员信息
            print(i.to_string())
# 初始化队列，让人员入队列
def init_user_queue(user_dict, my_queue):
    for k, v in user_dict.items():  # 遍历存储了队列人员信息的字典
        user = User(v, k)  # 初始化人员对象
        my_queue.enter_queue(user)  # 入队列

# 当然，也许还有别的方法，比如建一个辅助的链表
# 欢迎你说出你的想法
# 程序入口，测试函数功能
if __name__ == "__main__":
    user_dict = {"Hadoop": 1, "Spark": 2, "Hive": 3, "SQL": 4}  # 方便书写，我们把user信息写到字典里
    my_queue = MyQueue1()  # 初始化一个队列
    init_user_queue(user_dict, my_queue)   # 初始化队列元素，人员入队列
    print("当前队列人员信息：")
    my_queue.print_queue()  # 打印入队列后所有人员
    import random
    queue_len = len(my_queue.q)
    seq = random.randint(0, queue_len-1)
    user = my_queue.q[seq]
    # 获取到一个随机人员
    print("离开人员信息：")
    print(user.to_string())   # 打印离队人员信息
    my_queue.random_pop_queue(user)  # 让获取到的随机人员出队列
    print("剩余人员信息：")    # 打印剩余人员信息
    my_queue.print_queue()