Stack and Queue Implementation with Doubly Linked List

Stack and Queue Implementation with Doubly Linked List

Lets start with defining Node and DBList classes.

class Node:
def __init__(self,el):
self.e=el
self.prev=None
self.next=None

class DBList:
def __init__(self):
self.nil=Node(None)
self.nil.next=self.nil
self.nil.prev=self.nil

def getListStr(self):
nextnode=self.nil.next
el=[]
while nextnode!=self.nil:
el.append(nextnode.e)
nextnode=nextnode.next
return str(el)

def __repr__(self):
return 'DBList: '+ self.getListStr()

def insert(self,el):
z=Node(el)
z.next=self.nil.next
z.prev=self.nil
self.nil.next.prev=z
self.nil.next=z
return self

def delete(self,n):
n.prev.next=n.next
n.next.prev=n.prev
return self

def search(self,el):
x=self.nil.next
while x!=self.nil and x.e!=el:
x=x.next
return x

##Some tests
L=DBList()
L.insert(5)
L.insert(4)
L.insert(2)
print L
L.delete(L.search(2))
print L
L.delete(L.search(5))
print L

DBList: [2, 4, 5]
DBList: [4, 5]
DBList: [4]


Queue

Now it we have Doubly Linked List with insertion and deleteon in O(1) time. Note that use nil node to access last and first node in O(1) time. Lets define Queue.

class Queue:
def __init__(self):
self.q=DBList()
def __repr__(self):
return 'Queue: '+self.q.getListStr()
def enque(self,e):
self.q.insert(e)
def peek(self):
return self.q.nil.prev.e
def deque(self):
lastnode=self.q.nil.prev
if lastnode==self.q.nil: return None
self.q.delete(lastnode)
return lastnode.e
q1=Queue()
q1.enque(5)
q1.enque(3)
print q1
print q1.peek()
print q1.deque()
print q1.deque()
print q1.deque()
q1.enque(42)
print q1.peek()
print q1


Queue: [3, 5]
5
5
3
None
42
Queue: [42]


Stack

Quite similar

class Stack:
def __init__(self):
self.q=DBList()
def __repr__(self):
return 'Stack: '+self.q.getListStr()
def push(self,e):
self.q.insert(e)
def peek(self):
return self.q.nil.next.e
def pop(self):
nextnode=self.q.nil.next
if nextnode==self.q.nil: return None
self.q.delete(nextnode)
return nextnode.e
q1=Stack()
q1.push(5)
q1.push(3)
print q1
print q1.peek()
print q1.pop()
print q1.pop()
print q1.pop()
q1.push(42)
print q1.peek()


Stack: [3, 5]
3
3
5
None
42


Tags:

Categories:

Updated: