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