veer

Almost every other computer application, whether it is a web based application, a standalone data logger, a mobile app or a desktop application with or without GUI, stores and retrieves data from some persistent storage device such as hard disk or a flash drive. Such storage device may either be connected to computer or it may be available on a network. Without this ability to recurrently access, update and retrieve stored data, most computer applications would have been reduced to programmable calculators!

• Python Data Persistence – File I0
• Data Persistence – Python – PyMongo
• Python Data Persistence – RDBMS Concepts

Python Data Persistence – A Quick Guide

Data storage format depends on the logical structure of data and on the processing logic. Data may be stored in flat computer files, in tables of relational databases or different store formats of NOSQL databases. You will know more about these terms in subsequent chapters of this Page.

Back-end process of a computer application stores, modifies and retrieves data in response to front-end user’s requirements. Almost every programming language offers tools to interact with files/databases. This book aims to familiarize the reader with Python’s functions and modules that handle persistent data processing.

Python Data Persistence – Getting Started

• Python Data Persistence – Installation
• Python Data Persistence – Built-in Functions

Python Data Persistence – Program Flow Control

• Python Data Persistence – Decision Control
• Python Data Persistence – Repetition
• Python Data Persistence – while Statement
• Python Data Persistence – for Keyword
• Python Data Persistence – Using Range
• Python Data Persistence – for loop with Dictionary
• Python Data Persistence – Repetition Control
• Python Data Persistence – Nested Loops
• Python Data Persistence – List Comprehension

Python Data Persistence – Structured Python

• Python Data Persistence – Structured Python
• Python Data Persistence – Function
• Python Data Persistence – math Module
• Python Data Persistence – os module
• Python Data Persistence – User Defined Functions
• Python Data Persistence – Function with Parameters
• Python Data Persistence – return Keyword
• Python Data Persistence – Required Arguments
• Python Data Persistence – Parameter with Default Value
• Python Data Persistence – Keyword Arguments
• Python Data Persistence – User Defined Modules

Python Data Persistence Object Oriented Programming OOP

• Python Data Persistence – Class Keyword
• Python Data Persistence – Constructor
• Python Data Persistence – Getters/setters
• Python Data Persistence – property() Function
• Python Data Persistence – @property Decorator
• Python Data Persistence – Class Level Attributes and Methods
• Python Data Persistence – Inheritance
• Python Data Persistence – Overriding
• Python Data Persistence – Magic Methods

Python Data Persistence – File IO

• Python Data Persistence – Opening File
• Python Data Persistence – Writing to File
• Python Data Persistence – Reading a File
• Python Data Persistence – Write/Read Binary File
• Python Data Persistence – Simultaneous Read/Write
• Python Data Persistence – File Handling using os Module
• Python Data Persistence – File/Directory Management Functions
• Python Data Persistence – Exceptions

Python Data Persistence – Object Serialization

• Python Data Persistence – pickle Module
• Python Data Persistence – shelve Module
• Python Data Persistence – dbm Modules
• Python Data Persistence – csv module
• Python Data Persistence – json Module
• Python Data Persistence – xml Package
• Python Data Persistence – plistlib Module

Python Data Persistence – RDBMS Concepts

• Python Data Persistence – RDBMS Concepts
• Python Data Persistence – Relational Database
• Python Data Persistence – RDBMS Products
• Python Data Persistence – Constraints
• Python Data Persistence – INSERT Statement
• Python Data Persistence – SELECT Statement
• Python Data Persistence – UPDATE Statement
• Python Data Persistence – Transaction Control
• Python Data Persistence – MySQL

Python Data Persistence – Python DB-API

• Python Data Persistence – Python DB-API
• Python Data Persistence – Creating Table
• Python Data Persistence – ResultSet Object
• Python Data Persistence – User-Defined Functions
• Python Data Persistence – Row Object
• Python Data Persistence – Backup and Restore Database
• Python Data Persistence – Using pymysql Module

Python Data Persistence – Python – SQLAlchemy

• Python Data Persistence – Python – SQLAlchemy
• Python Data Persistence – SQLAlchemy ORM
• Python Data Persistence – ORM – Table Object and Mapped Class
• Python Data Persistence – ORM-Add Data
• Python Data Persistence – ORM – Querying
• Python Data Persistence – ORM – Filter criteria
• Python Data Persistence – ORM – Update Data
• Python Data Persistence – ORM – Relationships
• Python Data Persistence – Querying related tables (ORM)
• Python Data Persistence – SQLAlchemy Core
• Python Data Persistence – Core – Inserting Records
• Python Data Persistence – Core – Updating Records

Python Data Persistence – Python and Excel

• Python Data Persistence – Python and Excel
• Python Data Persistence – Creating a workbook
• Python Data Persistence – Read Data from Worksheet
• Python Data Persistence – Define Formula
• Python Data Persistence – Copy Formula
• Python Data Persistence – Charts
• Python Data Persistence – Insert Image
• Python Data Persistence – Excel with Pandas

Python Data Persistence – Python – PyMongo

• Python Data Persistence – Python – PyMongo
• Python Data Persistence – Installation of MongoDB
• Python Data Persistence – MongoDB – Querying Collection
• Python Data Persistence – MongoDB – Update Document
• Python Data Persistence – PyMongo Module
• Python Data Persistence – PyMongo – Add Collection
• Python Data Persistence – PyMongo – Querying Collection
• Python Data Persistence – PyMongo – Relationships

Python Data Persistence – Python – Cassandra

• Python Data Persistence – Python – Cassandra
• Python Data Persistence – Create Keyspace
• Python Data Persistence – Querying Cassandra Table
• Python Data Persistence – Table with Compound Partition Key
• Python Data Persistence – Python Cassandra Driver
• Python Data Persistence – Parameterized Queries
• Python Data Persistence – User-defined Types

Read Also: 

• Python Data Presistence – Identifiers
• Python Data Presistence – Statements
• Python Data Presistence – Indents
• Python Data Presistence – Data Types
• Python Data Presistence – Methods of Built-in Data Type Classes
• Python Data Presistence – Variables
• Python Data Persistence – pyodbc Module
• Python Data Persistence – Deleting Rows
• Python Data Persistance – Inserting Rows
• Python Data Persistence – Package

Why Python?

Popularity of Python has increased by many fold recently because of the emergence of powerful libraries for data analysis, visualization and machine learning. These libraries use data stored in different formats such as text files and relational databases. Hence to be a proficient data scientist, it is important to have a sound understanding of Python tools for data persistence.

Features of Python

Python is easy!: So why has Python been so popular? First and foremost, Python is very easy to learn and use. “Simple is better than Complex”. This is one of the guiding principles of Python’s design philosophy. It has clean and simple syntax resembling to a natural language. It saves a lot of development time.

Open source: Python is free and open source having a very active and supportive developer community. As a result of plenty of documentation resources, guides tutorials and forums me available in public domain. Any newcomer can access, learn, collaborate and seek advice from community.

Object oriented: Python is completely object oriented, although it supports multiple programming paradigms including functional programming style.

Extensible: Python can be easily integrated with other languages such as C/C++, Java, .NET, etc. Corporate support: Python enjoys great corporate support. Google for example promotes Python in a big way as Python is extensively used in many of its applications. Many other companies use Python as their development platform.

Prerequisites

In order to understand this stack tutorial, you’ll need to learn the Stack data structure which requires the following:

1. Python 3
2. Basic data structure concepts like List (Click here to refresh List concepts)
3. OOP concepts

What is a Stack?

Howdy! If you are reading this article, you are about to learn one of the very basic and most useful data structure concepts. If you know other languages like C or C++, implementation of stack might be tricky (since you will have to keep track of pointers!) but not with Python. Python is so amazing that you can use lists to easily implement them but you will also learn how to implement using pointers to adopt a language agnostic way. But first, let’s understand what they are. If you are already familiar with this, you can skip to the implementation section.

When you hear the word Stack, the first thing that comes to your mind may be a stack of books, and we can use this analogy to explain stacks easily! Some of the commonalities include:

1. There is a book at the top of the stack (if there is only one book in the stack, then that will be considered the topmost book).
2. Only when you remove the topmost book can you get access to the bottom ones. No Jenga games here! (Also assume that you can only lift one book at a time).
3. Once you remove all the books from the top one by one, there will be none left and hence you cannot remove any more books.

Check out this fun game called Towers of Hanoi which beautifully demonstrates how a Stack works. Read the instructions carefully and turn off the music (it is awfully loud!).

To describe the above points programmatically:

1. Keep track of the topmost element as this will give you the information about the number of elements in the stack and whether the stack is empty/full (if the stack is empty then top will be set to 0 or a negative number)
2. The last element to enter the stack will always be the first to leave (Last In First Out – LIFO)
3. If all the elements are removed, then the stack is empty and if you try to remove elements from an empty stack, a warning or an error message is thrown.
4. If the stack has reached its maximum limit and you try to add more elements, a warning or error message is thrown.

Things to remember:

1. The entry and exit of elements happens only from one end of the stack (top)
2. Push – Adding an element to the Stack
3. Pop – Removing an element from the Stack
4. Random access is not allowed – you cannot add or remove an element from the middle.

Note: Always keep track of the Top. This tells us the status of the stack.

• Stack Data Structure in Python
• Problem Solving and Programming In C Notes and Study Material PDF Free Download
• Python Programs for Class 12 | Python Practical Programs for Class 12 Computer Science

How to implement Stack?

Now that you know what a Stack is, let’s get started with the implementation!

Stack implementation using List

Here we are going to define a class Stack and add methods to perform the below operations:

1. Push elements into a Stack
2. Pop elements from a Stack and issue a warning if it’s empty
3. Get the size of the Stack
4. Print all the elements of the Stack

class Stack:

    #Constructor creates a list
    def __init__(self):
        self.stack = list()

    #Adding elements to stack
    def push(self,data):
        #Checking to avoid duplicate entries
        if data not in self.stack:
            self.stack.append(data)
            return True
        return False

    #Removing last element from the stack
    def pop(self):
        if len(self.stack)<=0:
            return ("Stack Empty!")
        return self.stack.pop()
        
    #Getting the size of the stack
    def size(self):
        return len(self.stack)

myStack = Stack()
print(myStack.push(5)) #prints True
print(myStack.push(6)) #prints True
print(myStack.push(9)) #prints True
print(myStack.push(5)) #prints False since 5 is there
print(myStack.push(3)) #prints True
print(myStack.size())  #prints 4 
print(myStack.pop())   #prints 3
print(myStack.pop())   #prints 9
print(myStack.pop())   #prints 6
print(myStack.pop())   #prints 5
print(myStack.size())  #prints 0
print(myStack.pop())   #prints Stack Empty!

NOTE: We are not worried about the size of the stack since it is represented by a list which can dynamically change its size.

Stack implementation using Array

Python Lists have made it so easy to implement Stack. However, if you want to implement Stack language agnostically, you have to assume that lists are like arrays (fixed in size) and use a Top pointer to keep a tab on the status of the stack. Check this animation to understand how it works.

Algorithm

1. Declare a list and an integer MaxSize, denoting the maximum size of the Stack
2. Top is initially set to 0
3. Push operation:
   1. Check if Top is less than the MaxSize of the Stack
      1. If yes, append data to stack and increment top by 1
      2. If no, print stack full message
4. Pop operation:
   1. Check if Top is greater than 0:
      1. If yes, pop the last element from the list and decrement top by 1
      2. If no, print stack empty message
5. Size operation:
   1. The value of the Top pointer is the size of the Stack

Program

class Stack:
    
    #Constructor 
    def __init__(self):
        self.stack = list()
        self.maxSize = 8
        self.top = 0
    
    #Adds element to the Stack
    def push(self,data):
        if self.top>=self.maxSize:
            return ("Stack Full!")
        self.stack.append(data)
        self.top += 1
        return True
        
    #Removes element from the stack
    def pop(self):
        if self.top<=0:
            return ("Stack Empty!")
        item = self.stack.pop()
        self.top -= 1
        return item
        
    #Size of the stack
    def size(self):
        return self.top

s = Stack()
print(s.push(1))#prints True
print(s.push(2))#prints True
print(s.push(3))#prints True
print(s.push(4))#prints True
print(s.push(5))#prints True
print(s.push(6))#prints True
print(s.push(7))#prints True
print(s.push(8))#prints True
print(s.push(9))#prints Stack Full!
print(s.size())#prints 8        
print(s.pop())#prints 8
print(s.pop())#prints 7
print(s.pop())#prints 6
print(s.pop())#prints 5
print(s.pop())#prints 4
print(s.pop())#prints 3
print(s.pop())#prints 2
print(s.pop())#prints 1
print(s.pop())#prints Stack Empty!

Note: Element 9 was not added and hence size remains 8.

Apart from the methods described above, you can add methods to return the top element, check if the stack is empty etc.

Conclusion

One of the main application of Stacks is in recursion. Be sure to check this tutorial to know what recursion is.  Once you are familiar with this concept, try to solve these puzzles using recursion – sentence reversal and balancing brackets. Happy Pythoning!

Prerequisites

To learn about the Queue data structure, you should first have a good understanding of the following:

1. Python 3
2. Basic data structure concepts like List (Click here to refresh List concepts)
3. OOP concepts

Introduction

This tutorial will help you understand a Queue data structure and how to implement it. These concepts are often tested in interviews and have a wide variety of applications. Python implementation of Queue is relatively simple when compared to other languages. Here you will learn how to do it in the Pythonic way and in a language-agnostic way.

• Stack Data Structure in Python
• Data Structures Lecture Notes PDF | DS Lecture Notes & Study Material PDF Free Download
• Advanced Data Structures and Algorithms Notes and Study Material PDF Free Download

How to use Queue

A Queue is a simple data structure concept that can be easily applied in our day-to-day life, like when you stand in a line to buy coffee at Starbucks. Let’s make a few observations based on this example:

1. People enter the line from one end and leave at the other end
2. The person to arrive first leaves first and the person to arrive last leaves last
3. Once all the people are served, there are none left waiting to leave the line

Now, let’s look at the above points programmatically:

1. Queues are open from both ends meaning elements are added from the back and removed from the front
2. The element to be added first is removed first (First In First Out – FIFO)
3. If all the elements are removed, then the queue is empty and if you try to remove elements from an empty queue, a warning or an error message is thrown.
4. If the queue is full and you add more elements to the queue, a warning or error message must be thrown.

Things to remember:

1. The point of entry and exit are different in a Queue.
2. Enqueue – Adding an element to a Queue
3. Dequeue – Removing an element from a Queue
4. Random access is not allowed – you cannot add or remove an element from the middle.

Implementation

We are going to see three different implementations. One is using Lists, another is using the library deque and the last is by using an array. Let’s take a look one by one…

1. Queue implementation using List

Here we are going to define a class Queue and add methods to perform the below operations:

1. Enqueue elements to the beginning of the Queue and issue a warning if it’s full
2. Dequeue elements from the end of the Queue and issue a warning if it’s empty
3. Assess the size of the Queue
4. Print all the elements of the Queue

class Queue:

  #Constructor creates a list
  def __init__(self):
      self.queue = list()

  #Adding elements to queue
  def enqueue(self,data):
      #Checking to avoid duplicate entry (not mandatory)
      if data not in self.queue:
          self.queue.insert(0,data)
          return True
      return False

  #Removing the last element from the queue
  def dequeue(self):
      if len(self.queue)>0:
          return self.queue.pop()
      return ("Queue Empty!")

  #Getting the size of the queue
  def size(self):
      return len(self.queue)

  #printing the elements of the queue
  def printQueue(self):
      return self.queue

myQueue = Queue()
print(myQueue.enqueue(5)) #prints True
print(myQueue.enqueue(6)) #prints True
print(myQueue.enqueue(9)) #prints True
print(myQueue.enqueue(5)) #prints False
print(myQueue.enqueue(3)) #prints True
print(myQueue.size())     #prints 4
print(myQueue.dequeue())  #prints 5
print(myQueue.dequeue())  #prints 6
print(myQueue.dequeue())  #prints 9
print(myQueue.dequeue())  #prints 3
print(myQueue.size())     #prints 0
print(myQueue.dequeue())  #prints Queue Empty!

Call the method printQueue() wherever necessary to ensure that it’s working.

Note: You will notice that we are not removing elements from the beginning and adding elements at the end. The reason for this is covered in the ‘implementation using arrays’ section below.

2. Queue implementation using deque

Deque is a library which, when imported, provides ready-made commands such as the append() command for enqueuing and the popleft() command for dequeuing.

#Importing the library
from collections import deque

#Creating a Queue
queue = deque([1,5,8,9])

#Enqueuing elements to the Queue
queue.append(7) #[1,5,8,9,7]
queue.append(0) #[1,5,8,9,7,0]

#Dequeuing elements from the Queue
queue.popleft() #[5,8,9,7,0]
queue.popleft() #[8,7,9,0]

#Printing the elements of the Queue
print(queue)

Try using the popleft() command after the queue is empty and see what you get. Post the ways in which you can handle this issue.

NOTE: Implementation 2 is more efficient as the insert operation in the list is costly! This is because whenever an element is inserted at position 0, all of the other elements have to be shifted by one position (it is similar to when people sitting on a bench push down to accommodate another person). We will discuss the efficiency of operations in detail in later tutorials.

3. Queue implementation using array

Python Lists have made it so easy to implement Queue. However, if you want to implement Queues language agnostically, you have to bear in mind the following points:

1. Elements are added from the end and removed at the beginning of the Queue.
2. Treat lists like arrays (fixed in size) – we can achieve it by virtually restricting the size of the list. This is done by ensuring that the list doesn’t grow beyond a fixed limit or size.
3. Use a Tail pointer to keep a tab of the elements added to the Queue – the Tail pointer will always point to the next available space. For instance when there are three elements in the queue, Tail will point to the fourth place. When the queue is full, the tail pointer will be greater than the declared size.
4. Use a Head pointer to keep a tab on the elements removed from the Queue – the Head pointer will point to the element to be dequeued next. For instance, if there are three elements in a queue, the Head pointer will be pointing to the first element. After one dequeue operation, the Head pointer will point to the second element in the queue. No element will be actually removed from the queue. This is because once an element is removed, the list automatically shifts all the other elements by one position to the left. This means that the position 0 will always contain an element, which is not how an actual queue works.
5. Use a Reset method – this method is called to reset the queue, Tail and Head. For instance, if there are three elements in the queue then Head = 0, Tail = 4. Now, if we dequeue all three elements, the queue will be empty meaning Head = Tail = 4. So if you enqueue an element, it will happen at position 4 which is not correct. Hence it becomes necessary to reset these pointers to 0. Note that since we are not actually deleting elements, the list still contains the ‘deleted” elements, hence a new list needs to be created as well.

Algorithm

1. Declare a list and an integer MaxSize, denoting a virtual maximum size of the Queue
2. Head and Tail are initially set to 0
3. Size method
   1.  Calculates the number of elements in the queue -> Size = Tail – Head
4. Reset method:
   1. Resets Tail and Head to 0
   2. Creates a new Queue (initializes queue to a new list)
5. Enqueue operation:
   1. Check if Size is less than the MaxSize:
      1. If yes, append data to Queue and then increment Tail by 1
      2. If no, print Queue full message
6. Dequeue operation:
   1. Check if Size is greater than 0:
      1. If yes, pop the first element from the list and increment Head by 1
      2. If no:
         1. Call Reset method
         2. Print Queue empty message

Program

class Queue:

    #Constructor
    def __init__(self):
        self.queue = list()
        self.maxSize = 8
        self.head = 0
        self.tail = 0

    #Adding elements
    def enqueue(self,data):
        #Checking if the queue is full
        if self.size() >= self.maxSize:
            return ("Queue Full")
        self.queue.append(data)
        self.tail += 1
        return True     

    #Deleting elements 
    def dequeue(self):
        #Checking if the queue is empty
        if self.size() <= 0:
            self.resetQueue()
            return ("Queue Empty") 
        data = self.queue[self.head]
        self.head+=1
        return data
                
    #Calculate size
    def size(self):
        return self.tail - self.head
    
    #Reset queue
    def resetQueue(self):
        self.tail = 0
        self.head = 0
        self.queue = list()
    
q = Queue()
print(q.enqueue(1))#prints True
print(q.enqueue(2))#prints True
print(q.enqueue(3))#prints True
print(q.enqueue(4))#prints True
print(q.enqueue(5))#prints True
print(q.enqueue(6))#prints True
print(q.enqueue(7))#prints True
print(q.enqueue(8))#prints True
print(q.enqueue(9))#prints Queue Full!
print(q.size())#prints 8        
print(q.dequeue())#prints 8
print(q.dequeue())#prints 7 
print(q.dequeue())#prints 6
print(q.dequeue())#prints 5
print(q.dequeue())#prints 4
print(q.dequeue())#prints 3
print(q.dequeue())#prints 2
print(q.dequeue())#prints 1
print(q.dequeue())#prints Queue Empty
#Queue is reset here 
print(q.enqueue(1))#prints True
print(q.enqueue(2))#prints True
print(q.enqueue(3))#prints True
print(q.enqueue(4))#prints True

Note: Element 9 was not added to the Queue and hence the size of the Queue remains 8

Apart from the methods described above, you can add methods which could return the element at the start of the queue, check if the queue is empty etc.

Conclusion

That’s it for this tutorial. Be sure to learn the applications of Queue. Plus, stay tuned with us here on PythonCentral to learn more about other types of Queues like Circular Queue and Priority Queue. Happy Pythoning!

Prerequisites

To learn about Circular Queue, you should first have a good understanding of the following:

1. Python 3
2. Linear Queues (you can learn more here)
3. Basic Python data structure concepts – lists
4. Basic math operations – modulo(%)

What is a Circular Queue?

Before you go ahead and read this tutorial, I highly recommend you to read our previous tutorial on Queues as we will be building off of those concepts. Circular Queues are widely used and are often tested on job interviews. A Circular Queue can be seen as an improvement over the Linear Queue because:

1. There is no need to reset Head and Tail pointers since they reset themselves. This means that once the Head or Tail reaches the end of the Queue, it resets itself to 0.
2. The Tail and Head can point to the same location – this means the Queue is empty
3. The Head can be greater than the Tail or vice-versa. This is possible because the Head and Tail pointers are allowed to cross each other.

Check out this animation to understand the circular queue a bit better.

Observations based on the above animation:

1. Head pointer – Points to the front of the Queue. Or in other words, it points to the element to be removed if the dequeue operation is called.
2. Tail pointer – Points to the next empty spot in which the new element can be inserted. In the above animation, if you tried to fill the queue completely you wouldn’t be able to enqueue after the 13th position. This is because the Tail has no empty spot to point to after an element is inserted in the 14th position. The queue is considered full, even though there is one empty spot left. You should also try doing three or four dequeue operations and then enqueueing an element. Here you will observe that the elements are inserted from the 14th position and then it restarts from 0. It is for this reason that it is called a circular queue.
3. Number of elements:
   1. Tail>=Head: Number of elements = Tail – Head. For instance, if Head = 2 and Tail = 5, then the number of elements will be 5 – 2 = 3
   2. Head>Tail: Number of elements = (Size of Queue) – (Head-Tail) =  (Size of Queue) – Head + Tail. For instance, Head = 14, Tail = 5 and Size of Queue = 15, then the number of elements = 15 – (14 – 5) = 6

How to implement circular queue?

I hope you now feel confident that you know what a circular queue is. Let’s see how to implement it using the language agnostic method. To do this, we need to treat Lists like arrays, hence we will restrict its size.

Note: During a dequeue operation, the Head pointer will be incremented by 1 but no element will actually be removed from the queue. This is because once an element is removed, the list automatically shifts all the other elements by one position to the left. This means that the position 0 will always contain an element which is not how an actual queue/circular queue works.

• How to use Queue: A beginner’s guide
• Priority Queue: A Beginner’s Guide
• Stack Data Structure in Python

Algorithm

The following steps can be seen as a flow chart to the operation of the Circular Queue:

1. Initialize the queue, size of the queue (maxSize), head and tail pointers
2. Enqueue:
   1. Check if the number of elements (size) is equal to the size of the queue (maxSize):
      1. If yes, throw error message “Queue Full!”
      2. If no, append the new element and increment the tail pointer
3. Dequeue:
   1. Check if the number of elements (size) is equal to 0:
      1. If yes, throw error message “Queue Empty!”
      2. If no, increment head pointer
4. Size:
   1. If tail>=head, size = tail – head
   2. if head>tail, size = maxSize – (head – tail)

Note: The range for the head and tail pointer should be between 0 and maxSize – 1,  hence we are using the logic that if we divide x by 5, then the remainder can never be greater than 5. In other words, it should be between 0 and 4. So apply this logic to the formulae tail = (tail+1)%maxSize and head = (head+1)%maxSize. Observe that this is helps us to avoid reinitializing tail and head to 0 when the queue becomes full.

Program

class CircularQueue:

    #Constructor
    def __init__(self):
        self.queue = list()
        self.head = 0
        self.tail = 0
        self.maxSize = 8

    #Adding elements to the queue
    def enqueue(self,data):
        if self.size() == self.maxSize-1:
            return ("Queue Full!")
        self.queue.append(data)
        self.tail = (self.tail + 1) % self.maxSize
        return True

    #Removing elements from the queue
    def dequeue(self):
        if self.size()==0:
            return ("Queue Empty!") 
        data = self.queue[self.head]
        self.head = (self.head + 1) % self.maxSize
        return data

    #Calculating the size of the queue
    def size(self):
        if self.tail>=self.head:
            return (self.tail-self.head)
        return (self.maxSize - (self.head-self.tail))

q = CircularQueue()
print(q.enqueue(1))
print(q.enqueue(2))
print(q.enqueue(3))
print(q.enqueue(4))
print(q.enqueue(5))
print(q.enqueue(6))
print(q.enqueue(7))
print(q.enqueue(8))
print(q.enqueue(9))
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

Application

There are several uses for Circular Queues, such as:

1. Computer Architecture (Scheduler)
2. Disk drivers
3. Video buffering
4. Printer job scheduling

Conclusion

Circular Queue may appear a little confusing at first but the only way to get the hang of it is to keep practicing. Try out different enqueue and dequeue operations in the animation link provided above to see how it works. That’s it for this tutorial. Happy Pythoning!

Prerequisites

To learn about Linear and Binary search, you’ll need to have a good understanding of:

1. Python 3
2. Basic Python data structure concepts – lists

Introduction

Often we will have to find an element from a given data structure like lists, linked lists or binary trees. An efficient searching technique saves a great amount of time and improves performance. In this tutorial, we are going to see two very commonly used searching algorithms.

Linear Search

So if you were to search “Harry Potter”, from a shelf in a poorly lit room how would you go about it? You would start at one end, take one book at a time and check if it’s Harry Potter or not. You will use a brute force methodology which checks every book until the Harry Potter is found or the end of the shelf is reached. Best case scenario would be when Harry Potter is the first book and worst case would be the book not in there at all. Either way, you can know this only by checking each and every book. This is exactly what Linear Search is.

Binary Search

What if you were to search for Harry Potter from a shelf of books which are ordered alphabetically? Would you start searching from the start? Definitely not! You would start somewhere near the middle and check the first letter of the books and then go back or forward from there to find the ‘H’ titles. This means that you won’t be looking at all the books, thus saving time. You also won’t need to go through the entire shelf to know whether the book is there or not. At a given point you are eliminating many books which you will never look at. Binary Search is similar to this.

NOTE: Linear Search can be done on both sorted and unsorted items but Binary Search can only be done on a sorted set of items.

• Binary Search Algorithm in Python
• Python Program to Implement Fibonacci Search
• Implementing Sentinel Search in Python

Implementation

Now that you know what Linear and Binary Search methodologies are, let us look at how these searches would work on a list of numbers.

Linear Search

Given list A = [6,3,9,0,5,8,2] find if 0 is present in this list or not.

Algorithm

1. Take one number at a time from list A
2. Compare it with 0 and check if it is a match:
   1. If yes, return True
   2. If not, return False
3. If the end of the list is met, return False

Code

def linearSearch(ls,data):

   for item in ls:
       if item == data:
           return True
   return False

print(linearSearch([6,3,9,5,8,2],0))

Binary Search

The idea is to keep comparing the element with the middle value. This way with each search we eliminate one half of the list.

Algorithm

1. Keep track of two pointers First and Last, these are incremented or decremented to limit the part of the list to be searched.
2. Find the middle element of the list: mid = ( length of the list )/2
3. Compare the middle element with the value to be found
4. Check if the middle element is lesser than the value to be found:
   1. If yes, the element must lie on the second half of the list
   2. If no, the element must lie on the first half of the list
5. Repeat steps 1 through 3 until the element is found or the end of the list is reached

NOTE: The list continues to get divided into two and the middle element gets compared until the element is found or no more elements are left to compare with.

Code

Given list B = [2,5,7,8,9,11,14,16] find if 14 is present in this list or not.

def binarySearch(ls,data):
   first = 0
   last = len(ls)-1
   done = False   

    while first<=last and not done:
       mid = (first+last)//2
          if ls[mid] == data:
           done = True
       else:
           if ls[mid] > data:
               last = last-1
           else:
               first = first+1
   return done 

print(binarySearch([2,5,7,8,9,11,14,16],4))

NOTE: To find the mid element, “(first+last)//2” is used instead of “(first+last)/2”. This gives us whole numbers especially when the length of the list is odd. Try 9/2 and 9//2 in your Python IDLE to get a better understanding.

Try out this animation for a better understanding of both these search algorithms. Try to find the first element of the array. Which is faster?

Conclusion

From the above explanation, it must be clear that Binary Search is consistently faster than Linear Search. If you are familiar with o(n) notation, Linear Search is o(n) and Binary Search is log(n)

You can perform Linear Searches on a sorted list as well with a small optimization. You can stop the search once the number to be found exceeds the element being compared to. For instance, you want to search for 12 from the list [2,4,5,13,16,19], once you reach 13 you can stop because there is no way that 12 is going to come after 13 in a sorted list.

In this tutorial, we have discussed only the iterative method of Binary Search. Try to implement the recursive approach on your own.  Also, learn about the uses of these searches and when to apply them. That’s all for this tutorial. Happy Pythoning!

Prerequisites

To learn about Priority Queue, you must know:

1. Python 3
2. Linear Queue
3. Basic Python data structure concepts – lists, tuples

What is a priority queue?

Before you go ahead and read this tutorial, I highly recommend you to read the previous tutorial on Queues and Circular Queues as it will give you a better foundation and help you grasp the the content here.

What would you do if you wanted to track the least played songs in your playlist? The easiest solution would be to sort the list but that is time-consuming and wasteful. You only have to keep track of the song with the least hits. A min heap or priority queue helps you do this.

Priority Queues, also known as heap queues, are abstract data structures. Heaps are binary trees where every parent node has a value less than or equal to any of its children. In other words, this type of queue keeps track of the minimum value. Thus it helps retrieve the minimum value at all times. For this reason, it is also referred to as min heap. Thus, position 0 holds the smallest/minimum value. There is also a max heap whose operation is quite similar.

Note: heap queues or priority queues don’t sort lists in ascending order. It just keeps the smallest element in its 0th position. The rest of the elements may or may not be sorted.

• Data Structures Lecture Notes PDF | DS Lecture Notes & Study Material PDF Free Download
• Stack Data Structure in Python
• Data Structure through C++ Lecture Notes | Syllabus, Reference Books and Important Questions

How To Implement Priority Queue

To use priority queue, you will have to import the heapq library. This is done as follows:

import heapq

The following heap commands can be performed once the heapq module is imported:

1. heapify() – this operation enables you to convert a regular list to a heap. On performing this operation, the smallest element gets pushed to position 0.

h = [5,2,6,8,0,1,2,4]
heapq.heapify(h) #returns [0, 2, 1, 4, 5, 6, 2, 8]

Note: Only the first element is in its correct sorted position.

1. heapq.heappush(heap, item) – this operation pushes an element into a heap. Heap refers to the name of the heap and item refers to the item to be added to the heap. For instance:

heapq.heappush(h,7)
print(h) #[0, 2, 1, 4, 5, 6, 2, 8, 7]

Try adding a negative number and observe what happens.

1. heapq.heappop(heap) – this operation is used to return the smallest element in the heap. Heap refers to the name of the heap.

heapq.heappop(h) #returns 0

1. heapq.heappushpop(heap, item) – as the name suggests this command adds an item to the heap and returns the smallest number. This single command is much more efficient than a heappush() command followed by heappop() command.

heapq.heappushpop(h,3) #returns 0
print(h) #prints [1, 2, 2, 4, 5, 6, 3, 8, 7]

If you try the above command with a number smaller than the min value of heap, you will notice that the same element gets popped. For instance:

heapq.heappushpop(h,0) #returns 0 print(h) #prints [1, 2, 2, 4, 5, 6, 3, 8, 7]

1. heapq.heapreplace(heap, item) -the above issue can be solved by executing this operation as it returns the smallest element and then adds the new element.

heapq.heapreplace(h,0) #returns 1
print(h) #prints [0, 2, 2, 4, 5, 6, 3, 8, 7]

The above-mentioned commands are the main ones you will use when dealing with heaps but there are also other general commands like merge(), nlargest() and nsmallest(). You can explore these on your own!

Applications

Priority Queues are widely used in different fields such as Artificial Intelligence, Statistics, Operating systems and in graphs.

Conclusion

Try solving the music player problem discussed in the introduction. You will need to heapify a list of tuples where each tuple should look like (number of hits, songid, name of the song). The heapify command will track the min according to the first element of the tuple which is why the first element of the tuple is the number of hits. Post your answers below. That’s it for this tutorial. Happy Pythoning!

Getting started with Python

If you are new to Python, chances are that you will find this post quite useful. Here you will learn about some common Python starter tips and tricks that will enable you to write simple and efficient code.

Python version 3.5.2 was used to create this tutorial.

List initialization

Lists are one of the most frequently used data structures in Python. If you have declared lists in the past, you would have done something like this:

alist = list()

              (or) 

            alist = []

If you want to initialize alist to five 0s, you would have done this:

alist = [0,0,0,0,0]

The above mentioned way works well enough for short lists, but what if you wanted to initialize a list to twenty 0s? Typing 0 twenty times would not be an efficient way. So instead, you can write something like this:

alist = [0] * 20

print(alist)

Output: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

• Python Project Ideas & Topics for Beginners to Try in 2021 | Interesting Python Projects List for Beginners, Intermediate, Advanced Level Students
• Python Program for Multiplication of Two Matrices | How do you do Matrix Multiplication in Python?
• Python Program to Iterate Through Two Lists in Parallel

Randint Command

Often you will be required to generate random numbers. Python has made this very easy by introducing the randint command. This command selects a number at random from the range you specify, making the process quick and simple. Randint needs to be imported from the ‘random’ library, which can be done like this:

from random import randint

The syntax for using randint is:

randint(<from_range>,<to_range>)

As an example, if you want to print random integers between 0 and 9 (both inclusive), it would be done like this:

from random import randint 

print(randint(0, 9))

Output: prints an integer between 0 and 9

Note that every time you execute the above command, you will get a different integer between 0 and 9.

Type Command

When you receive inputs from users or process inputs from other programs, it’s very useful to know the datatype of the input that you are dealing with. This gives you better control over the operations that you can perform. The type command identifies the datatype of a variable.

The syntax looks like this:

type(<variable_name>)

For instance, if you have a variable named alist which is a list, then executing the below command would return:

alist = list()

type(alist)

Output: <class 'list'>

Strip Command

This is a very useful command that formats inputs that are received in the form of strings. The strip command removes the spaces that are present before and after a string. The syntax is:

<string>.strip()

For example, if you want to strip spaces before and after in a string, it should be done like this:

sample = “   Python “

sample.strip()

Output: Python

Note: only spaces before and after are removed and not the spaces in between two words. For example:

sample = “      I love Python       “

sample.strip()

Output: “I love Python”

There are many more operations that can be performed using lstrip/rstrip commands like stripping on the left/right side of the string respectively. Be sure to explore further on your own!

Counting 

I am sure you will be familiar with counting forward using the for keyword, which looks like this:

for i in range(0,5):

print(i)

Output: prints 0,1,2,3,4

However, there is more to the for keyword. It also enables you to count in steps and even in reverse. The syntax is as follows:

for i in range (<from_value>,<to_value>,<step>):

print(i)

For example, if you want to count every second number between 0 and 10, it should be written as follows:

for i in range(0,10,2):

print(i)

Output: prints 0,2,4,6,8

The above command will print 0,2,4,6,8. Note that if the step is not specified, it is taken to be 1 by default.

To count in reverse, the command is as follows:

for i in range(10,0,-1):

print(i)

Output: prints 10,9,8,7,6,5,4,3,2,1

If the step is specified as -2, then the above command would print 10,8,6,4,2.

General Tips

A few other general tips:

• Comment – write comments wherever possible as this will help you and others to understand the code better. Single line comments can be written as follows:

#<Single line comment>

Paragraph comments can be written as below:

“”” 

<Paragraph comment>

“””

• Naming conventions – Take extra care in using relevant names while naming variables. Specifying the datatype in the name will be extra helpful when someone else reads your code. If you are initializing a string called “first name”, be sure to include the data type in the name like “strFirstName”. This way anyone reading your code will immediately understand that the variable “strFirstName” is of the type string.
• Line number – If you are using Python IDLE, be sure to use the ALT+G command to get to a particular line. This helps in tracking a line based on line number and can be a lifesaver when you have several lines of code and an error is thrown.

Conclusion

These are a few handpicked tips from Python and hopefully these make coding a little easier for you. There is so much more to learn as Python has an ocean of libraries that make coding extremely simple. So keep exploring and happy Pythoning!

Prerequisites

To learn about in place list reversal, you should know the following:

1. Python 3
2. Python data structures – Lists
3. Swapping values

What is in place list reversal?

In the previous posts, you might have learned how to read a list in reverse in Python which is quite fun. You can check this out here. However, the motive of this tutorial is quite different. We are not going to read a list in reverse but we are going to change an existing list to its reversed self. Note that this is a language agnostic approach.

Let’s look at an example:

alist = [1,2,3,4,5,6,7]

print(alist[::-1]) #prints [7,6,5,4,3,2,1]

print(alist) #prints [1,2,3,4,5,6,7]

So you are merely reading alist in the reverse order when you do alist[::-1]. What we want to achieve is to make alist = [7,6,5,4,3,2,1].

How to implement this?

The idea behind this is to use two pointers, left and right. The left pointer points to the first index of the list and the right pointer points to the last index of the list. Now we swap the elements pointed to by these pointers. Then, we move the pointer to the next indices. The terminating condition of this would be when the left pointer equals or crosses over the right pointer. Let us see this using an example:

As you can see, now the list is reversed.

Algorithm

1. left pointer points to the first index and right pointer points to the last index
2. Swap elements pointed by the left and right pointers respectively
3. Increment the left pointer by 1 and decrement the right pointer by 1
4. Check if left>= right:
   1. If no, repeat steps 2-4
   2. If yes, stop. The list reversal is complete

Note: Although this algorithm is explained for lists, you can use this on strings as well. In that case, you might have to convert the string to a list by typecasting it. Do not forget to reconstruct the string back from the list format. This can be done by using some of the formatting commands like replace().

Code

def reverse(alist):

   #intializing pointers
   left = 0
   right = len(alist)-1

   #condition for termination
   while left<right:

       #swapping
       temp = alist[left]
       alist[left] = alist[right]
       alist[right] = temp

       #updating pointers
       left += 1
       right -= 1

   return alist

print(reverse([1,2,3,4,5]))

• Python Programs for Beginners | Basic to Advanced Python Practice Programs for Beginners
• what is the string in python
• Python Starter Tips: Beginner’s Guide to Writing Simple and Effective Code

Efficiency

You might think that instead of going through all this trouble, you can create a new list with reversed contents. Something like this:

alist = [1,2,3,4,5,6,7]
blist = list()
for item in alist[::-1]:
blist.append(item)
print(blist) #prints [7,6,5,4,3,2,1]

Although the above approach works, you are using additional memory (blist) to store the reversed list. This might be a serious concern if the number of elements in the list is large. That is when the in place reversal will come in handy. The efficiency of in place reversal is O(n) since we visit all the elements of the list at least once.

Conclusion

This is a very commonly asked interview question. Try using the same approach to solve these puzzles and comment below:

1. Reverse the string “hello”. Output should be “olleh”
2. Reverse the sentence “I love Python Central”. Output should be “Central Python love I”
3. Check if “madam” is a palindrome or not

We will use this concept in future tutorials like linked list reversal. That’s it for this tutorial. Happy Pythoning!