Data Structures with Python.ipynb

Kernel: Python 3 (ipykernel)

1. Lists

Concept: Lists are ordered collections of items, which can be of different types. Lists are mutable, meaning you can change their content.

# Creating a list
fruits = ["apple", "banana", "cherry"]

# Accessing elements
print(fruits[1])  # Output: banana

# Modifying elements
fruits[2] = "blueberry"

# Adding elements
fruits.append("orange")

# Removing elements
fruits.remove("banana")

# Iterating through a list
for fruit in fruits:
    print(fruit)

banana
apple
blueberry
orange

2. Tuples

Concept: Tuples are similar to lists, but they are immutable, meaning their content cannot be changed after creation.

# Creating a tuple
coordinates = (10.0, 20.0)

# Accessing elements
print(coordinates[0])  # Output: 10.0

# Iterating through a tuple
for coord in coordinates:
    print(coord)

10.0
10.0
20.0

3. Dictionaries

Concept: Dictionaries are unordered collections of key-value pairs. Keys must be unique and immutable.

# Creating a dictionary
student_grades = {"Alice": 85, "Bob": 90, "Charlie": 78}

# Accessing values by key
print(student_grades["Bob"])  # Output: 90

# Adding a new key-value pair
student_grades["David"] = 88

# Removing a key-value pair
del student_grades["Charlie"]

# Iterating through a dictionary
for student, grade in student_grades.items():
    print(f"{student}: {grade}")

90
Alice: 85
Bob: 90
David: 88

4. Sets

Concept: Sets are unordered collections of unique items. They are useful for operations like union, intersection, and difference.

Example:

# Creating a set
unique_numbers = {1, 2, 3, 4, 5,5,9}

# Adding elements
unique_numbers.add(6)

# Removing elements
unique_numbers.discard(2)

# Set operations
other_numbers = {4, 5, 6, 7}
print(unique_numbers & other_numbers)  # Output: {4, 5, 6} (intersection)
print(unique_numbers | other_numbers)  # Output: {1, 4, 5, 6, 7} (union)
print(unique_numbers - other_numbers)  # Output: {1} (difference)

{4, 5, 6}
{1, 3, 4, 5, 6, 7, 9}
{1, 3, 9}

5. Queues (using collections.deque)

Concept: Queues are collections used to manage data in a First-In-First-Out (FIFO) manner.

from collections import deque

# Creating a queue
queue = deque(["first", "second", "third"])

# Enqueuing (adding to the end)
queue.append("fourth")

# Dequeuing (removing from the front)
print(queue.popleft())  # Output: first

# Iterating through a queue
for item in queue:
    print(item)

first
second
third
fourth

6. Stacks (using a list)

Concept: Stacks are collections that follow Last-In-First-Out (LIFO) principles.

## Creating a stack
stack = []

# Pushing (adding to the end)
stack.append("first")
stack.append("second")
stack.append("third")

# Popping (removing from the end)
print("Removing from the end:")
print(stack.pop())  # Output: third

# Peeking (viewing the top element without removing it)
print("Viewing the top element without removing it")
print(stack[-1])    # Output: second

print("Iterating through a stack")
for item in stack:
    print(item)

Removing from the end:
third
Viewing the top element without removing it
second
Iterating through a stack
first
second

Stacks

• Stacks follow the Last-In-First-Out (LIFO) principle. Here’s how you can work with them:

Example 1: Balancing Parentheses

Concept: Check if a string of parentheses is balanced using a stack.

def is_balanced(expression):
    stack = []
    matching_bracket = {')': '(', '}': '{', ']': '['}

    for char in expression:
        if char in matching_bracket.values():
            stack.append(char)
        elif char in matching_bracket.keys():
            if stack == [] or matching_bracket[char] != stack.pop():
                return False

    return stack == []

# Test
print("Testing the expression:")
expression = "{[()()]}"
print(is_balanced(expression))  # Output: True
print("Testing the expression2:")
expression2 = "{[((]}"
print(is_balanced(expression2)) 

Testing the expression:
True
Testing the expression2:
False

Example 2: Implementing a Stack using Linked List

Concept: Create a stack using a custom linked list.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.top.value

    def is_empty(self):
        return self.top is None

# Test
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2

3
2

Queues

Queues follow the First-In-First-Out (FIFO) principle. Here’s how you can work with them:

• Example 1: Implementing a Queue using Two Stacks Concept: Use two stacks to implement a queue.

class QueueWithStacks:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def enqueue(self, value):
        self.stack1.append(value)

    def dequeue(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        if not self.stack2:
            raise IndexError("dequeue from empty queue")
        return self.stack2.pop()

# Test
print("Test the Stacks:")
queue = QueueWithStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.dequeue())  # Output: 2

Test the Stacks:
1
2

Example 2: Using queue.Queue for Thread-Safe Queue Operations

Concept: Use Python’s built-in queue.Queue for thread-safe queue operations.

import queue

# Creating a queue
q = queue.Queue()

# Enqueuing (adding to the end)
q.put(1)
q.put(2)
q.put(3)

# Dequeuing (removing from the front)
print(q.get())  # Output: 1
print(q.get())  # Output: 2

# Checking if the queue is empty
print(q.empty())  # Output: False

Quick Practice

Employee Data Management System

Create a Python program that manages and processes employee data using various data structures. The system should perform the following operations

• Add New Employees: Store employee details (ID, name, age, department, salary) in appropriate data structures (use dictionary for storing employee details).

• Employee Search by ID: Allow users to search for an employee by their ID (use dictionary lookup for efficient search).

• Sort Employees by Salary: Sort and display employees based on their salary in descending order (use list of tuples for sorting).

• Remove Duplicate Employees: Ensure there are no duplicate entries (use set to remove duplicate employee IDs).

• Department-wise Employee Details: Organize and display employees department-wise (use dictionary of lists where keys are department names and values are lists of employees).

• Add Multiple Employees using Stack: Implement a stack to allow adding multiple employees. When all employees are added, display the stack in reverse order to show the order in which employees were added.

• Queue for Employee Exit: Implement a queue to manage employees who are leaving the organization. Add employees to the queue as they leave, and show the order in which they exit.

# Importing necessary modules
from collections import deque

# Employee Data Management System

class EmployeeManagementSystem:
    def __init__(self):
        self.employees = {}  # Dictionary to store employee details with Employee ID as key
        self.exit_queue = deque()  # Queue for employee exit
        self.add_stack = []  # Stack for adding employees

    # Function to add a new employee
    def add_employee(self, emp_id, name, age, department, salary):
        if emp_id not in self.employees:
            self.employees[emp_id] = {
                "Name": name,
                "Age": age,
                "Department": department,
                "Salary": salary
            }
            print(f"Employee {name} added successfully!")
        else:
            print(f"Employee with ID {emp_id} already exists!")

    # Function to search employee by ID
    def search_employee(self, emp_id):
        if emp_id in self.employees:
            return self.employees[emp_id]
        else:
            return "Employee not found!"

    # Function to sort employees by salary
    def sort_employees_by_salary(self):
        # Creating a list of tuples (emp_id, salary) and sorting by salary
        sorted_employees = sorted(self.employees.items(), key=lambda x: x[1]['Salary'], reverse=True)
        for emp_id, details in sorted_employees:
            print(f"ID: {emp_id}, Name: {details['Name']}, Salary: {details['Salary']}")

    # Function to remove duplicate employee IDs
    def remove_duplicates(self):
        unique_ids = set(self.employees.keys())  # Using set to ensure unique IDs
        print(f"Unique employee IDs: {unique_ids}")

    # Function to display department-wise employee details
    def department_wise_employees(self):
        department_dict = {}
        for emp_id, details in self.employees.items():
            dept = details['Department']
            if dept not in department_dict:
                department_dict[dept] = []
            department_dict[dept].append(f"{details['Name']} (ID: {emp_id})")
        
        for dept, emp_list in department_dict.items():
            print(f"\nDepartment: {dept}")
            for emp in emp_list:
                print(emp)

    # Function to add multiple employees using stack
    def add_multiple_employees(self, employees_list):
        for emp in employees_list:
            self.add_stack.append(emp)
        print("Employees added to the stack.")
    
    # Function to display stack in reverse order (LIFO)
    def display_stack_reverse(self):
        while self.add_stack:
            emp = self.add_stack.pop()
            print(f"Employee: {emp['Name']}, ID: {emp['ID']}")

    # Function to add employees to exit queue
    def employee_exit(self, emp_id):
        if emp_id in self.employees:
            self.exit_queue.append(emp_id)
            print(f"Employee {self.employees[emp_id]['Name']} added to exit queue.")
        else:
            print(f"Employee with ID {emp_id} not found!")

    # Function to process the employee exit queue
    def process_exit_queue(self):
        while self.exit_queue:
            emp_id = self.exit_queue.popleft()  # FIFO order
            print(f"Employee {self.employees[emp_id]['Name']} has exited the organization.")
            del self.employees[emp_id]  # Removing employee from the system


# Testing the Employee Management System

ems = EmployeeManagementSystem()

# Adding new employees
ems.add_employee(1, "John Doe", 30, "HR", 60000)
ems.add_employee(2, "Jane Smith", 28, "IT", 80000)
ems.add_employee(3, "Alice Johnson", 35, "Finance", 75000)
ems.add_employee(4, "Bob Brown", 40, "IT", 65000)

# Searching for an employee by ID
print("\nSearch Employee by ID:")
print(ems.search_employee(2))

# Sorting employees by salary
print("\nEmployees Sorted by Salary:")
ems.sort_employees_by_salary()

# Removing duplicate employees (This example does not have duplicates, but shows usage)
print("\nRemoving Duplicate Employees:")
ems.remove_duplicates()

# Displaying department-wise employee details
print("\nDepartment-wise Employee Details:")
ems.department_wise_employees()

# Adding multiple employees using stack
print("\nAdding Employees Using Stack:")
new_employees = [
    {"ID": 5, "Name": "Charlie Black", "Age": 29, "Department": "HR", "Salary": 55000},
    {"ID": 6, "Name": "Diana White", "Age": 32, "Department": "IT", "Salary": 70000}
]
ems.add_multiple_employees(new_employees)

# Display stack in reverse order (LIFO)
print("\nStack in Reverse Order:")
ems.display_stack_reverse()

# Adding employees to exit queue
print("\nEmployee Exit Queue:")
ems.employee_exit(1)
ems.employee_exit(3)

# Processing employee exit queue (FIFO)
print("\nProcessing Employee Exit Queue:")
ems.process_exit_queue()

Employee John Doe added successfully!
Employee Jane Smith added successfully!
Employee Alice Johnson added successfully!
Employee Bob Brown added successfully!

Search Employee by ID:
{'Name': 'Jane Smith', 'Age': 28, 'Department': 'IT', 'Salary': 80000}

Employees Sorted by Salary:
ID: 2, Name: Jane Smith, Salary: 80000
ID: 3, Name: Alice Johnson, Salary: 75000
ID: 4, Name: Bob Brown, Salary: 65000
ID: 1, Name: John Doe, Salary: 60000

Removing Duplicate Employees:
Unique employee IDs: {1, 2, 3, 4}

Department-wise Employee Details:

Department: HR
John Doe (ID: 1)

Department: IT
Jane Smith (ID: 2)
Bob Brown (ID: 4)

Department: Finance
Alice Johnson (ID: 3)

Adding Employees Using Stack:
Employees added to the stack.

Stack in Reverse Order:
Employee: Diana White, ID: 6
Employee: Charlie Black, ID: 5

Employee Exit Queue:
Employee John Doe added to exit queue.
Employee Alice Johnson added to exit queue.

Processing Employee Exit Queue:
Employee John Doe has exited the organization.
Employee Alice Johnson has exited the organization.

Employee Data Management System where the user is prompted to enter employee details interactively (ID, name, age, department, and salary)

# Importing necessary modules
from collections import deque

# Employee Data Management System

class EmployeeManagementSystem:
    def __init__(self):
        self.employees = {}  # Dictionary to store employee details with Employee ID as key
        self.exit_queue = deque()  # Queue for employee exit
        self.add_stack = []  # Stack for adding employees

    # Function to add a new employee
    def add_employee(self, emp_id, name, age, department, salary):
        if emp_id not in self.employees:
            self.employees[emp_id] = {
                "Name": name,
                "Age": age,
                "Department": department,
                "Salary": salary
            }
            print(f"Employee {name} added successfully!")
        else:
            print(f"Employee with ID {emp_id} already exists!")

    # Function to search employee by ID
    def search_employee(self, emp_id):
        if emp_id in self.employees:
            return self.employees[emp_id]
        else:
            return "Employee not found!"

    # Function to sort employees by salary
    def sort_employees_by_salary(self):
        # Creating a list of tuples (emp_id, salary) and sorting by salary
        sorted_employees = sorted(self.employees.items(), key=lambda x: x[1]['Salary'], reverse=True)
        for emp_id, details in sorted_employees:
            print(f"ID: {emp_id}, Name: {details['Name']}, Salary: {details['Salary']}")

    # Function to remove duplicate employee IDs
    def remove_duplicates(self):
        unique_ids = set(self.employees.keys())  # Using set to ensure unique IDs
        print(f"Unique employee IDs: {unique_ids}")

    # Function to display department-wise employee details
    def department_wise_employees(self):
        department_dict = {}
        for emp_id, details in self.employees.items():
            dept = details['Department']
            if dept not in department_dict:
                department_dict[dept] = []
            department_dict[dept].append(f"{details['Name']} (ID: {emp_id})")
        
        for dept, emp_list in department_dict.items():
            print(f"\nDepartment: {dept}")
            for emp in emp_list:
                print(emp)

    # Function to add multiple employees using stack
    def add_multiple_employees(self, employees_list):
        for emp in employees_list:
            self.add_stack.append(emp)
        print("Employees added to the stack.")
    
    # Function to display stack in reverse order (LIFO)
    def display_stack_reverse(self):
        while self.add_stack:
            emp = self.add_stack.pop()
            print(f"Employee: {emp['Name']}, ID: {emp['ID']}")

    # Function to add employees to exit queue
    def employee_exit(self, emp_id):
        if emp_id in self.employees:
            self.exit_queue.append(emp_id)
            print(f"Employee {self.employees[emp_id]['Name']} added to exit queue.")
        else:
            print(f"Employee with ID {emp_id} not found!")

    # Function to process the employee exit queue
    def process_exit_queue(self):
        while self.exit_queue:
            emp_id = self.exit_queue.popleft()  # FIFO order
            print(f"Employee {self.employees[emp_id]['Name']} has exited the organization.")
            del self.employees[emp_id]  # Removing employee from the system


# Function to gather employee details from the user
def get_employee_details():
    emp_id = input("Enter Employee ID: ")
    name = input("Enter Employee Name: ")
    age = int(input("Enter Employee Age: "))
    department = input("Enter Employee Department: ")
    salary = float(input("Enter Employee Salary: "))
    return emp_id, name, age, department, salary


# Function to add multiple employees by user input
def add_multiple_employees_from_user(ems):
    num_employees = int(input("Enter the number of employees to add: "))
    for _ in range(num_employees):
        emp_id, name, age, department, salary = get_employee_details()
        ems.add_employee(emp_id, name, age, department, salary)


# Main Program: Interacting with the Employee Management System

ems = EmployeeManagementSystem()

while True:
    print("\n--- Employee Management System ---")
    print("1. Add Employee")
    print("2. Search Employee by ID")
    print("3. Sort Employees by Salary")
    print("4. Remove Duplicate Employees")
    print("5. Department-wise Employee Details")
    print("6. Add Multiple Employees using Stack")
    print("7. Display Stack in Reverse Order")
    print("8. Employee Exit")
    print("9. Process Employee Exit Queue")
    print("10. Exit")
    
    choice = int(input("\nEnter your choice: "))
    
    if choice == 1:
        # Adding a single employee
        emp_id, name, age, department, salary = get_employee_details()
        ems.add_employee(emp_id, name, age, department, salary)
    
    elif choice == 2:
        # Searching for an employee by ID
        emp_id = input("Enter Employee ID to search: ")
        print(ems.search_employee(emp_id))
    
    elif choice == 3:
        # Sorting employees by salary
        print("\nEmployees Sorted by Salary:")
        ems.sort_employees_by_salary()
    
    elif choice == 4:
        # Removing duplicate employees
        print("\nRemoving Duplicate Employees:")
        ems.remove_duplicates()
    
    elif choice == 5:
        # Display department-wise employee details
        print("\nDepartment-wise Employee Details:")
        ems.department_wise_employees()
    
    elif choice == 6:
        # Adding multiple employees using stack
        add_multiple_employees_from_user(ems)
    
    elif choice == 7:
        # Display stack in reverse order
        print("\nStack in Reverse Order:")
        ems.display_stack_reverse()
    
    elif choice == 8:
        # Adding employees to exit queue
        emp_id = input("Enter Employee ID to add to exit queue: ")
        ems.employee_exit(emp_id)
    
    elif choice == 9:
        # Processing employee exit queue
        print("\nProcessing Employee Exit Queue:")
        ems.process_exit_queue()
    
    elif choice == 10:
        print("Exiting the system. Goodbye!")
        break
    
    else:
        print("Invalid choice! Please try again.")

--- Employee Management System ---
1. Add Employee
2. Search Employee by ID
3. Sort Employees by Salary
4. Remove Duplicate Employees
5. Department-wise Employee Details
6. Add Multiple Employees using Stack
7. Display Stack in Reverse Order
8. Employee Exit
9. Process Employee Exit Queue
10. Exit

Enter your choice: 10
Exiting the system. Goodbye!