What Will I Learn?
- Create a queue in python language.
- Add items to the queue.
- Extract items from the queue.
Requirements
- PC (Laptop or Desktop)
- Python 3.6
Difficulty
- Intermediate
Tutorial Contents
- Abstract Data Type
An abstract data type (ADT), specifies a set of operations (or methods) and the semantics of operations (what they do), but does not specify the implementation of the operations. This is what makes it abstract. Why is this helpful? It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time how the operations are performed. Since there are usually many ways to implement a ADT, it may be useful to write an algorithm that can be used with any of the possible implementations. Well-known ADT, such as the ADT Queue, are already implemented in standard libraries for python, so they can be written once and used by many programmers. ADT operations provide a common high-level language for specifying and talking about algorithms.
- Queue
A common ADT is a queue. A ADT queue models this behavior: The first one that arrives is the first to be attended, the others are glued until their turn comes. Think of the queue you get every time you go to the grocery store. In order for you to be attended, all the people in front of you in the queue must be attended or given up so that you can be attended. So the last in the queue is last to exit.
Its operations are:
init: Initializes a new empty queue.
insert: Adds a new element to the end of the queue.
remove: Remove the first one from the queue and return it.
isEmpty: Returns True or false depending on whether the queue is empty or not.
Sometimes is called a "first in, first out" or FIFO data structure because the first item added is the first to be removed.
See below for an illustration of how a queue works. In the first item of illustration (1), we have a queue composed of 5 elements, which were inserted chronologically in the following order: p0, p1, p2, p3, and finally p4. The second part of illustration (2) shows the state of the queue q after insertion of a new element (p5). The third part (3) shows the queue after removal of an element. As you can see, the removed element was the first one to be inserted (p5). In the latter part of the illustration (4), a further removal of element from the queue is shown, this time p1. If there were more removal operations, we would have to remove, in order, the elements: p2, p3, p4 and p5.
________|----p5----|
|----p4----| |----p4----| |----p5----|
|----p3----| |----p3----| |----p4----| |----p5----|
|----p2----| |----p2----| |----p3----| |----p4----|
|----p1----| |----p1----| |----p2----| |----p3----|
|----p0----| |----p0----| |----p1----| |----p2----|
queue q--q.insert(p5)--q.remove()--q.remove()
(1) _______ (2) _______ (3)________(4)
- Implementation
For the implementation of queues we can use a list as structure for data storage. Just now define how the operation will work.
This code is called an implementation of the ADT Queue. Generally, an implementation is a set of methods that satisfy the syntactic and semantic requirements of an interface.
Here is an implementation of ADT Queue that uses a Python list:
We will define a class queue with an attribute, items, of a type list, that will contain the elements of the queue. The first one in the queue will be in the first position of the list, and each time you add a new element, it will be added to the end.
- Creating a Queue
init: A Queue object contains an attribute called items that is a list of items in the queue. The init method will not receive additional parameters, since you must create an empty queue (which we will represent by an empty list).
def __init__(self) :
self.items = [] # Create an empty queue
- Adding elements
Insert: To add a new item to the queue, the method “insert” will be implemented. The method append() appends a passed object into the existing list. This method will be implemented by adding the new element to the end of the list.
def __init__(self) :
self.items = [] # Create an empty queue
- Adding elements
Insert: To add a new item to the queue, the method “insert” will be implemented. The method append() appends a passed object into the existing list. This method will be implemented by adding the new element to the end of the list.
def insert(self, item) :
self.items.append(item) # Insert the item as the last one of the queue
- Extracting elements
This function extracts an element from the queue. To implement the remove method, the first element in the list will be removed and the value of the removed element will be returned, we will use the pop method. We will pass it to position 0, so that it removes the first element. If the queue is empty, an exception will be raised.
def remove(self) :
try: #Removes the 1st element of the queue and returns this value
return self.items.pop(0)
except: #If the queue is empty an exception will be raised
raise ValueError ('' The Queue is empty'')
Finally, the method isEmpty will indicate whether the queue is empty or not.
def isEmpty(self) :
return (self.items == []) #Returns true if the queue is empty or false if is not empty
Now let's show how the queue works.
- Work Results
Example 1:
First, let’s create a queue with 4 numbers. First we use the queue() function, that is the method that will call the class queue functions and save the result into a queue data type variable. Then we add the elements with the q.insert() function.
Code of the main function:
q=queue() #Create and initialize the queue methods
q.insert(10) #Insert the item '10' into the queue
q.insert(20) #Insert the item '20' into the queue
q.insert(30) #Insert the item '30' into the queue
q.insert(10) #Insert the item '10' into the queue
print (“the queue is”)
print (q.items) #Print the queue
the final result is as follows:
Example 2:
Let’s repeat the first example but now we are going to remove two elements from the list, following the queue behavior (FIFO).
Code of the main function:
q=queue() #Create and initialize the stack methods
q.insert(10) #Insert the item ’10’ in to the queue
q.insert(20) #Insert the item ’20’ in to the queue
q.insert(30) #Insert the item ’30’ in to the queue
q.insert(10) #Insert the item ’10’ in to the queue
print ("removing", q.remove()) #Remove element
print ("removing", q.remove()) #Remove element
print ("The queue is", q.items)
the final result for this test is as follows:
As we can see, the first two elements that were added in the queue were removed. First the element 10 and then eh element 20. The first one that enters is the first one that comes out.
Example 3:
Another fundamental operation is the method that returns a boolean indicating whether the queue is empty.
Code of the main function:
q=queue() #Create and initialize the queue methods
q.insert(10) #Insert the item ’10’ in to the queue
q.insert(20) #Insert the item ’20’ in to the queue
q.insert(30) #Insert the item ’30’ in to the queue
q.remove() #Extract element
q.remove() #Extract element
#returns Boolean indicating if the queue is empty
print ("The queue is", q.items)
print ("Empty Queue?", q.isEmpty())
As we can see the queue is not empty, so the program returned False.
Full Code:
class queue:
def __init__(self):
self.items=[]
def insert(self, item):
self.items.append(item)
def remove(self):
try:
return self.items.pop(0)
except:
raise ValueError ("The Queue is empty")
def isEmpty(self):
return (self.items == [])
q=queue() #Create and initialize the queue methods
q.insert(10) #Insert the item ’10’ in to the queue
q.insert(20) #Insert the item ’20’ in to the queue
q.insert(30) #Insert the item ’30’ in to the queue
q.remove() #Extract element
q.remove() #Extract element
#returns Boolean indicating if the queue is empty
print ("The queue is", q.items)
print ("Empty Queue?", q.isEmpty())
Run the code and learn python
Curriculum
Posted on Utopian.io - Rewarding Open Source Contributors