python基于单链表的链式队列和基于数组的循环队列

队列（queue）

• 队列是一种操作受限“”的线性数据结构，只支持入栈和出栈操作。
• 栈中的元素只能先进后出（First In First Out）。
• 队列的出口端叫作队头head，队列的入口端叫作队尾tail
• 队列的应用非常广泛，特别是一些具有额外特性的队列，如：循环队列、阻塞队列、并发队列

下面为链式队列的实现代码：

class Node(object):
    def __init__(self, value:str = None, next = None):
        self.value = str(value)
        self.next = next

class LinkedQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None
        
    def enqueue(self, value: str):
    	'''入队，将新元素放入队列'''
        new_node = Node(value)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
    
    def dequeue(self):
    	'''出队，将元素移出队列，仅允许在队头移出元素'''
        if self.head:
            value = self.head.value
            self.head = self.head.next
            if not self.head:
                self.tail = None
            return value
            
    def travel(self):
        data = []
        current = self.head
        while current:
            data.append(current.value)
            current = current.next
        return data
            
              
if __name__ == "__main__":
    queue = LinkedQueue()
    for i in range(1,7):
        queue.enqueue(i)
    print("——————当前队列数据：", queue.travel())
    message = ''
    while message != 'q':
        print('''
          *************************************************************************************************************
          **********************************************请选择相应的序号完成相应的操作************************************
          *************************************************************************************************************   
          **         q、退出操作！！！！！！                                                                          ***
          **         1、入队！                                                                                       ***
          **         2、出队！                                                                                       ***
          *************************************************************************************************************
          ''')
        message = input('——————输入下一步要进行的相应操作序号——————：')
        if message == 'q':
            break
        print("——————操作前队列数据：", queue.travel())
        if message == '1':
            value = input('——————请输入要入队的数据：')
            queue.enqueue(value)
        elif message == '2':
            queue.dequeue()
        print("——————操作后队列数据：", queue.travel())

下面为循环队列的实现代码：

class Node(object):
    def __init__(self, value:str = None, next = None):
        self.value = str(value)
        self.next = next

class CircularQueue(object):
    def __init__(self,size=0):
        self.items = [ None for i in range(size+1)]
        self.size = size+1 #队列大小 为了方便判断队满状态，循环队列会浪费一个数组的存储空间
        self.head = 0 #队头位置
        self.tail = 0 #队尾位置
        
    def enqueue(self, value: str):
        if (self.tail + 1) % self.size == self.head: 
            print("——————当前队列已满")
            return False
        tail = self.tail % self.size
        self.items[tail] = str(value)
        self.tail = (self.tail + 1) % self.size
        return True
    
    def dequeue(self):
        if self.head == self.tail:
            return False
        value = self.items[self.head]
        self.head = (self.head + 1) % self.size
        return value
            
    def travel(self):
        #print(f'——————原始数组数据：{self.items}') #为了方便判断队满状态，循环队列会浪费一个数组的存储空间
        if self.tail >= self.head:
            return self.items[self.head : self.tail]
        else:
            items = self.items[self.head:]+self.items[:self.tail]
            return items
          
              
if __name__ == "__main__":
    queue = CircularQueue(4) 
    print("——————当前队列数据：", queue.travel())
    message = ''
    while message != 'q':
        print('''
          *************************************************************************************************************
          **********************************************请选择相应的序号完成相应的操作************************************
          *************************************************************************************************************   
          **         q、退出操作！！！！！！                                                                          ***
          **         1、入队！                                                                                       ***
          **         2、出队！                                                                                       ***
          *************************************************************************************************************
          ''')
        message = input('——————输入下一步要进行的相应操作序号——————：')
        if message == 'q':
            break
        print("——————操作前队列数据：", queue.travel())
        if message == '1':
            value = input('——————请输入要入队的数据：')
            queue.enqueue(value)
        elif message == '2':
            value = queue.dequeue()
            print("——————出队数据：", value)
        print("——————操作后队列数据：", queue.travel())

最后

以上就是烂漫身影为你收集整理的python基于单链表的链式队列和基于数组的循环队列的全部内容，希望文章能够帮你解决python基于单链表的链式队列和基于数组的循环队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。