3.5 Extras

3.5.1 Stack

• >Stacks are LIFO, Last In First Out Data Structures. Elements go in and out from a single direction only. Main operations/methods of Stack are adding an element which is called a push operation and removing an element which is called a pop operation. Other operations are isEmpty, isFull and peek etc.
• >The main operations of Stack can be easily performed using list's available methods. And as append() is ~O(1) and pop is O(1), so list should be good enough for Stacks.

## Create a stack
my_stack = [10, 45, 32, 34]
print(my_stack)  # [10, 45, 32, 34]


## Add/Remove operations
# push: append at top
my_stack.append(20)
print(my_stack)  # [10, 45, 32, 34, 20]

# pop: remove at top
my_stack.pop()
print(my_stack)  # [10, 45, 32, 34]

3.5.2 Queue

• >Queues are FIFO, First In First Out Data Structures. Elements go in one direction and go out from another direction. Main operations/methods of Queue are adding an element which is called an enqueue operation and removing an element which is called a dequeue operation. Other operations are isEmpty, isFull and peek etc.
• >Variants of Queue are circular queue, priority queue and dequeue. Let's use list as a Queue.

## Create a queue
my_queue = [23, 67, 12, 67, 89]
print(my_queue)  # [23, 67, 12, 67, 89]


## Add/Remove operations
# enqueue: append at rear
my_queue.append(20)
print(my_queue)  # [23, 67, 12, 67, 89, 20]

# dequeue: remove at front
my_queue.pop(0) 
print(my_queue)  # [67, 12, 67, 89, 20]

• >Python also has a dequeue (double ended queue) Data Structure which can also be used as a normal Queue. They are implemented as doubly linked-list and support adding & removing from both sides (front & rear), they are efficient at add/remove from left (front) operation. Other operations have similar performance as list.
• >For Queues we only need to append at the rear and pop/remove at the front, both of which are O(1) for dequeue, which is great. They are not part of core Python and need to be imported from the collections module.

from collections import deque
import sys

my_list = [23, 45, 12, 67, 132, 67]
## Create a deque, can be initialized using any iterable
dq = deque(my_list)
print(dq)  # deque([23, 45, 12, 67, 132, 67])


## Add/Remove operations
# enqueue: append at rear
dq.append(20)
print(dq)  # deque([23, 45, 12, 67, 132, 67, 20])

# dequeue: remove at front
dq.popleft()
print(dq)  # deque([45, 12, 67, 132, 67, 20])

# only drawback is that they are data inefficient than list
print(sys.getsizeof(dq))  # 624
print(sys.getsizeof(my_list))  # 152

3.5.3 Priority Queue

• >Priority Queues are used when the elements are supposed to have some priority associated with them. So instead of using FIFO like normal queues, Priority Queue uses priority, elements with highest priority are taken out first. In order for this to work the data has to be comparable (same data type).
• >Python provides heapq which are Priority Queues implementation, they support only min-heap (smallest element has highest priority). The heapq module implements the Heap Data Structure (Binary heap) which is the most efficient way of implementing a Priority Queue. A Heap DS is a complete binary tree (all levels are filled except the leaf positions) that satisfies a heap property, which is nothing but the max/min criteria for getting an element out.
• >A Heap DS has a heapify function, it is responsible for constructing a Heap DS i.e constructing/adding elements in a binary tree for sorting. The three main operations of a Heap DS add, delete and peek are explained below:
  1. >add: First traverse to the last (leaf) empty position (left to right), add the element there and heapify the tree.
  2. >delete: Select the index to be deleted, replace with the last element (rightest leaf), remove the last element and heapify the tree.
  3. >peek: Traverse to the rightest leaf position, return the element.
• >A Priority Queue is useful in tasks such as prioritizing, scheduling, load balancing etc. Another implementation of Priority Queue is in the queue module, named PriorityQueue, you can also use a normal list for doing the same utilizing the sorted() function, but heapq operations are more efficient.

import heapq

## Create a priority queue, initialize with a empty list
my_pq = []

# Initialize with values, use the heapify function
# first to construct a Heap DS
my_pq = [34, 6, 23, 67, 23, 78]
heapq.heapify(my_pq)
print(my_pq)  # [6, 23, 23, 67, 34, 78]


## Adding: Use the 'heappush()' function to add elements,
# syntax heappush(container, item)
# here container is our list 'my_pq'
heapq.heappush(my_pq, 3)
heapq.heappush(my_pq, 2)
heapq.heappush(my_pq, 0)
print(my_pq)  # [0, 3, 2]


## Removing: Use the 'heappop()' function to get elements from the list
print(heapq.heappop(my_pq))  # 0
# smallest element is taken out first
print(my_pq)  # [2, 3]
# when a element is inserted, it is put in its right sorted position
# so [0] index is always the smallest and hence the pop position


## Elements should be comparable: So once a 'int' type is inserted,
# other elements should be 'int' only else 'TypeError' will be raised
heapq.heappush(my_pq, "some string")  # TypeError

# The items can also be tuple
# so for example, we can provide some name to a item
my_pq = []

heapq.heappush(my_pq, (2, "task2"))
heapq.heappush(my_pq, (1, "task1"))
heapq.heappush(my_pq, (5, "task3"))
print(heapq.heappop(my_pq))  # (1, 'task1')

• >Apart from the above Data Structures there are some more that I haven't mentioned, you can find them in the collections module.