我簡(jiǎn)單寫了個(gè)規(guī)則，大家說(shuō)可以，然后，我們就開始吧，我習(xí)慣把該做的事情提前一天做（如果有時(shí)間的話）。
今天給大家分享的書籍《Python程序員面試算法寶典》第二章第七小節(jié)：用隊(duì)列實(shí)現(xiàn)一個(gè)排序系統(tǒng)（關(guān)于人員入隊(duì)列與出隊(duì)列）。
如果你是第一次看，也許，你可以看看本系列下面的文章：
Python數(shù)據(jù)結(jié)構(gòu)：鏈表合集（12+7），復(fù)現(xiàn)幾遍，包你學(xué)會(huì)
Smaller And Smarter Python數(shù)據(jù)結(jié)構(gòu)：自己動(dòng)手實(shí)現(xiàn)棧
Smaller Python數(shù)據(jù)結(jié)構(gòu)：自己動(dòng)手實(shí)現(xiàn)隊(duì)列
Smarter Python數(shù)據(jù)結(jié)構(gòu)：如何翻轉(zhuǎn)棧
Smarter Python數(shù)據(jù)結(jié)構(gòu)：根據(jù)入棧序列來(lái)判斷可能的出棧序列
Smarter Python數(shù)據(jù)結(jié)構(gòu)：利用O(1)的時(shí)間復(fù)雜度求棧中最小元素
Smarter Python數(shù)據(jù)結(jié)構(gòu)：如何用兩個(gè)棧模擬隊(duì)列
今日問(wèn)題
'''
目標(biāo)：寫一個(gè)程序，設(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)
能讓每個(gè)進(jìn)入隊(duì)伍的用戶都能看到自己在隊(duì)列中所處位置的變化。
輸入：進(jìn)入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
'''
要求
1、進(jìn)入隊(duì)列的每個(gè)用戶可以看到自己的信息
2、隊(duì)伍可能隨時(shí)有人加入和退出
3、當(dāng)有人退出時(shí)，需要重新給用戶進(jìn)行排序
解題
首先我們之前已經(jīng)寫好了棧的基本操作，在b_2_implementation_queue.py文件中，所以我們先導(dǎo)入這個(gè)包。
from StackQueueHash.b_2_implementation_queue import LinkQueue
方法：基本法-List隊(duì)列
'''
Method One : 基本法-List隊(duì)列
核心思想：這個(gè)題不難，我們之前動(dòng)手實(shí)現(xiàn)的隊(duì)列即可完成對(duì)應(yīng)功能，難在如何優(yōu)化，
方法一是基本方法，我們用List隊(duì)列，方便實(shí)現(xiàn)隨機(jī)用戶離隊(duì)。
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: # 一個(gè)用戶類
def __init__(self, id, name):
self.id = id # 用戶id，唯一不可變
self.name = name # 用戶名
self.seq = 0 # 用戶入隊(duì)序號(hào)
# 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: # 排序系統(tǒng)隊(duì)列
def __init__(self):
self.q = ListQueue() # 初始化一個(gè)隊(duì)列
def enter_queue(self, u): # 入隊(duì)列
u.set_seq(self.q.queue_len() + 1) # 元素序列號(hào)
self.q.queue_push(u) # 添加元素
def pop_queue(self, u): # 出隊(duì)列，不一定是隊(duì)首
self.q.queue.remove(u) # 出隊(duì)列
self.update_seq() # 更新隊(duì)列
def update_seq(self): # 更新元素序列號(hào)
i = 1
for u in self.q.queue:
u.set_seq(i) # 重新設(shè)置隊(duì)列序號(hào)
i = i + 1
# 打印隊(duì)列信息
def print_queue(self):
for i in self.q.queue: # 遍歷打印人員信息
print(i.to_string())
# 初始化隊(duì)列，讓人員入隊(duì)列
def init_user_queue(user_dict, my_queue):
for k, v in user_dict.items(): # 遍歷存儲(chǔ)了隊(duì)列人員信息的字典
user = User(v, k) # 初始化人員對(duì)象
my_queue.enter_queue(user) # 入隊(duì)列
測(cè)試代碼
# 當(dāng)然，也許還有別的方法，比如建一個(gè)輔助的鏈表
# 歡迎你說(shuō)出你的想法
# 程序入口，測(cè)試函數(shù)功能
if __name__ == '__main__':
user_dict = {'Hadoop': 1, 'Spark': 2, 'Hive': 3, 'SQL': 4} # 方便書寫，我們把user信息寫到字典里
my_queue = MyQueue() # 初始化一個(gè)隊(duì)列
init_user_queue(user_dict, my_queue) # 初始化隊(duì)列元素，人員入隊(duì)列
print('當(dāng)前隊(duì)列人員信息：')
my_queue.print_queue() # 打印入隊(duì)列后所有人員
import random
queue_len = my_queue.q.queue_len()
seq = random.randint(0, queue_len-1)
user = my_queue.q.queue[seq]
# 獲取到一個(gè)隨機(jī)人員
print('離開人員信息：')
print(user.to_string()) # 打印離隊(duì)人員信息
my_queue.pop_queue(user) # 讓獲取到的隨機(jī)人員出隊(duì)列
print('剩余人員信息：') # 打印剩余人員信息
my_queue.print_queue()
優(yōu)化1
'''
優(yōu)化1：前面我們用的是List實(shí)現(xiàn)的隊(duì)列，但其效率較低，特別是當(dāng)隊(duì)列元素變多，
再要隨機(jī)刪除時(shí)，List 的底層是數(shù)組（array），其最大的時(shí)間空間消耗出現(xiàn)在存
儲(chǔ)元素增長(zhǎng)超過(guò)當(dāng)前數(shù)組分配的大小時(shí)，所有元素都必須移動(dòng)到新的位置，尤其對(duì)于
頭部的插入與刪除（O(n)），其實(shí)Python里有種數(shù)據(jù)結(jié)構(gòu)叫：deque，雙隊(duì)列，
Python 中的 List 類型（使用其內(nèi)部的 append：尾部進(jìn)，和 pop 成員函數(shù)：尾
部出，左端受限）能勝任 stack 的角色，但其在前端的 pop（或 insert）的操作
時(shí)間都是線性級(jí)的，下面我們用deque來(lái)代替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: # 排序系統(tǒng)隊(duì)列
def __init__(self):
self.q = deque() # 初始化一個(gè)隊(duì)列,雙向隊(duì)列
def enter_queue(self, u): # 入隊(duì)列
u.set_seq(len(self.q) + 1) # 元素序列號(hào)
self.q.append(u) # 添加元素
def pop_queue(self): # 出隊(duì)列
self.q.popleft() # 出隊(duì)列,左邊出（隊(duì)首）
self.update_seq() # 更新隊(duì)列
def random_pop_queue(self, u): # 隨機(jī)出隊(duì)列
self.q.remove(u) # 出隊(duì)列
self.update_seq() # 更新隊(duì)列
def update_seq(self): # 更新元素序列號(hào)
i = 1
for u in self.q:
u.set_seq(i) # 重新設(shè)置隊(duì)列序號(hào)
i = i + 1
# 打印隊(duì)列信息
def print_queue(self):
for i in self.q: # 遍歷打印人員信息
print(i.to_string())
# 初始化隊(duì)列，讓人員入隊(duì)列
def init_user_queue(user_dict, my_queue):
for k, v in user_dict.items(): # 遍歷存儲(chǔ)了隊(duì)列人員信息的字典
user = User(v, k) # 初始化人員對(duì)象
my_queue.enter_queue(user) # 入隊(duì)列
測(cè)試代碼
# 當(dāng)然，也許還有別的方法，比如建一個(gè)輔助的鏈表
# 歡迎你說(shuō)出你的想法
# 程序入口，測(cè)試函數(shù)功能
if __name__ == '__main__':
user_dict = {'Hadoop': 1, 'Spark': 2, 'Hive': 3, 'SQL': 4} # 方便書寫，我們把user信息寫到字典里
my_queue = MyQueue1() # 初始化一個(gè)隊(duì)列
init_user_queue(user_dict, my_queue) # 初始化隊(duì)列元素，人員入隊(duì)列
print('當(dāng)前隊(duì)列人員信息：')
my_queue.print_queue() # 打印入隊(duì)列后所有人員
import random
queue_len = len(my_queue.q)
seq = random.randint(0, queue_len-1)
user = my_queue.q[seq]
# 獲取到一個(gè)隨機(jī)人員
print('離開人員信息：')
print(user.to_string()) # 打印離隊(duì)人員信息
my_queue.random_pop_queue(user) # 讓獲取到的隨機(jī)人員出隊(duì)列
print('剩余人員信息：') # 打印剩余人員信息
my_queue.print_queue()
運(yùn)行結(jié)果
注意哈，這兩個(gè)方法，其實(shí)差不多，只是一個(gè)隊(duì)列是用的自己寫的（性能肯定差些），一個(gè)是環(huán)境里的（雙隊(duì)列，用起來(lái)更加靈活），兩個(gè)測(cè)試代碼也是有差別的，所以我寫了兩個(gè)，希望大家學(xué)習(xí)過(guò)程中不要搞混了。
本文代碼思路來(lái)自書籍《Python程序員面試寶典》，書中部分代碼有問(wèn)題，文中已經(jīng)修改過(guò)了，并添加上了豐厚的注釋，方便大家學(xué)習(xí)，后面我會(huì)把所有內(nèi)容開源放到Github上，包括代碼，思路，算法圖解（手繪或者電腦畫），時(shí)間充裕的話，會(huì)錄制視頻。
