title: Implementing a queue in LinkedList
body: <p>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. </p>
  
  <p>Here is my ListNode Class:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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).</p>
  
  <pre><code>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() &gt; 0:
          ch1 = q.dequeue()
          ch2 = s.pop()
          if ch1 != ch2:
              return False
      return True
  
  
  print(isPalindrome('CooperepooC'))
  </code></pre>
  
  <p>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.</p>
  
  <p>Here is my queue class:</p>
  
  <pre><code>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')
  </code></pre>
  
  <p>If anyone could help me write out a working queue class it would be much appreciated.</p>