Day 2: Understanding and Implementing Custom Data Structures: Stacks, Queues, and Linked Lists

Day 2: Understanding and Implementing Custom Data Structures: Stacks, Queues, and Linked Lists

I. Introduction to Custom Data Structures

Data structures form the backbone of efficient programming. They not only provide a means to manage large amounts of data efficiently but also facilitate efficient algorithms for different kinds of applications. While Python offers built-in data structures like lists, tuples, sets, and dictionaries, custom data structures such as stacks, queues, and linked lists offer more precise control over data and can be tailored to suit specific requirements.

A. Definition and Overview of Custom Data Structures

Custom data structures are user-defined data structures that are adapted or designed to solve specific problems. These structures are not usually provided as built-ins in the programming language, hence the term “custom”. In Python, custom data structures are typically created using classes, leveraging object-oriented programming features to encapsulate data and the operations that can be performed on the data.

The focus for today’s study is on three specific custom data structures: Stacks, Queues, and Linked Lists.

  • Stacks operate based on the LIFO (Last In, First Out) principle, meaning that the most recently added item is the first one to be removed.
  • Queues, in contrast, follow the FIFO (First In, First Out) principle. The first item added (enqueued) to the queue will be the first one to be removed (dequeued).
  • Linked Lists consist of nodes where each node contains a data field and a reference(link) to the next node in the list.

B. Importance and Applications of Custom Data Structures in Python

Understanding and implementing custom data structures is a crucial skill for any Python programmer. These data structures find applications in various areas of computer science and software engineering:

  • Stacks: Used in expression evaluation and syntax parsing, backtracking (like in maze solving problems or searching algorithms), memory management, and more.
  • Queues: Essential in scheduling tasks in computing, handling requests on a single shared resource like a printer, thread synchronization, and in algorithms like Breadth First Search.
  • Linked Lists: Ideal for implementations where memory is a constraint, as they don’t need a contiguous memory block like arrays. Also useful in various applications including music players (circular linked list) and page replacement algorithms.

In the following sections, we will dive deeper into each of these data structures, understanding their characteristics, operations, and how to implement them in Python. We’ll also engage in hands-on coding exercises to cement your understanding of these crucial concepts. The journey into custom data structures promises to boost your programming prowess and problem-solving abilities. So, let’s delve in!

II. Section 1: Understanding Stacks

A. Introduction to Stacks

Stacks form an integral part of data structures and are quite simple to understand and implement. They are used extensively in both system and application level programming.

1. Concept and Real-Life Examples

The concept of a stack is similar to a physical stack or pile. For example, consider a stack of books. You can place one book on top of another. The book that is put on the stack last is the first one to be removed as it is at the top. If you want to get to the book at the bottom, you have to remove all the books on top of it first. This principle of accessing elements is the basic concept behind a stack in programming as well.

Another real-life example would be a web browser’s back button. As you navigate from webpage to webpage, the URLs are placed on a stack. The current page you are on is at the top of the stack. If you click the back button, you’re taken to the URL at the top of the stack. If you keep clicking back, you’ll visit the URLs of the stack in reverse order of how you first visited them.

2. Explanation of Last-In-First-Out (LIFO) Principle

Stacks in programming are based on the Last-In-First-Out (LIFO) principle. The item that is added or pushed last onto the stack is the first one to be removed or popped.

Imagine a spring-loaded stack of plates in a buffet. You take a plate from the top (pop), and when a new plate is added (pushed), it’s placed on the top. The plate that was placed there last will be the first one you take. This is the LIFO principle in action.

Understanding this principle is fundamental to comprehending the nature of stack operations and how to apply stacks to solve computational problems. In the next section, we’ll discuss the key operations that can be performed on stacks and demonstrate how to implement a stack in Python.

B. Operations on Stacks

There are three fundamental operations performed on stacks, namely Push, Pop, and Peek (or Top). Let’s understand each operation in detail:

1. Push Operation

The push operation adds an element to the top of the stack.

Definition and uses: When an element is added to the stack, we say it is “pushed” onto the stack. This operation increases the size of the stack by one. If the stack was empty, the pushed element becomes the top element. If there were already elements in the stack, the pushed element is placed on top of the previous top element.

In terms of its usage, the push operation is used whenever we want to add an item to the stack. For example, in a browser’s back button functionality, the push operation would be used to add the URL of a new webpage to the stack when a user navigates to that page.

Coding example in Python:

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)

s = Stack()
s.push("Hello")
s.push("World")
print(s.stack)  # Output: ['Hello', 'World']
2. Pop Operation

The pop operation removes the top element from the stack.

Definition and uses: The pop operation removes the most recently added (i.e., top) element from the stack. This operation decreases the size of the stack by one. If the stack is empty, a pop operation may return an error or exception, depending on the implementation.

Pop operations are used in many applications, such as when implementing undo functionality in software applications or backtracking in algorithms.

Coding example in Python:

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

s = Stack()
s.push("Hello")
s.push("World")
print(s.pop())  # Output: 'World'
print(s.stack)  # Output: ['Hello']
3. Peek or Top Operation

The peek (or top) operation returns the top element from the stack without removing it.

Definition and uses: The peek operation retrieves the top element of the stack but does not remove it from the stack. This operation is helpful when we need to know what the top element is for further processing but do not want to remove it.

Peek operations are useful in numerous applications. For instance, stack-based algorithms may need to inspect the top element to make decisions, such as in the case of parsing and evaluating mathematical expressions.

Coding example in Python:

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()
    def peek(self):
        if len(self.stack) < 1:
            return None
        return self.stack[-1]

s = Stack()
s.push("Hello")
s.push("World")
print(s.peek())  # Output: 'World'
print(s.stack)  # Output: ['Hello', 'World']

In the upcoming section, we will discuss how to implement these operations and build a fully functional stack in Python.

C. Implementing Stacks in Python

In Python, there are several ways to implement a stack. You can use a list, which is a built-in Python data structure, or you can create your own class to define the behavior of the stack.

1. Using Built-in Data Types (list)

Python’s built-in list data type provides methods that make it act very much like a stack. The append() method can be used to simulate the push operation, and the pop() method without an explicit index removes and returns the last item from the list, effectively working as the pop operation.

Here’s an example:

stack = []

# push elements onto the stack
stack.append('A')
stack.append('B')
stack.append('C')

print('Initial Stack:', stack)  # Output: Initial Stack: ['A', 'B', 'C']

# pop elements from the stack
print('Elements popped from stack:')
print(stack.pop())  # Output: 'C'
print(stack.pop())  # Output: 'B'
print(stack.pop())  # Output: 'A'

print('Stack after elements are popped:', stack)  # Output: Stack after elements are popped: []
2. Creating a Stack Class

While using lists provides basic stack functionality, creating a dedicated Stack class can provide clearer code and more control over the operations. Below is an example of a simple Stack class in Python:

class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.stack.pop()

    def peek(self):
        return self.stack[-1] if not self.isEmpty() else "Stack is empty"
3. Example Programs and Hands-On Exercises

Consider an exercise where we use a stack to reverse a string:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        return self.stack.pop() if self.stack else None

# function to reverse string using stack
def reverse_string(s):
    stack = Stack()

    for char in s:
        stack.push(char)

    reversed_s = ""
    while (char := stack.pop()) is not None:  # using Python's assignment expression
        reversed_s += char

    return reversed_s

print(reverse_string("Hello World!"))  # Output: !dlroW olleH

This simple program demonstrates how to use a stack to reverse a string by pushing all the characters of the string onto a stack and then popping them off into a new string.

As a hands-on exercise, try using a stack to check if parentheses in a given string are balanced. For example, the string "((()))" is balanced, but "((())" is not.

Stacks provide an elegant and efficient way to solve such problems. Understanding stacks is essential to mastering data structures and algorithms in Python. With practice and patience, you’ll find them increasingly intuitive and powerful.

III. Section 2: Understanding Queues

A. Introduction to Queues

Queues form a cornerstone of data structures and are used widely in various fields of computer science and programming.

1. Concept and Real-Life Examples

The concept of a queue in programming is similar to queues in real life. Consider a line of people waiting to buy tickets at a movie theater. The person who has been waiting the longest is the next one to get served. When a new person arrives, they join the end of the queue. This principle forms the basis of a queue in programming.

Another common real-life example of a queue is a print queue. When multiple print tasks are sent to a printer, they get lined up and the printer processes them in the order they were received.

2. Explanation of First-In-First-Out (FIFO) Principle

Queues in computer science adhere to the First-In-First-Out (FIFO) principle. This means that the item that has been in the queue the longest is the first one to be removed. Similarly, newly added (or enqueued) items are placed at the back of the queue and have to wait their turn to be removed (or dequeued).

For instance, consider a queue of print tasks. The first print task sent to the printer will be the first one to be printed and removed from the queue. Any subsequent print tasks will wait in the queue until all the tasks before them are completed.

Understanding this principle is key to comprehending the nature of queue operations and how to apply queues to solve computational problems. In the following sections, we’ll discuss the primary operations performed on queues and how to implement a queue in Python.

B. Operations on Queues

The primary operations performed on queues are Enqueue (insertion), Dequeue (removal), and operations to check the Front and Rear elements of the queue. Let’s explore each one in detail:

1. Enqueue Operation

The enqueue operation adds an element to the end of the queue.

Definition and uses: The enqueue operation involves adding an element to the rear of the queue. It increases the size of the queue by one. The new element becomes the rear of the queue.

In practical applications, the enqueue operation is used when a new task is created or a new element needs to be added to the queue. For instance, in a print queue, when a new print task is sent to the printer, it gets enqueued at the end of the queue.

Coding example in Python:

class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self, item):
        self.queue.append(item)

q = Queue()
q.enqueue("Apple")
q.enqueue("Banana")
print(q.queue)  # Output: ['Apple', 'Banana']
2. Dequeue Operation

The dequeue operation removes an element from the front of the queue.

Definition and uses: The dequeue operation involves removing an element from the front of the queue. It decreases the size of the queue by one. If the queue is empty, a dequeue operation may return an error or exception, depending on the implementation.

In a practical setting, the dequeue operation is used when a task has been completed and needs to be removed from the queue. In the print queue example, once a print task is completed, it is dequeued from the print queue.

Coding example in Python:

class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self, item):
        self.queue.append(item)
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

q = Queue()
q.enqueue("Apple")
q.enqueue("Banana")
print(q.dequeue())  # Output: 'Apple'
print(q.queue)  # Output: ['Banana']
3. Front and Rear Operations

The front operation returns the front element of the queue, and the rear operation returns the last element of the queue. Both operations do not remove the element from the queue.

Definition and uses: The front and rear operations are used to inspect the elements at the front and rear of the queue without removing them. They are useful when the current tasks need to be checked without dequeuing them.

In our print queue example, the front operation could be used to check which print task is currently being processed, and the rear operation to check which task was most recently added to the queue.

Coding example in Python:

class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self, item):
        self.queue.append(item)
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)
    def front(self):
        if len(self.queue) < 1:
            return None
        return self.queue[0]
    def rear(self):
        if len(self.queue) < 1:
            return None
        return self.queue[-1]

q = Queue()
q.enqueue("Apple")
q.enqueue("Banana")
print(q.front())  # Output: 'Apple'
print(q.rear())  # Output: 'Banana'

In the upcoming sections, we will talk about how to implement these operations in Python to create a fully functional queue.

C. Implementing Queues in Python

In Python, there are several ways to implement a queue. You can use built-in data types, such as a list or a deque from the collections module, or create a custom Queue class to have more control over the queue behavior.

1. Using Built-in Data Types (list, collections.deque)

Python’s built-in list data type can simulate queue operations, but it isn’t efficient for large data due to its underlying implementation. The time complexity of popping an element from the front of a list is O(n). To handle queue operations more efficiently, Python provides a collections.deque object, which allows for O(1) time complexity for pop operations from both ends.

Here’s an example using collections.deque:

from collections import deque

queue = deque()

# enqueue elements
queue.append('A')
queue.append('B')
queue.append('C')

print('Initial queue:', list(queue))  # Output: Initial queue: ['A', 'B', 'C']

# dequeue elements
print('Elements dequeued from queue:')
print(queue.popleft())  # Output: 'A'
print(queue.popleft())  # Output: 'B'
print(queue.popleft())  # Output: 'C'

print('Queue after elements are dequeued:', list(queue))  # Output: Queue after elements are dequeued: []
2. Creating a Queue Class

For a more customized and controlled implementation, a Queue class can be created with methods for the required operations. Here’s an example of a Queue class in Python:

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    def size(self):
        return len(self.queue)
3. Example Programs and Hands-On Exercises

As an exercise, consider a scenario where a queue can be used to simulate a real-world event: a server processing tasks. Each task takes a certain amount of time (‘duration’), and tasks are processed in the order they are received (queue order).

class Task:
    def __init__(self, name, duration):
        self.name = name
        self.duration = duration

class ServerQueue(Queue):
    def process_tasks(self):
        while self.size():
            current_task = self.dequeue()
            print(f"Processing task {current_task.name}")
            # simulate task processing time
            time.sleep(current_task.duration)
            print(f"Finished task {current_task.name}")

server = ServerQueue()

# enqueue tasks
server.enqueue(Task("Task 1", 2))
server.enqueue(Task("Task 2", 1))
server.enqueue(Task("Task 3", 3))

# process tasks
server.process_tasks()

In this program, the server processes tasks in the order they are received, waiting the ‘duration’ time before moving on to the next task. This is a simple simulation of how a queue can be used to handle tasks in a server environment.

As a hands-on exercise, try using a queue to simulate a printer queue where print tasks with varying print durations are processed in order.

IV. Section 3: Understanding Linked Lists

A. Introduction to Linked Lists

Linked Lists form the foundation of many advanced data structures and have various applications across different domains of computer science.

1. Concept and Types: Singly, Doubly, and Circular Linked Lists

A linked list is a linear data structure where each element is a separate object called a node. Each node contains a data field and a reference(link) to the next node in the sequence.

Singly Linked List: In a singly linked list, each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node. It is the simplest type of linked list.

Doubly Linked List: In a doubly linked list, each node contains a data field and two pointers or references. One pointer points to the next node, while the other one points to the previous node. As a result, a doubly linked list can be traversed in both directions.

Circular Linked List: In a circular linked list, the last node of the list points back to the first node (or the head) of the list. It can be a singly circular linked list (where the traversal of the list is possible in one direction only) or a doubly circular linked list (where the traversal is possible in both directions).

2. Comparisons with Arrays and Other Data Structures

Arrays vs Linked Lists: An array is a static data structure, meaning it’s size is fixed at the time of creation, whereas a linked list is dynamic and allows for its size to change during runtime. In an array, elements are stored in contiguous memory locations, making indexing of elements quick. On the other hand, elements in a linked list are not stored contiguously in memory, which means you cannot access elements of a linked list using an index directly.

Stacks/Queues vs Linked Lists: While both stacks/queues and linked lists are linear data structures, they differ in terms of their functionality and use cases. Stacks and queues follow a particular order in which operations are performed. Stacks follow LIFO (Last-In-First-Out), and queues follow FIFO (First-In-First-Out) principles. In contrast, linked lists do not follow such order, and insertion and deletion can be done at any place with the proper reference.

In the following sections, we will explore the various operations that can be performed on linked lists and how to implement them in Python.

B. Operations on Linked Lists

Linked lists have many common operations such as insertion, deletion, and traversal. Each operation requires a different approach due to the structure of the linked list. Here’s a detailed look into these operations:

1. Insertion Operation

In a linked list, an element can be inserted at the beginning, at the end, or after a given node.

At the beginning: This involves pointing the next pointer of the new node to the current head of the linked list. The head of the linked list is then updated to the new node.

At the end: This involves traversing the entire linked list and updating the next pointer of the last node to the new node. The new node becomes the last node in the list.

After a given node: This involves updating the next pointer of the new node to the next pointer of the given node. Then, the next pointer of the given node is updated to the new node.

Coding example in Python:

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

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_start(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def insert_end(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while(last.next):
            last = last.next
        last.next = new_node

    def insert_after(self, prev_node, new_data):
        if prev_node is None:
            print("The given previous node must be in LinkedList.")
            return
        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node
2. Deletion Operation

The deletion operation in a linked list involves removing a node from the linked list given a key or at a given position.

Given a key: This involves traversing the linked list until the node with the given key is found. Then, the node is removed by updating the next pointer of the previous node to point to the node after the current node.

At a given position: This involves traversing the linked list to the given position and then removing the node by updating the next pointer of the previous node to point to the node after the current node.

Coding example in Python:

class LinkedList:
    # ... same as before ...

    def delete_node_key(self, key):
        temp = self.head
        if (temp is not None):
            if (temp.data == key):
                self.head = temp.next
                temp = None
                return
        while(temp is not None):
            if temp.data == key:
                break
            prev = temp
            temp = temp.next
        if(temp == None):
            return
        prev.next = temp.next
        temp = None

    def delete_node_position(self, position):
        if self.head == None:
            return
        temp = self.head
        if position == 0:
            self.head = temp.next
            temp = None
            return
        for i in range(position -1 ):
            temp = temp.next
            if temp is None:
                break
        if temp is None:
            return
        if temp.next is None:
            return
        next = temp.next.next
        temp.next = None
        temp.next = next
3. Traversal Operation

Traversal involves moving through or navigating the linked list. Typically, you start from the

head node and follow the references (or ‘links’) to the next node until you reach the end of the list.

Coding example in Python:

class LinkedList:
    # ... same as before ...

    def print_list(self):
        temp = self.head
        while(temp):
            print(temp.data)
            temp = temp.next

With this linked list implementation, you can create a linked list, insert new nodes at different positions, delete nodes either by key or by position, and print the linked list elements by traversing the list.

V. Summary

A. Recap of Stacks, Queues, and Linked Lists

Throughout this section, we delved into three essential custom data structures: stacks, queues, and linked lists.

Stacks are linear data structures that follow a Last-In-First-Out (LIFO) principle. The insertion (push) and removal (pop) of elements occur at the same end, known as the “top” of the stack. Stacks are useful in various scenarios such as function call stacks, undo operations in text editors, and balancing of symbols.

Queues are another type of linear data structure, but they follow a First-In-First-Out (FIFO) principle. The insertion (enqueue) occurs at the “rear” and removal (dequeue) happens from the “front.” Queues are commonly used in scenarios where order needs to be maintained, like CPU scheduling, disk scheduling, or when implementing printers.

Linked Lists provide a dynamic and efficient approach to handle data in a sequential manner. They consist of nodes linked to each other, each node having a data part and a link to the next node. Linked lists are foundational for many other data structures and have various applications in computer science.

B. Importance and Applications of These Data Structures in Python

Understanding and being able to implement these data structures is crucial for any Python programmer, especially those involved in more computationally complex fields like AI and data science.

Stacks are used in parsing, expression evaluation, and backtracking algorithms. They’re essential for function call implementation and can be used to solve problems like reversing words or checking balanced parentheses.

Queues are integral to simulate real-world phenomena such as serving requests on a single shared resource, like a printer, CPU task scheduling, or in networking to handle congestion.

Linked Lists are beneficial for efficient insertion and deletion operations. They serve as a foundation for other data structures like stacks and queues, are used in separate chaining in hash tables, and support polynomial representation and operations, among others.

C. Suggestion for Further Reading and Practice Exercises

To reinforce your understanding of these data structures and their implementation in Python, hands-on practice is vital. You might find the following resources helpful:

  1. Python Data Structures (Python.org)
  2. Python Algorithms: Mastering Basic Algorithms in the Python Language
  3. GeeksforGeeks Python Data Structures

Try solving problems that involve these data structures on platforms like HackerRank, LeetCode, or CodeSignal. Remember, the key to mastering data structures is practice and understanding the underlying concepts. Happy coding!

Links to Online Resources for Further Reading and Understanding

Here are some additional online resources that you may find useful for enhancing your understanding of Stacks, Queues, and Linked Lists:

  1. Text Resources:
  1. Interactive Learning:
  1. Coding Practice:
  1. Videos and Lectures:

Remember to complement your learning with consistent practice, as it is the key to mastering data structures and algorithms. Happy learning!