Python：先进先出打印

Question

我是一名Python初学者，我在使用这个程序时遇到了问题：

下面的程序是一个后进先出（LIFO）结构。我想将它改为先进先出（FIFO）结构的程序。

from NodeList import Node

class QueueLL:

    def __init__(self):
        self.head = None


    def enqueueQLL(self,item):
        temp = Node(str(item))
        temp.setNext(self.head) 
        self.head = temp
        length = max(len(node.data) for node in self.allNodes()) if self.head else 0
        print('\u2510{}\u250c'.format(' '*length))
        for node in self.allNodes():
            print('\u2502{:<{}}\u2502'.format(node.data, length))
        print('\u2514{}\u2518'.format('\u2500'*length))

以下是 NodeList：

class Node:

    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

注意: "Rainbow" 应该在 "Arc" 底部或者按照FIFO(下图是LIFO)。 我在考虑像 NodeList 中添加一个新的类似 setPrevious 的定义，但我不知道怎么做。 (说实话，我对这些 self.head = none 的东西非常陌生，我过去通常写 self.items=[])。

任何帮助和提示都将不胜感激！谢谢！

- arcwinolivirus

Answer 1

除了学习目的，我不建议使用自定义数据结构来创建LIFO或FIFO。毕竟内置的数据类型list已经很好了。

您可以使用append方法添加项目，并使用pop方法删除它们。对于LIFO，这将如下所示：

stack = list()
stack.append(1)
stack.append(2)
stack.append(3)

print stack.pop()  #3
print stack.pop()  #2
print stack.pop()  #1

如果你给pop传递一个整数参数，就可以指定要删除的元素。对于FIFO，请使用索引0表示第一个元素：

注：翻译中的HTML标签已保留。

stack = list()
stack.append(1)
stack.append(2)
stack.append(3)

print stack.pop(0)  #1
print stack.pop(0)  #2
print stack.pop(0)  #3

- Constantinius

---

我也想使用那个内置的数据类型，但我不知道如何将其转换为链表。 - arcwinolivirus

为什么需要链表？ - Constantinius

我在我们的课程中被要求使用链表实现队列（包括其他数据结构类型）。 - arcwinolivirus

list 对于栈来说是可以的，因为 .append() 和 .pop() 都很快。然而，它不适用于先进先出队列，因为 .pop(0) 很慢（它的复杂度不是 O(1)）。使用 collections.deque 作为先进先出队列的数据结构。 - nitsas

Answer 2

好的，既然你的课程现在可能已经结束了，并且你在问题本身中没有提到你的课程（或者它必须是一个链接列表），我现在就告诉你内置的简单方法，这可能更符合你目前的情况（并将帮助找到你的问题的人）。

import sys;
if sys.version_info[0]>2: #Just making sure the program works with both Python 2.x and 3.x
    from queue import Queue
else:
    from Queue import Queue

q=Queue()
q.put("first") #Put an item on the Queue.
q.put("second")
q.put("third")

while not q.empty(): #If it's empty, the program will stall if you try to get from it (that's why we're checking)
    print(q.get()) #Get an item from the Queue

This outputs

first
second
third

实际上，我不确定这种方法与Constantinius的回答相比有什么优势，但由于它是一个包含的模块，我认为一定有某些优势。我知道它们与threading模块中的线程一起使用。与队列相关的函数比我在这里提到的还要多。

要了解更多，请打开您的Python解释器并输入以下内容：

from queue import Queue #or from Queue import Queue for 2.x
help(Queue) #Press q to exit the help

不要问我什么是阻塞，但是这里可能使用了队列类文档中使用的术语: http://en.wikipedia.org/wiki/Blocking_(computing)

- Brōtsyorfuzthrāx

---

队列类型是线程安全的，而列表类型不是（这就是为什么队列可以阻塞）。在此以FIFO方式创建、填充和清空列表比使用队列执行相同操作快30多倍。因此，如果您不需要线程安全性... - Stephan Lukits

Answer 3

class Box:
    def __init__(self,data):
        self.data=data
        self.next=None        
class List:
    def __init__(self):
        self.head=None        
    def add(self,item):                
        temp=Box(item)                
        if self.head==None:
            self.head=temp
            self.prev=temp
        self.prev.next=temp
        self.prev=self.prev.next               
    def PrintList(self):
        while self.head!=None:
            print(self.head.data)
            self.head=self.head.next

myList=List()
myList.add("Vinoth")
myList.add("Karthick")
myList.add("Ganesh")
myList.add("Malai")
myList.add("Shan")
myList.add("Saravana")
myList.PrintList()

- Vinoth Karthick