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.
