Learning Python: Programming and Data Structures- Tutorial 19- Stacks, Queues, Linked Lists

1. Stacks in Python

For a detailed explanation about the general ideas and principles behind a stack data structure, you might find this tutorial useful. Default Python lists can easily be used as stacks in Python. Appending to a list is the equivalent on pushing an element onto a stack. Popping from a list is the equivalent of de-queing an element from the stack.


# You can use Lists as Stacks in Python
stack = [10,9,8,7,6,5] # Original contents of the stack print "Original Contents of the Stack" print stack # Appending to a list is the same as pushing to a stack stack.append(1) stack.append(2) # In the two steps above we push 1 and 2 onto the stack print "After pushing 1 and 2 onto the stack it looks like:" print stack # Now we explore the pop operation poppedValue = stack.pop() # Display the popped value print "Popped Value:" print poppedValue # Now display what the stack looks like: print "After the pop operation the stack looks like:" print stack # Now we explore the pop operation again poppedValue = stack.pop() # Display the popped value print "Again, we pop a value from the top of the stack. Popped Value:" print poppedValue # Now display what the stack looks like: print "After the second pop operation the stack looks like:" print stack


Output of the Program above:


~/work/pythontutorials$ python DataStructuresStacks.py 
Original Contents of the Stack
[10, 9, 8, 7, 6, 5]
After pushing 1 and 2 onto the stack it looks like:
[10, 9, 8, 7, 6, 5, 1, 2]
Popped Value:
2
After the pop operation the stack looks like:
[10, 9, 8, 7, 6, 5, 1]


2. Queues in Python


For a detailed explanation about the functioning of the Queue data structure (which is a FIFO Data Structure) you might find this tutorial very useful.
For creating Queues in Python we can use the collections.deque data structure because it was designed to have efficient pops and pushes from both ends unlike lists which are designed to work efficiently from the right end.
# Deques from collections are convenient to use as Queues
# It is not efficient to use lists because they are efficient for reading/appending/popping from the end
# But they are not so efficient for dequeing from the beginning
from collections import deque
queue = deque(["London","Paris","New York","Delhi"])
print "The Original Queue:"
print queue

# Now we also queue a few more cities
queue.append("Mumbai")
queue.append("Kolkata")
# Now display the queue after en-queueing these
print queue
# You will observe that Mumbai and Kolkata have been en-queued at the end of the queue

# Now let us start to De-que element from this queue
dequedElement1 = queue.popleft()
dequedElement2 = queue.popleft()
# Let us display the Dequeued Elements. 
# Given that a Queue is a First In First Out (FIFO) data structure the de-queued elements will be London and Paris
print "Two cities were de-queued"
print "First Dequeued city:"
print dequedElement1
print "First Dequeued city:"
print dequedElement2

# You will notice how the first two cities have been removed from the Queue, in FIFO order
print "Current state of the queue after dequeing two cities:"
print queue

Output of the Program above:


~/work/pythontutorials$ python DataStructuresQueues.py 
The Original Queue:
deque(['London', 'Paris', 'New York', 'Delhi'])
deque(['London', 'Paris', 'New York', 'Delhi', 'Mumbai', 'Kolkata'])
Two cities were de-queued
First Dequeued city:
London
First Dequeued city:
Paris
Current state of the queue after dequeing two cities:
deque(['New York', 'Delhi', 'Mumbai', 'Kolkata'])


3. Linked Lists in Python


For a detailed explanation about Linked Lists and the common operations on them, check out the tutorial here. Linked lists are linear, self referential data structures. Common operations on them are insertion, deletion, traveral/display, and finding elements.

class
Node: def __init__(self,data=None,next=None): self.data = data self.next = next def __str__(self): return "Node[Data=" + `self.data` + "]" class LinkedList: def __init__(self): self.head = None # Inserting new data at the end of the list # Iterate through the list till we encounter the last node. # A new node is created for this data element # And the last pointer points to this def insert(self,data): if (self.head == None): self.head = Node(data) else: current = self.head while (current.next != None) and (current.data == data):
                            current = current.next
			current.next = Node(data)

	# Deleting a given data value from the linked list
	# If the head contains this data value
	# Set head = node which comes next after the current head
	# Otherwise go to the node such that the node after it (next to it) contains the value we're looking for
	# set node.next = node.next.next
	# so, the node which dontains the specified value/data; is skipped
	def delete(self,data):
		current = self.head
		if current.data == data:
			self.head = current.next
		if current == None:
			return False
		else:
			while (current != None) and (current.next != None) and (current.next.data != data):	
				current = current.next
			if (current != None) and (current.next != None) :
				current.next = current.next.next

	# Find a given data value in the linked list
	# Traverse the linked list till you either find the data value or you come to the end of the list

	def find(self,data):
		found = False
		current = self.head
		while ((current != None) and (current.data != data) and ( current.next != None)):
			current = current.next
 		if current != None:
			found = True
		return found

	# Display the linked list
	# Traverse the linked list till you reach its end
	# Display each node which you traverse	
	def display(self):
		current = self.head
		string_representation = " "
		while current != None:
			string_representation +=  str(current) + "--->"
			current = current.next
		print string_representation

# Initialize a new linked list
print "Initializing linked list"
ll = LinkedList()

# Insert values in the linked list
print "Inserting values 1,2,3,9 in the Linked List"
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(9)

# Display the linked list
print "Displaying the linked list"
ll.display()

# Delete an element from the linked list. Demonstrate the Delete function
print "Delete an element (data = 3) from the linked list"
ll.delete(3)

print "Display the linked list again. The value 3 is deleted. "
ll.display()

# Try to find the value 2 in the linked list (Demonstrating the Find function)
print "Try to find the value 2 in the linked list"
found = ll.find(2)
if found == True:
	print "The value 2 is present in the Linked List"
else:
	print "The value 2 is not present in the linked list"

# Try to find the value 20 in the linked list
print "Try to find the value 20 in the linked list"
found = ll.find(20)
if found == True:
	print "The value 20 is present in the Linked List"
else:
	print "The value 20 is not present in the linked list"



Output of the Program above:


~/work/pythontutorials$ python DataStructuresLinkedLists.py 
Initializing linked list
Inserting values 1,2,3,9 in the Linked List
Displaying the linked list
 Node[Data=1]--->Node[Data=2]--->Node[Data=3]--->Node[Data=9]--->
Delete an element (data = 3) from the linked list
Display the linked list again. The value 3 is deleted. 
 Node[Data=1]--->Node[Data=2]--->Node[Data=9]--->
Try to find the value 2 in the linked list
The value 2 is present in the Linked List
Try to find the value 20 in the linked list
The value 20 is not present in the Linked List




4. Double Linked Lists in Python



class
Node: # Constructor to initialize data # If data is not given by user,its taken as None def __init__(self, data=None, next=None, prev=None): self.data = data self.next = next self.prev = prev # __str__ returns string equivalent of Object def __str__(self): return "Node[Data = %s]" % (self.data,) class DoubleLinkedList: def __init__(self): self.head = None self.tail = None def insert(self, data): if (self.head == None): # To imply that if head == None self.head = Node(data) self.tail = self.head else: current = self.head while(current.next != None): current = current.next current.next = Node(data, None, current) self.tail = current.next def delete(self, data): current = self.head # If given item is the first element of the linked list if current.data == data: self.head = current.next self.head.prev = None return True # In case the linked list is empty if current == None: return False # If the element is at the last if self.tail == data: self.tail = self.tail.prev self.tail.next = None return True # If the element is absent or in the middle of the linked list while current != None: if current.data == data : current.prev.next = current.next current.next.prev = current.prev return True current = current.next # The element is absent return False def find(self, data): current = self.head while current != None: if current.data == data : return True current = current.next return False def fwd_print(self): current = self.head if current == None: print("No elements") return False while (current!= None): print (current.data) current = current.next return True def rev_print(self): current = self.tail if (self.tail == None): print("No elements") return False while (current != None): print (current.data) current = current.prev return True # Initializing list l = DoubleLinkedList() # Inserting Values l.insert(1) l.insert(2) l.insert(3) l.insert(4) # Forward Print l.fwd_print() # Reverse Print l.rev_print() # Try to find 3 in the list if (l.find(3)): print("Found") else : print("Not found") # Delete 3 from the list l.delete(3) # Forward Print l.fwd_print() # Reverse Print l.rev_print() # Now if we find 3, we will not get it in the list if (l.find(3)): print("Found") else : print("Not found")