Implementing a queue in LinkedList

Question

For a homework question, my teacher wants me to implement a stack and a queue in a LinkedList. I made the stack class no problem, however the queue part is what I am having trouble with.

Here is my 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

Here is the code which is labeled 'Palindrome' which basically tests out both my Stack (Already completed) and my Queues(Which I am having trouble with).

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'))

Now here is my Queue class, I know I need to pop the first thing added to the list first, but how would I go about doing that? In my code I am popping the self.head which is the most recent addition to the list (like a stack) what would I need to do to remove from the beginning? PS. The problem is in the dequeue.

Here is my queue 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')

If anyone could help me write out a working queue class it would be much appreciated.

Answer 1

If you implement enqueue by adding node at the list head, you have to dequeue by removing the tail. If you implement enqueue in the other way, dequeue would be easier. Since this is homework, I'd like to only give hint.