在 LinkedList 中实现队列

Question

一道作业题，老师要我在LinkedList中实现栈和队列。我使堆栈 class 没问题，但是队列部分是我遇到的问题。

这是我的 ListNode Class:

class ListNode(object):

    def __init__(self, item = None, link = None):

        '''creates a ListNode with the specified data value and link
        post: creates a ListNode with the specified data value and link'''

        self.item = item
        self.link = link

这是标记为 'Palindrome' 的代码，它基本上测试了我的堆栈（已经完成）和我的队列（我遇到了问题）。

from MyQueue import Queue
from MyStack import Stack
import string

#------------------------------------------------------------

def isPalindrome(phrase):
    forward = Queue()
    reverse = Stack()
    extractLetters(phrase, forward, reverse)
    return sameSequence(forward, reverse)

#------------------------------------------------------------

def extractLetters(phrase, q, s):
    for ch in phrase:
        if ch.isalpha():
            ch = ch.lower()
            q.enqueue(ch)
            s.pushItem(ch)

#------------------------------------------------------------

def sameSequence(q, s):
    while q.size() > 0:
        ch1 = q.dequeue()
        ch2 = s.pop()
        if ch1 != ch2:
            return False
    return True


print(isPalindrome('CooperepooC'))

现在这是我的队列 class，我知道我需要先弹出添加到列表中的第一个东西，但我该怎么做呢？在我的代码中，我正在弹出 self.head 这是列表中最近添加的（如堆栈）我需要做什么才能从头删除？ PS。问题出在出列中。

这是我的队列 class:

from ListNode import ListNode
#----------------------------------------------------------------------

class Queue:

    #----------------------------------------------------------------------

    def __init__(self):

        self.head = None

    #----------------------------------------------------------------------

    def size(self):

        '''return number of items in the queue

        pre: none

        post: returns number of items in the queue'''

        return self.size

    #----------------------------------------------------------------------

    def enqueue(self, item):

        '''insert x at end of queue

        pre: none

        post: x is added to the queue'''

        tempNode = ListNode(item)
        tempNode.link = self.head

        self.head = tempNode

    #----------------------------------------------------------------------

    def front(self):

        '''return first item in queue

        pre: queue is not empty; IndexError is raised if empty

        post: returns first item in the queue'''

        return self.head[0]

    #----------------------------------------------------------------------

    def dequeue(self):

        '''remove and return first item in queue

        pre: queue is not empty; IndexError is raised if empty

        post: removes and returns first item in the queue'''

        if self.emptyList():
            raise IndexError("The list is empty so we cannot pop from it.")

        else:
            tempNode = self.head(0)
            self.head = self.head.link
            return tempNode

#----------------------------------------------------------------------

    def emptyList(self):

        return self.head == None


#----------------------------------------------------------------------

    def size(self):

        '''post: returns the number of elements in the stack'''

        return len('a')

如果有人能帮我写出工作队列class，将不胜感激。

Answer 1

如果通过在链表头部添加节点来实现入队，则必须通过移除尾部来实现出队。如果您以其他方式实现入队，则出队会更容易。由于这是作业，所以我只想给出提示。

在 LinkedList 中实现队列

Implementing a queue in LinkedList

python

queue

linked-list