# Explore Data Structure and Algorithm Part-4

Previous link: https://m-alinkon10.medium.com/explore-data-structure-and-algorithm-part-3-7ab58eba2996

We are gonna cover that topic

Stack

Queue

Types of Queue

Circular Queue

Priority Queue

Deque

Heap Data Structure

A stack is a linear data structure that follows the principle of **Last In First Out (LIFO)**. This means the last element inserted inside the stack is removed first.

You can think of the stack data structure as a pile of coins on top of another.

Here, you can:

- Put a new coin on top
- Remove the top coin

# LIFO Principle of Stack

in programming, putting an item on top of the stack is called a **push,** and removing an item is called **pop**.

# Basic Operations of Stack

**Push**: Add an element to the top of a stack**Pop**: Remove an element from the top of a stack**IsEmpty**: Check if the stack is empty**IsFull**: Check if the stack is full**Peek**: Get the value of the top element without removing it

`# Stack in python`

# Creating a stack

def create_stack():

stack = []

return stack

# Creating an empty stack

def check_empty(stack):

return len(stack) == 0

# Adding items into the stack

def push(stack, item):

stack.append(item)

print("pushed item: " + item)

# Removing an element from the stack

def pop(stack):

if (check_empty(stack)):

return "stack is empty"

return stack.pop()

stack = create_stack()

push(stack, str(1))

push(stack, str(2))

push(stack, str(3))

push(stack, str(4))

print("popped item: " + pop(stack))

print("stack after popping an element: " + str(stack))

# Applications of Stack Data Structure

Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:

**To reverse a word**— Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.**In compilers**— Compilers use the stack to calculate the value of expressions like`2 + 4 / 5 * (7 - 9)`

by converting the expression to prefix or postfix form.**In browsers**— The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.

# Queue Data Structure

Queue follows the **First In First Out (FIFO)** rule — the item that goes in first is the item that comes out first.

# Basic Operations of Queue

**Enqueue**: Add an element to the end of the queue**Dequeue**: Remove an element from the front of the queue**IsEmpty**: Check if the queue is empty**IsFull**: Check if the queue is full**Peek**: Get the value of the front of the queue without removing it

# Working of Queue

- two pointers FRONT and REAR
- FRONT track the first element of the queue
- REAR track the last element of the queue
- initially, set the value of FRONT and REAR to -1

# Enqueue Operation

- check if the queue is full
- for the first element, set the value of FRONT to 0
- increase the REAR index by 1
- add the new element in the position pointed to by REAR

# Dequeue Operation

- check if the queue is empty
- return the value pointed by FRONT
- increase the FRONT index by 1
- for the last element, reset the values of FRONT and REAR to -1

`# Queue in Python`

class Queue:

def __init__(self):

self.queue = []

# Add an element

def enqueue(self, item):

self.queue.append(item)

# Remove an element

def dequeue(self):

if len(self.queue) < 1:

return None

return self.queue.pop(0)

# Display the queue

def display(self):

print(self.queue)

def size(self):

return len(self.queue)

q = Queue()

q.enqueue(1)

q.enqueue(2)

q.enqueue(3)

q.enqueue(4)

q.enqueue(5)

q.display()

q.dequeue()

print("After removing an element")

q.display()

# Applications of Queue

- CPU scheduling, Disk Scheduling
- When data is transferred asynchronously between two processes.The queue is used for synchronization. For example IO Buffers, pipes, file IO, etc
- Handling of interrupts in real-time systems.
- Call Center phone systems use Queues to hold people calling them in order.

**There are four different types of queues:**

- Simple Queue — It strictly follows the FIFO (First in First out) rule.
- Circular Queue- the last element points to the first element making a circular link.
- Priority Queue A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.
- Double Ended Queue- In a double ended queue, insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO (First In First Out) rule.

# Heap Data Structure

Heap data structure is a complete binary tree.

hereis the link : https://www.javatpoint.com/full-binary-tree-vs-complete-binary-tree

# Heap Operations

Heapify: Heapify is the process of creating a heap data structure from a binary tree`Heapify(array, size, i)`

set i as largest

leftChild = 2i + 1

rightChild = 2i + 2

if leftChild > array[largest]

set leftChildIndex as largest

if rightChild > array[largest]

set rightChildIndex as largest

`swap array[i] and array[largest]`

Insert Element into Heap

`If there is no node, `

create a newNode.

else (a node is already present)

insert the newNode at the end (last node from left to right.)

heapify the array

# Delete Element from Heap

`If nodeToBeDeleted is the leafNode`

remove the node

Else swap nodeToBeDeleted with the lastLeafNode

remove noteToBeDeleted

heapify the array

# Peek (Find max/min)

Peek operation returns the maximum element from Max Heap or minimum element from Min Heap without deleting the node.

# Max-Heap data structure in Python

def heapify(arr, n, i):

largest = i

l = 2 * i + 1

r = 2 * i + 2

if l < n and arr[i] < arr[l]:

largest = l

if r < n and arr[largest] < arr[r]:

largest = r

if largest != i:

arr[i],arr[largest] = arr[largest],arr[i]

heapify(arr, n, largest)

def insert(array, newNum):

size = len(array)

if size == 0:

array.append(newNum)

else:

array.append(newNum);

for i in range((size//2)-1, -1, -1):

heapify(array, size, i)

def deleteNode(array, num):

size = len(array)

i = 0

for i in range(0, size):

if num == array[i]:

break

array[i], array[size-1] = array[size-1], array[i]

array.remove(num)

for i in range((len(array)//2)-1, -1, -1):

heapify(array, len(array), i)

arr = []

insert(arr, 3)

insert(arr, 4)

insert(arr, 9)

insert(arr, 5)

insert(arr, 2)

print (“Max-Heap array: “ + str(arr))

deleteNode(arr, 4)

print(“After deleting an element: “ + str(arr))

# Heap Data Structure Applications

- Heap is used while implementing a priority queue.
- Dijkstra’s Algorithm
- Heap Sort

Note: for better understanding go to the programmiz dot com