#demonstrates a stack implemented as a list
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd #data item
self.pNext = None #next link in list
def displayLink(self): #display ourself
print self.dData,
#end class Link
class LinkList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #first item on list
#(no links on list yet)
def __del__(self): #destructor (deletes list)
self.__init__()
def isEmpty(self): #true if list is empty
return self._pFirst == None
def insertFirst(self, dd): #insert at start of list
#make new link
pNewLink = Link(dd)
pNewLink.pNext = self._pFirst #newLink-->old first
self._pFirst = pNewLink #first-->newLink
def deleteFirst(self): #delete first item
#(assumes list not empty)
pTemp = self._pFirst #save old first link
self._pFirst = self._pFirst.pNext #remove it: first-->old next
key = pTemp.dData #remember data
del pTemp #delete old first link
return key #return deleted link's data
def displayList(self): #display all links
pCurrent = self._pFirst #start at beginning of list
while pCurrent: #until end of list,
pCurrent.displayLink() #print data
pCurrent = pCurrent.pNext #move to next link
#end class LinkList
class LinkStack:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pList = LinkList() #make a linked list
def __del__(self): #destructor
del self._pList #delete the linked list
def push(self, j): #put item on top of stack
self._pList.insertFirst(j)
def pop(self): #take item from top of stack
self._pList.deleteFirst()
def isEmpty(self): #true if stack is empty
return self._pList.isEmpty()
def displayStack(self):
print
print 'Stack (top-->bottom):',
self._pList.displayList()
#end class LinkStack
theStack = LinkStack() #make stack
theStack.push(20) #push items
theStack.push(40)
theStack.displayStack() #display stack (40, 20)
theStack.push(60) #push items
theStack.push(80)
theStack.displayStack() #display (80, 60, 40, 20,)
theStack.pop() #pop items (80, 60)
theStack.pop()
theStack.displayStack() #display stack (40, 20)
#end
#demonstrates list with first and last references
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd #data item
self.pNext = None #next link in list
def displayLink(self): #display this link
print self.dData,
#end class Link
class FirstLastList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #first link
self._pLast = None #last link
def __del__(self): #destructor
self.__init__() #deletes list
def isEmpty(self): #true if no links
return self._pFirst == None
def insertFirst(self, dd): #insert at front of list
pNewLink = Link(dd) #make new link
if self.isEmpty(): #if empty list,
self._pLast = pNewLink #newLink <-- last
pNewLink.pNext = self._pFirst #newLink-->old first
self._pFirst = pNewLink #first-->newLink
def insertLast(self, dd): #insert at end of list
pNewLink = Link(dd) #make new link
if self.isEmpty(): #if empty list,
self._pFirst = pNewLink #first --> newLink
else:
self._pLast.pNext = pNewLink #old last --> newLink
self._pLast = pNewLink #newLink <--last
def removeFirst(self): #remove first link
#(assumes non-empty list)
pTemp = self._pFirst #remember first link
if not self._pFirst.pNext: #if only one item
self._pLast = None#None <-- last
self._pFirst = self._pFirst.pNext #first-->old next
del pTemp #delete the link
def displayList(self):
print 'List (first-->last):',
pCurrent = self._pFirst #start at beginning
while pCurrent: #until end of list,
pCurrent.displayLink() #print data
pCurrent = pCurrent.pNext #move to next link
#end class FirstLastList
theList = FirstLastList() #make new list
theList.insertFirst(22) #insert at front
theList.insertFirst(44)
theList.insertFirst(66)
theList.insertLast(11) #insert at rear
theList.insertLast(33)
theList.insertLast(55)
theList.displayList() #display the list
print
print 'Deleting first two items'
theList.removeFirst() #remove first two items
theList.removeFirst()
theList.displayList() #display again
#end
#demonstrates queue implemented as double-ended list
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd #data item
self.pNext = None #next link in list
def displayLink(self): #display this link
print self.dData,
#end class Link
class FirstLastList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #first link
self._pLast = None #last link
def __del__(self): #destructor
self.__init__() #deletes list
def isEmpty(self): #true if no links
return self._pFirst == None
def insertLast(self, dd): #insert at end of list
pNewLink = Link(dd) #make new link
if self.isEmpty(): #if empty list,
self._pFirst = pNewLink #first --> newLink
else:
self._pLast.pNext = pNewLink #old last --> newLink
self._pLast = pNewLink #newLink <--last
def removeFirst(self): #delete first link
#(assumes non-empty list)
pTemp = self._pFirst #remember first link
temp = self._pFirst.dData
if not self._pFirst.pNext: #if only one item
self._pLast = None#None <-- last
self._pFirst = self._pFirst.pNext #first-->old next
del pTemp #delete the link
return temp
def displayList(self):
pCurrent = self._pFirst #start at beginning
while pCurrent: #until end of list,
pCurrent.displayLink() #print data
pCurrent = pCurrent.pNext #move to next link
#end class FirstLastList
class LinkQueue:
def __init__(self):
self._theList = FirstLastList()
def isEmpty(self): #true if queue is empty
return self._theList.isEmpty()
def insert(self, j): #insert, rear of queue
self._theList.insertLast(j)
def remove(self): #remove, front of queue
return self._theList.removeFirst()
def displayQueue(self):
print 'Queue (front-->rear):',
self._theList.displayList()
print
#end class LinkQueue
theQueue = LinkQueue() #make a queue
theQueue.insert(20) #insert items
theQueue.insert(40)
theQueue.displayQueue() #display queue (20, 40)
theQueue.insert(60) #insert items
theQueue.insert(80)
theQueue.displayQueue() #display queue (20, 40, 60, 80)
print 'Removing two items'
theQueue.remove() #remove items (20, 40)
theQueue.remove()
theQueue.displayQueue() #display queue (60, 80)