数据结构之python实现队列的链式存储实例

题目1：

python实现：

class QueueNode():
    def __init__(self):
        self.data = None
        self.next = None
class LinkQueue():
    def __init__(self):
        tQueueNode = QueueNode()
        self.front = tQueueNode
        self.rear = tQueueNode
    '''判断是否为空'''
    def IsEmptyQueue(self):
        if self.front == self.rear:
            iQueue = True
        else:
            iQueue = False
        return iQueue
    '''进队列'''
    def EnQueue(self,da):
        tQueueNode = QueueNode()
        tQueueNode.data = da
        self.rear.next = tQueueNode
        self.rear = tQueueNode
    '''出队列'''
    def DeQueue(self):
        if self.IsEmptyQueue():
            print("队列为空")
            return
        else:
            tQueueNode = self.front.next
            self.front.next = tQueueNode.next
            if self.rear == tQueueNode:
                self.rear = self.front
            return tQueueNode.data
    '''遍历顺序队列内的所有元素'''
    def QueueTraverse(self):
        if self.IsEmptyQueue():
            return
        else:
            tQueueNode = self.front.next
            while tQueueNode != self.rear:
                    print(tQueueNode.data,end = " ")
                    tQueueNode = tQueueNode.next
            print(tQueueNode.data,end = " ")
           
    '''链式队列长度'''
    def GetQueueLength(self):
        if self.IsEmptyQueue():
            return
        else:
            tQueueNode = self.front
            num = 0
            tQueueNode = self.front.next
            while tQueueNode != self.rear:
                num = num+1
                tQueueNode = tQueueNode.next
            num = num+1
            return num
class TestJP():
    def Josephus(self,n,k):
        qu = LinkQueue()
        i = 1
        while i <= n:
            qu.EnQueue(i)
            i = i+1
        print("队内元素为：",end = " ")
        qu.QueueTraverse()
        count = 0
        print("\n出队顺序为：")
        while qu.GetQueueLength() > 1:
            iNum = 1
            while iNum != k:
                tData = qu.DeQueue()
                qu.EnQueue(tData)
                iNum = iNum + 1
            print(qu.DeQueue(), end = " ")
            count = count + 1
            if count % 10 == 0:
                print()
        print("获得资格的为：",qu.DeQueue())
    def TestJosephus(self):
        peolenum = int(input("请输入总人数："))
        gap = int(input("请输入要出列的编号："))
        self.Josephus(peolenum,gap)
TJP =  TestJP()
TJP.TestJosephus()

结果如下：

题目2：

python实现：

class QueueNode():
    def __init__(self):
        self.data = None
        self.next = None
class LinkQueue():
    def __init__(self):
        tQueueNode = QueueNode()
        self.front = tQueueNode
        self.rear = tQueueNode
    '''判断是否为空'''
    def IsEmptyQueue(self):
        if self.front == self.rear:
            iQueue = True
        else:
            iQueue = False
        return iQueue
    '''进队列'''
    def EnQueue(self,da):
        tQueueNode = QueueNode()
        tQueueNode.data = da
        self.rear.next = tQueueNode
        self.rear = tQueueNode
    '''出队列'''
    def DeQueue(self):
        if self.IsEmptyQueue():
            print("队列为空")
            return
        else:
            tQueueNode = self.front.next
            self.front.next = tQueueNode.next
            if self.rear == tQueueNode:
                self.rear = self.front
            return tQueueNode.data
    '''遍历顺序队列内的所有元素'''
    def QueueTraverse(self):
        if self.IsEmptyQueue():
            return
        else:
            tQueueNode = self.front.next
            while tQueueNode != self.rear:
                    print(tQueueNode.data,end = " ")
                    tQueueNode = tQueueNode.next
            print(tQueueNode.data,end = " ")
class TestM():       
    def MatchAB(self):
        quA = LinkQueue()    # 存放女生
        quB = LinkQueue()    # 存放男生
        print ("输入选手编号，如果男生输入M**，如果是女生输入F**,如果结束输入“#”：")
        num = input("请输入选手编号：")
        while num != "#":
            if num[0]== "F":
                quA.EnQueue(num) 
            elif num[0] == "M":
                quB.EnQueue(num)
            else:
                print("输入错误")
            num = input("请输入选手编号：")
        print("A队列的女生有：")
        quA.QueueTraverse()
        print("\nB队列的男生有：")
        quB.QueueTraverse()
        print()
        count = 0
        while True:
            if quA.IsEmptyQueue() and quB.IsEmptyQueue():
                print("两队均为空，组合结束")
                break
            elif quA.IsEmptyQueue():
                print("女生队为空")
                print("男生队还剩：")
                quB.QueueTraverse()
                break
            elif quB.IsEmptyQueue():
                print("男生队为空")
                print("女生队还剩：")
                quA.QueueTraverse()
                break
            else:
                result1 = quA.DeQueue()
                result2 = quB.DeQueue()
                print(result1,"组合",result2)
                count = count + 1
        print()
        print("共有",count,"个组合")
MAB = TestM()
MAB.MatchAB()

结果如下：