DSA_Reviewer.pdf

BULACAN STATE UNIVERSITY COLLEGE OF INFORMATION AND COMMUNICATIONS TECHNOLOGY IT 201 DATA STRUCTURES AND ALGORITHM AUTHORS: LESTER PHIL M. CRUZ, MSCpE TERESITA G. DELA CRUZ RALPH JEROME C. ESPONILLA DONNA Q. FERNANDO,...

BULACAN STATE UNIVERSITY COLLEGE OF INFORMATION AND COMMUNICATIONS TECHNOLOGY IT 201 DATA STRUCTURES AND ALGORITHM AUTHORS: LESTER PHIL M. CRUZ, MSCpE TERESITA G. DELA CRUZ RALPH JEROME C. ESPONILLA DONNA Q. FERNANDO, MSIT MARK DAVID P. OTAYDE MARK JUSTINE A. ROQUE 1 IT 201: DATA STRUCTURES AND ALGORITHM CONTENTS UNIT 01 Data Structures LESSON 1: Introduction to Data Structures and Algorithm 7 4 Pretest 8 Use of Data 8 Data Structure 8 Algorithm 9 Classification of Data Structures 11 Activity LESSON 2: Linked Lists 12 13 The Use of Lists 13 Linked Lists Basic Concepts 14 Pointers 16 Algorithm for Creating a Linked List 16 Algorithm for Adding a Node 17 Algorithm for Displaying a Node 19 Linked Lists Basic Operations 20 Traverse a Linked List 20 Insert a Node to a Linked List 21 Delete a Node from a Linked List 24 Types of Linked Lists 30 Assignment 1 32 Activity 1 34 Activity 2 2 IT 201: DATA STRUCTURES AND ALGORITHM  LESSON 3: Stacks 37 38 Introduction to Stacks and its Concepts 41 Stacks Using Class 44 Private and Public 44 Data Member and Member Functions 44 Constructors and Deconstructors 47 Algorithm for Inserting an Element in the Stack 47 Algorithm for Deleting an Element in the Stack 51 Stacks Using Arrays 54 Stacks Using Linked Lists 57 Activity LESSON 4: Queues 58 59 Pretest 61 What is a Queue? 63 Difference Between Queues and Stacks 63 Basic Operations 65 Applications of Queues 66 Enqueue and Dequeue Operations 68 Algorithm for Enqueue and Dequeue Operations 73 Circular Queues 76 Algorithm for Circular Queues 83 Priority Queues 90 Activity 1 91 Activity 2 93 Activity 3 95 Activity 4 98 Post-Test for Unit 1 106 Suggested Readings 3 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 02 Algorithms LESSON 1: Search Algorithms 107 108 Pretest 109 Search Algorithms 109 Linear Search 110 Binary Search 111 Interpolation Search 113 Reflection/Learning Insights 114 Activity LESSON 2: Sorting Algorithms 115 116 Sorting Algorithms 116 Bubble Sort 119 Selection Sort 123 Insertion Sort 125 Quick Sort 129 Merge Sort 133 Activity 1 134 Activity 2 137 Post-test for Unit 2 UNIT 03 Additional Topics on Data Structures LESSON 1: Hash Tables and Binary Trees 142 143 Pretest 144 Hash Tables 146 Hash Function 146 Hash Collision 147 Algorithm for Hashing a Key 4 IT 201: DATA STRUCTURES AND ALGORITHM  147 Algorithm for Rehashing a Key 147 Algorithm for Adding Data into Hash Tables 151 Algorithm for Deleting Data from Hash Tables 156 Introduction to Binary Trees 157 Algorithm for Printing-out Values of a Binary Tree 157 Algorithm for Searching in a Binary Tree 158 Algorithm for Inserting Values in a Binary Tree 160 Assignment 1 161 Assignment 2 162 Activity 1 163 Activity 2 165 Post-test for Unit 3 167 Glossary 5 IT 201: DATA STRUCTURES AND ALGORITHM UNIT 1: Data Structures UNIT 1 DATA STRUCTURES In this unit we will discuss about structuring and organizing data - a fundamental aspect of designing and implementing computing software. Data structures determine the logical linkages between data elements and affect the physical processing of data. All software programs use data structures of some kind; many use files as well. Data structure knowledge is required design and develop software for either commercial or technical applications. It also required design and develop system software like operating systems, database management systems, and language compilers. Data structure and algorithms are primary factors that determine program performance. The first part of this unit discusses the different type of data structure and tells how they are managed by computer programs. This introductory chapter should give you an understanding of what a data structure is and why data structures are important in information systems, as well as general knowledge of several simple data structures. 6 3 IT 201: DATA STRUCTURES AND ALGORITHM UNIT 1: Data Structures e) LESSON 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHM OBJECTIVES: At the end of this lesson, the students will be able to: ▪ Explain the concept of Data. ▪ Classify the different types of Data Structure. ▪ Explain the properties and characteristics of an Algorithm 7 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 1: Data Structures Lesson 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHM The Use of Data Let us consider the role data plays in the events of any organization and implementation of data structure in C++. Data represents the overall resource of the organization, it can exist in different forms; such as numbers and characters/text on pieces of paper, as bits and bytes stored in computer memory, or as raw facts stored in a person's mind. They are aggregated and summarized in various meaningful ways to form information. A list may implement only a subset of the different operations. The outline of a listing is extremely general, and it will be implemented during several various ways, using the array method. And linked list methods are the two general implementation methods in implementing a list data structure. Data Structure A Data Structure is a way of collecting and organizing elements or items of data. It is an arrangement of data in a computer’s memory in such a way that it can access quickly to the processor for the required calculations. Data Structure must be seen in a logical concept that must address two fundamental concerns: 1) How data will be stored. Data type is a way to classify various types of data such as integer, string, etc. which determines the values that can be used to store the corresponding type of data, and 2) What operations will be performed on these data. The data in the data structures are processed by particular operations. The particular data structure was chosen largely depends on the frequency of the operation that needs to be performed on the data structure; traversing, searching, insertion, deletion, sorting, and merging. The functional definition of a data structure should be independent of its implementation since data structure is the scheme for data organization. The functional definition of a data structure is known as Abstract Data Type which is independent of implementation. Algorithm Along with data structures discussion, problem-solving is done with the help of data structures and algorithms. An algorithm is a finite set of instructions or procedures, written in order, to solve a certain predefined task. In programming, algorithms are implemented in the form of methods or functions. The algorithm is not a program, it is the main logic or solution to the problem, which can be stated as pseudocode. Every algorithm must solve complex problems using the following: 1) define the problem, 2) design the algorithm, and 3) solve the problem. 8 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 1: Data Structures The following are the characteristics of a good algorithm; 1. Input and output should be well-defined, 2. All steps should be clear and definite, 3. Solutions should be effective to problems 4. It should be feasible with the available resources. 5. It should have step-by-step directions, which should be independent of any programming code. An algorithm is effective and fast if it takes a lesser amount of time to perform and if it consumes less memory space. The following properties are the basis of its performance: 1. Time Complexity It is a way to signify the amount of time needed by the program to run to completion. 2. Space Complexity It is the amount of memory space necessary by the algorithm, during the course of its execution. Space complexity must be taken extremely for multi-user systems and in situations where limited memory is available. An algorithm generally requires space for the following components: Instruction Space - space required to store the executable version of the program. This space is static but differs depending upon the number of lines of code in the program Data Space - space required to store all the constants and variables value. Environment Space - space necessary to store the environment information needed to restart the suspended function. Classification of Data Structure A data structure is a type of data that can be categorized by its organization and the operations that are defined on it. Data structures are also known as data types. 9 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 1: Data Structures Data Structure Primitive Data Non-Primitive Data Structure Structure Integer Float Pointer Boolean Characters String Array List Record File s String s s Linear Non-linear Stack Queues Linked List Trees Graph s Figure 1.1 Data Structure Organization Data structures are divided into two types; 1. Primitive data structures A data structure that cannot be decomposed to other data structures. Integers, float, pointers, Booleans, and characters are under this type. These primitive data structures are the basis for the discussion of a more sophisticated data structure. 2. Non-primitive data structures It is a more complicated data structure and is derived from one or more primitive data structures. The simple data structures built from primitives are strings, arrays, lists, records, and files. A simple data structure can be combined in various ways to form more complex structures. The two important kinds of more complex data structures; 1. Linear data structure Elements are connected and accessed in sequential order by means of logically or in sequence memory locations. Example: stacks, queues, and linked list 2. Non-linear data structure Data items are not arranged in sequential order. Example: trees and graphs. 10 IT 201: DATA STRUCTURES AND ALGORITHM UNIT 1: Data Structures 11 IT 201: DATA STRUCTURES AND ALGORITHM LESSON 2: LINKED LISTS OBJECTIVES: By the end of this lesson, the students will be able to: Identify and Understand algorithm in creating Linked List, adding a node and displaying a node. Create a program for Singly Linked Lists and Doubly Linked Lists. Apply the Basic Operations of Linked List for Singly Linked List and Doubly Linked List. 12 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 1: Data Structures Lesson 2: LINKED LISTS The Use of LISTS A list is a collection of an ordered sequence of items. It might have properties, for example, being sorted or unsorted, having duplicate or being unique values. The most significant part about list structures is that data are arranged in order. Ordering means there is a thought there is a first item, a second item, and so on. Some operations of a list are adding, removing, and sorting. A list may implement only a subset of the different operations. The outline of a listing is extremely general, and it will be implemented during several various ways, using the array method, and linked list methods are the two general implementation methods in implementing a list data structure. The difference between these two ways of list implementation is that arrays are stored in computer memory consecutively and can accessed directly to any particular item with the use of its index number and the sorted list can be searched using binary search. Using a linked list, data are not stored consecutively in memory locations, so an oversized block of contiguous memory is not required even for storing large amounts of data. Each bit of information requires the storage of an additional pointer. However, the number of additional data is expounded on a number of things within the list already. A linked list cannot be searched using binary search as direct access to nodes don't seem to be available. Linked Lists Basic Concepts A Linked List is a data structure that stores elements (called nodes) in a sequence. Unlike arrays, elements in a linked list are not stored in contiguous memory locations. Instead, each element points to the next one, forming a chain-like structure. Why Use a Linked List? Dynamic Size: Unlike arrays with a fixed size, linked lists can grow or shrink dynamically. Efficient Insertions and Deletions: Linked lists make it easier to insert or delete elements, especially in large datasets. 36 IT 201: DATA STRUCTURES AND ALGORITHM Understanding the Structure of a Linked List? Each element in a linked list is called a Node. A node typically contains: Data: The value the node holds. Next: A reference (or pointer) to the next node in the list. Visualizing a Linked List A linked list looks like a series of connected nodes: Photo lifted from: tutorialspoint.com Figure 2.1 Linked Lists Figure 2.1 The figure represents the linked list with a pointer to the first node of the list called Head. Each node has a link to the next node of the list. The last node has a Null pointer, which indicates that there is no next node. Each node actually has two parts: data contents and the pointer field. Each node is a record data structure. Algorithms for Creating a Linked List Objective: To create an empty linked list. 1. Create a class Node with attributes data and next. 2. Create a class LinkedList with a head pointer initialized to null. 3. Define the necessary methods (add, display, etc.) in the LinkedList class. Algorithm: 1. Initialize head as null 2. Create a Node class with data and next fields 3. Create a LinkedList class with head as its only field 4. Define methods to operate on the list 36 IT 201: DATA STRUCTURES AND ALGORITHM. The Node Class public class Node { int data; // The data the node holds Node next; // A reference to the next node Node class represents each element in the linked list, storing data and a reference to the next node. The Node class is a fundamental building block of a linked list. Each node in a linked list contains two key parts: Data (int data): This stores the value or information that the node holds. Next (Node next): This is a reference (or pointer) to the next node in the sequence. It links one node to another, forming the chain that constitutes the linked list. Constructor of a Node Class // Constructor to create a new node public Node(int data) { this.data = data; this.next = null; // By default, the next pointer is null } } The constructor initializes a new node. It takes an integer data as a parameter, which is assigned to the node's data field. The next field is initialized to null, meaning this node doesn't point to any other node when it's first created. This is typical when a node is newly created and not yet linked to another node. LinkedList Class public class LinkedList { Node head; // The head of the linked list, initially null // Constructor to create an empty linked list public LinkedList() { head = null; // The head is initially null, indicating an empty list } } LinkedList class manages the overall list, with the head serving as the starting point. The LinkedList class is a container for managing the sequence of nodes. It typically provides methods to manipulate the nodes, such as adding, removing, or searching for elements. 36 IT 201: DATA STRUCTURES AND ALGORITHM Attributes and Constructor of the LinkedList Class Head (Node head): This is the most crucial attribute of the LinkedList class. It refers to the first node in the list. Initially, when the linked list is empty, head is set to null. The constructor of the LinkedList class initializes an empty linked list by setting head to null. This code demonstrates the creation of an empty linked list. public class Node { int data; // The data the node holds Node next; // A reference to the next node // Constructor to create a new node public Node(int data) { this.data = data; this.next = null; // By default, the next pointer is null } } public class LinkedList { Node head; // The head of the linked list, initially null // Constructor to create an empty linked list public LinkedList() { head = null; // The head is initially null, indicating an empty list } } How the Classes Work Together Node Instances: Each time you create a new Node, you create a discrete element that can hold data and point to another node. LinkedList Structure: The LinkedList class manages these nodes. The head serves as the starting point, and each node's next reference points to the next node in the list. If head is null, the list is empty. Visualizing the Structure Initially, the linked list is empty (head is null). When a new node is added, the head points to that node. As more nodes are added, the next field of each node points to the following node in the sequence, creating a chain. 36 IT 201: DATA STRUCTURES AND ALGORITHM Algorithms for Adding a Node Objective: To add a new node at the end of the linked list. 1. Create a new node with the given data. 2. If the list is empty (head is null), set the new node as the head. 3. Otherwise, traverse the list to find the last node. 4. Link the last node to the new node. Algorithm: 1. Create a new node with given data 2. If head is null, set head to new node 3. Else a. Traverse the list to find the last node b. Set the last node's next to the new node LinkedList Class Overview public class LinkedList { Node head; // The head of the linked list // Constructor to create an empty linked list public LinkedList() { head = null; // The head is initially null, indicating an empty list } The LinkedList class manages a sequence of nodes, where each node contains data and a reference to the next node in the list. Head (Node head): The head is a reference to the first node in the linked list. Initially, it's set to null, indicating that the list is empty. The constructor initializes an empty linked list by setting head to null. Adding a Node to the end of the List // Method to add a node at the end of the list public void add(int data) { Node newNode = new Node(data); // Create a new node with the given data The add method is responsible for adding a new node to the end of the linked list. Creating a New Node: The method begins by creating a new node with the given data. The newNode is an instance of the Node class, where data is passed to the Node constructor, initializing the data field of the node, and next is set to null (as per the Node constructor's definition). 36 IT 201: DATA STRUCTURES AND ALGORITHM  if (head == null) { // If the list is empty, the new node becomes the head head = newNode; } else { Node current = head; while (current.next != null) { // Traverse to the end of the list current = current.next; } current.next = newNode; // Link the last node to the new node } } } Case 1: Empty List: The method checks if the linked list is empty by seeing if head is null. If it is, the new node becomes the first node in the list, and head is updated to point to this new node. Case 2: Non-Empty List: If the list is not empty (i.e., head is not null), the method needs to find the last node in the list. ▪ Traversing the List: It starts by setting a temporary variable current to head and then iteratively moves through the list using current = current.next until it finds the last node (where current.next is null). ▪ Adding the New Node: Once the last node is found, the next field of that node is updated to point to the newly created node (newNode), effectively adding the new node to the end of the list. This code adds a node to the end of the linked list. public class LinkedList { Node head; // The head of the linked list // Constructor to create an empty linked list public LinkedList() { head = null; // The head is initially null, indicating an empty list } // Method to add a node at the end of the list public void add(int data) { Node newNode = new Node(data); // Create a new node with the given data if (head == null) { // If the list is empty, the new node becomes the head head = newNode; } else { Node current = head; while (current.next != null) { // Traverse to the end of the list current = current.next; } current.next = newNode; // Link the last node to the new node } } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  How the add Method Works in Context First Node: When the list is empty, the first call to add will set the head to the new node, establishing the first element in the list. Subsequent Nodes: Each additional call to add will traverse the list to find the last node and link it to the new node, extending the list by one element at the end. Algorithms for Displaying the Linked List Objective: To display all the nodes in the linked list from the head to the end. 1. Start from the head node. 2. Traverse through each node until you reach the end (next is null). 3. Print the data of each node. Algorithm: 1. Start from the head node 2. While the current node is not null a. Print current node's data b. Move to the next node 3. Print "null" to indicate the end of the list Purpose of the ‘display’ Method This code displays all the nodes in the linked list from the head to the end. // Method to display the linked list public void display() { Node current = head; while (current != null) { // Traverse the list System.out.print(current.data + " -> "); current = current.next; } System.out.println("null"); // End of the list } } The display method is used to visually represent the linked list by printing the data stored in each node and showing how each node points to the next one. 36 IT 201: DATA STRUCTURES AND ALGORITHM Step-by-Step Breakdown of the display Method: 1. Initialize the Traversal Node current = head; The method starts by creating a temporary variable current and initializing it to the head of the linked list. This variable will be used to traverse the list. 2. Traverse the Linked List while (current != null) { // Traverse the list System.out.print(current.data + " -> "); current = current.next; } Condition (current != null): The while loop continues as long as current is not null, meaning there are still nodes left to process. Printing the Data: Inside the loop, current.data is printed, followed by " -> " to indicate that this node points to the next node in the sequence. Moving to the Next Node: After printing the current node's data, current = current.next updates current to point to the next node in the list. This effectively moves the traversal forward by one node. 3. End of the List System.out.println("null"); // End of the list When the loop finishes (meaning current is null), "null" is printed. This indicates the end of the linked list, as null is what the next reference of the last node in the list would point to. 36 IT 201: DATA STRUCTURES AND ALGORITHM EXAMPLE: Create a linked list that stores student information such as Student ID, Name, and Grade. The linked list should have the following functionalities: Add a student to the list. Display all students in the list. ALGORITHM: a. Define the Node Structure 1. Create a StudentNode class to represent each node in the linked list. 2. Each node should contain: o Student ID o Name o Grade o next (a reference to the next node) b. Add a Student to the List 1. Create a StudentLinkedList class. 2. Implement the addStudent(int id, String name, double grade) method: o Create a new StudentNode. o If the list is empty, make the new node the head. o Otherwise, traverse to the end of the list and link the new node. c. Display the Student Information 1. Implement the displayStudents() method: o Traverse the list from the head and print the details of each student. 36 IT 201: DATA STRUCTURES AND ALGORITHM Source Code: a. StudentNode Class public class StudentNode { int id; // Student ID String name; // Student Name double grade; // Student Grade StudentNode next; // Reference to the next node // Constructor to initialize the student node public StudentNode(int id, String name, double grade) { this.id = id; this.name = name; this.grade = grade; this.next = null; // The next node is initially null } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  b. StudentLinkedList Class public class StudentLinkedList { StudentNode head; // The head of the linked list // Constructor to create an empty linked list public StudentLinkedList() { head = null; // The head is initially null, indicating an empty list } // Method to add a student to the list public void addStudent(int id, String name, double grade) { StudentNode newNode = new StudentNode(id, name, grade); // Create a new student node if (head == null) { // If the list is empty, the new node becomes the head head = newNode; } else { StudentNode current = head; while (current.next != null) { // Traverse to the end of the list current = current.next; } current.next = newNode; // Link the last node to the new node } } // Method to display all students in the list public void displayStudents() { StudentNode current = head; while (current != null) { // Traverse the list System.out.println("Student ID: " + current.id + ", Name: " + current.name + ", Grade: " + current.grade); current = current.next; } } } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  c. Main Class public class Main { public static void main(String[] args) { StudentLinkedList studentList = new StudentLinkedList(); // Adding students to the list studentList.addStudent(1, "Thess”, 85.5); studentList.addStudent(2, "Esmie", 92.0); studentList.addStudent(3, "Zeny", 78.0); // Displaying all students System.out.println("All Students:"); studentList.displayStudents(); // Deleting a student by ID System.out.println("\nDeleting student with ID 2:"); studentList.deleteStudent(2); // Displaying all students after deletion System.out.println("\nAll Students after deletion:"); studentList.displayStudents(); } } 36 IT 201: DATA STRUCTURES AND ALGORITHM Basic Operations on a Linked List Having knowledge about the basic concepts of a linked list, in this part of the module, you will learn basic operations on a linked list; traverse, insert, delete, and other operations like; searching, sorting and merging will discuss in the next unit of this module. Also, you will see the implementation of these operations of the linked list using Java. Insert Node to a Linked List There are three ways that occur when inserting elements in a linked list: 1. Insertion At the Beginning: Add a node at the start of the list. At the End: Add a node at the end of the list. At a Specific Position: Insert a node at a given position in the list. Inserting at the Beginning (insertAtBeginning): A new node is created and its next pointer is set to the current head of the list. The head of the list is then updated to point to this new node. Algorithm: 1. Create a new node with the given data. 2. Set the next pointer of the new node to the current head of the list. 3. Update the head of the list to be the new node. public void insertAtBeginning(int data) { Node newNode = new Node(data); // Step 1 newNode.next = head; // Step 2 head = newNode; // Step 3 } Inserting at the End (insertAtEnd): A new node is created. If the list is empty, the head is set to this new node. Otherwise, the list is traversed until the last node is found, and the new node is added as the next node of the last node. Algorithm: 1. Create a new node with the given data. 2. If the list is empty (i.e., head is null), set the head to the new node. 3. Start from the head 4. Otherwise, traverse the list to find the last node. 5. Set the next pointer of the last node to the new node. 36 IT 201: DATA STRUCTURES AND ALGORITHM  public void insertAtEnd(int data) { Node newNode = new Node(data); // Step 1 if (head == null) { // Step 2: Check if the list is empty head = newNode; // } else { Node temp = head; // Step 3: while (temp.next != null) { // Step 4: temp = temp.next; } temp.next = newNode; // Step 5: Set the last node's next to the new node } } Inserting at a Specific Position (insertAtPosition): A new node is created. If the position is 0, the new node is inserted at the beginning. Otherwise, the list is traversed to the node just before the specified position, and the new node is inserted by adjusting the pointers accordingly. Algorithm: 1. Create a new node with the given data. 2. If the position is 0, set the next pointer of the new node to the current head and update the head to the new node. 3. Otherwise, traverse the list to find the node at the (index - 1) position. 4. Set the next pointer of the new node to the next pointer of the current node. 5. Set the next pointer of the current node to the new node. public void insertAtPosition(int index, int data) { Node newNode = new Node(data); // Step 1: Create a new node with the given data if (index == 0) { // Step 2: Check if the position is the beginning newNode.next = head; // Step 3: Set the new node's next to the current head head = newNode; // Step 4: Update the head to be the new node } else { Node temp = head; // Step 5: Start from the head for (int i = 0; i < index - 1; i++) { // Step 6: Traverse to the (index-1)th node if (temp == null) { // Step 7: Check if index is out of bounds System.out.println("Index out of bounds"); return; } temp = temp.next; } newNode.next = temp.next; // Step 8: Set the new node's next to the current node's next temp.next = newNode; // Step 9: Set the current node's next to the new node } } 36 IT 201: DATA STRUCTURES AND ALGORITHM A sample program to implement basic operations in a linked list is shown below: class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head; // Insert a node at the beginning of the list public void insertAtBeginning(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } // Insert a node at the end of the list public void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; } } // Insert a node at a specific position public void insertAtPosition(int index, int data) { Node newNode = new Node(data); if (index == 0) { // Inserting at the beginning newNode.next = head; head = newNode; return; } Node temp = head; for (int i = 0; i < index - 1; i++) { if (temp == null) { System.out.println("Index out of bounds"); return; } temp = temp.next; } newNode.next = temp.next; temp.next = newNode; } 36 IT 201: DATA STRUCTURES AND ALGORITHM  // Display the linked list public void display() { Node temp = head; while (temp != null) { System.out.print(temp.data + " -> "); temp = temp.next; } System.out.println("null"); } } public class Main { public static void main(String[] args) { LinkedList list = new LinkedList(); // Inserting nodes list.insertAtBeginning(10); // List: 10 list.insertAtEnd(30); // List: 10 -> 30 list.insertAtPosition(1, 20); // List: 10 -> 20 -> 30 list.insertAtBeginning(5); // List: 5 -> 10 -> 20 -> 30 list.insertAtEnd(40); // List: 5 -> 10 -> 20 -> 30 -> 40 // Display the list System.out.println("Linked List:"); list.display(); } } 36 IT 201: DATA STRUCTURES AND ALGORITHM Delete Node from a Linked List There are three ways that occur when deleting elements from a linked list: 2. Deletion From the Beginning: Remove the first node. From the End: Remove the last node. From a Specific Position: Remove a node from a given position. Deleting at the Beginning (deleteAtBeginning): Removes the first node in the linked list. This operation updates the head of the list to the next node, effectively removing the current head node from the list. Algorithm: 1. Check if the List is Empty: o If head is null, print "List is empty" and exit. 2. Update Head: o Set head to head.next. This removes the first node by making the second node the new head. public void deleteAtBeginning() { // Check if the list is empty if (head == null) { System.out.println("List is empty"); return; } // Set head to the next node head = head.next; } Deleting at the End (deleteAtEnd) Removes the last node in the linked list. This involves traversing the list to find the second-to-last node, then updating its next pointer to null to remove the reference to the last node. Algorithm: 1. Check if the List is Empty: o If head is null, print "List is empty" and exit. 2. Check if There is Only One Node: o If head.next is null, set head to null to remove the only node. 3. Traverse to the Second-to-Last Node: o Initialize temp as head. o Traverse the list until temp.next.next is null (i.e., until temp is the second-to-last node). 4. Remove the Last Node: o Set temp.next to null. 36 IT 201: DATA STRUCTURES AND ALGORITHM  public void deleteAtEnd() { // Check if the list is empty if (head == null) { System.out.println("List is empty"); return; } // Check if there is only one node if (head.next == null) { head = null; return; } // Traverse to the second-to-last node Node temp = head; while (temp.next.next != null) { temp = temp.next; } // Remove the last node temp.next = null; } Deleting at a Specific Position Removes a node at a specific index in the linked list. This requires traversing the list to the node just before the specified position, then adjusting the pointers to bypass the node at that position. If the index is 0, it simply updates the head to the next node. Algorithm: 1. Check if the List is Empty: o If head is null, print "List is empty" and exit. 2. Check if Deleting the Head Node: o If index is 0, set head to head.next to remove the head node. 3. Traverse to the Node Before the Specified Position: o Initialize temp as head. o Traverse the list to the node at position (index - 1). o If temp is null or temp.next is null during traversal, print "Index out of bounds" and exit. 4. Remove the Node at the Specified Position: o Set temp.next to temp.next.next to skip the node at the specified position. 36 IT 201: DATA STRUCTURES AND ALGORITHM  public void deleteAtPosition(int index) { // Check if the list is empty if (head == null) { System.out.println("List is empty"); return; } // Check if deleting the head node if (index == 0) { head = head.next; return; } // Traverse to the node before the specified position Node temp = head; for (int i = 0; i < index - 1; i++) { if (temp == null || temp.next == null) { System.out.println("Index out of bounds"); return; } temp = temp.next; } // Remove the node at the specified position temp.next = temp.next.next; } Traverse a Linked List The operation of processing each element in the list is known as traversal. The concept of traversing list is to step through the entire list and display all elements one by one. Algorithm for Traversing a Linked List 1. Initialize: Start from the head of the linked list. 2. Traverse: Use a loop to visit each node until you reach the end of the list. o Print/Process Node Data: Access the data in the current node and print it or perform other operations as needed. o Move to Next Node: Update the current node reference to the next node in the list. 3. End of List: When the next node is null, exit the loop. 36 IT 201: DATA STRUCTURES AND ALGORITHM  // Method to traverse the linked list public void traverse() { Node currentNode = head; // Initialize currentNode to head of the list while (currentNode != null) { // Loop until the end of the list System.out.print(currentNode.data + " -> "); // Print current node's data currentNode = currentNode.next; // Move to the next node } System.out.println("null"); // End of list } Explanation: currentNode = head;: Start traversal from the head of the list. while (currentNode != null): Continue the loop until reaching the end of the list. System.out.print(currentNode.data + " -> ");: Print the data of the current node. currentNode = currentNode.next;: Move to the next node. System.out.println("null");: Print null to indicate the end of the list. Types of Linked Lists 1. Singly Linked List 2. Doubly Linked List 3. Circular Linked List Singly Linked List A singly linked list is a type of linked list where each node has a single pointer to the next node in the sequence. This allows traversal in only one direction (forward). Node Structure: class Node { int data; // Data part of the node Node next; // Pointer to the next node Node(int data) { this.data = data; this.next = null; } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  Algorithm and Sample Code: Inserting at the End: public void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; } } Traversing the List: public void traverse() { Node currentNode = head; while (currentNode != null) { System.out.print(currentNode.data + " -> "); currentNode = currentNode.next; } System.out.println("null"); } Explanation: Inserting at the End: Start from the head and traverse to the last node. Set the last node's next to the new node. Traversing the List: Start from the head and move through each node until reaching the end (null), printing each node's data. Doubly Linked List A doubly linked list is a type of linked list where each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions. 36 IT 201: DATA STRUCTURES AND ALGORITHM  Node Structure: class DoublyNode { int data; DoublyNode next; DoublyNode prev; DoublyNode(int data) { this.data = data; this.next = null; this.prev = null; } } Algorithm and Sample Code: Inserting at the End: public void insertAtEnd(int data) { DoublyNode newNode = new DoublyNode(data); if (head == null) { head = newNode; } else { DoublyNode temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; newNode.prev = temp; } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  Traversing the List (Forward): public void traverseForward() { DoublyNode currentNode = head; while (currentNode != null) { System.out.print(currentNode.data + " "); currentNode = currentNode.next; } System.out.println("null"); } Traversing the List (Backward): public void traverseBackward() { if (head == null) return; // Move to the last node DoublyNode currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } // Traverse backward while (currentNode != null) { System.out.print(currentNode.data + " "); currentNode = currentNode.prev; } System.out.println("null"); } 36 IT 201: DATA STRUCTURES AND ALGORITHM  Explanation: Inserting at the End: Similar to singly linked list, but also update the prev pointer of the new node and the last node. Traversing Forward: Start from the head and move through each node, printing data. Traversing Backward: Move to the end and traverse backward using the prev pointers. Circular Linked List A circular linked list is a type of linked list where the last node points back to the first node, creating a circular structure. Node Structure: class CircularNode { int data; CircularNode next; CircularNode(int data) { this.data = data; this.next = null; } } Algorithm and Sample Code: Inserting at the End: public void insertAtEnd(int data) { CircularNode newNode = new CircularNode(data); if (head == null) { head = newNode; newNode.next = head; // Point to itself } else { CircularNode temp = head; while (temp.next != head) { temp = temp.next; } temp.next = newNode; newNode.next = head; } } 36 IT 201: DATA STRUCTURES AND ALGORITHM  Traversing the List: public void traverse() { if (head == null) return; CircularNode currentNode = head; do { System.out.print(currentNode.data + " -> "); currentNode = currentNode.next; } while (currentNode != head); System.out.println("..."); } Explanation: Inserting at the End: Traverse to the node pointing to the head and update its next pointer to the new node. The new node’s next should point to the head. Traversing the List: Start from the head and continue until you return to the head, printing each node’s data. 36 IT 201: DATA STRUCTURES AND ALGORITHM  UNIT 1: Data Structures Lesson 3: STACKS Introduction to Stacks and Its Concept A stack is an abstract data type that serves as a collection of elements. It is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to stack will be the first one to be removed. It has two fundamental operations - Push and Pop. Push adds an element to the collection and Pop removes the most recently added element that was not yet removed. All the insertion and deletion of elements happen only from one side of the stack, which is referred to as the Top. Figure 3.1 Stack The manner in which elements come out of the stack gives definition to its alternative name: LIFO (Last In First Out) or FILO (First In Last Out). The name “stack” for this type of structure comes from the analogy to a set of physical items stacked on top of each other. This structure makes it easy to delete an element on top of the stack, while getting to an element deeper in the stack may require deleting multiple other elements first. There are many real-life examples of a stack. The simplest one could be the plates of a self-service cafe, that are stacked over one another. The plate which is at the top is the first one to be removed, and the plate which has been placed at the bottom most position remains in the stack for the longest period of time. So it can be simply seen to follow LIFO/FILO order. 38  UNIT 1: Data Structures Figure 3.2 Push a plate When a customer comes along and takes a plate, new plates comes on top of the stack to replace it. Figure 3.2 Pop a plate 39 UNIT 1: Data Structures A similar mechanism in action in shipment in a cargo, stack of coins, stack of chairs, stack of neatly folded shirts, etc. Figure 3.3 Real-life examples of stack Conceptually, a stack is simple: a data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack; the only element that can be removed is the element that was at the top of the stack. Stacks have some useful terminology associated with them: Push to add an element to the stack Pop to remove an element from the stack IsEmpty to check if the stack is empty IsFull to check if the stack is full (usually relevant for array-based stacks) Peek or Top views the top element of the stack without removing it. LIFO Refers to the last in, first out behavior of the stack FILO Equivalent to LIFO 40  UNIT 1: Data Structures Understanding Classes in Java Class A class in Java is a blueprint for creating objects. It encapsulates data and methods that operate on that data into a single unit. A class defines the form of an object by specifying its attributes (data) and behaviors (methods) Components of a Class: 1. Data(Fields/Attributes) Store information about the object Ex. In a car class, fields might include make, model and year. 2. Constructor Initialize objects. It is called when an instance of the class is created. Ex. The constructor Car(String make, String model, int year) initializes the make, model, and year fields. 3. Methods Define behaviors or actions that the object can perform. Ex. A drive() method in the Car class could simulate driving the car. Defining the Class in Java public class ClassName { // Data (variables) private int someData; // Constructor (optional) public ClassName(int initialData) { this.someData = initialData; } // Method (function) public void someMethod() { // Method implementation } } Data: Variables or fields that store the state of an object. Constructor: A special method used to initialize objects. Methods: Functions that define the behavior of the class. 41 Algorithm for Creating a Stack in Java The stack can be implemented using different data structures, such as arrays or linked lists. Here's a step-by-step algorithm for creating a stack using an array in Java: 1. Create a Stack Class Define a stackArray to hold the elements. Keep a top pointer to track the index of the top element. Define the maximum size of the stack (maxSize). 2. Push Operation Check if the stack is full. If not full, increment the top pointer and add the element at the new top position. 3. Pop Operation Check if the stack is empty. If not empty, return the element at the top position and decrement the top pointer. 4. Peek Operation Return the element at the top without removing it (if the stack is not empty). 5. isEmpty Operation Check if top == -1. If true, the stack is empty. 6. isFull Operation Check if top == maxSize - 1. If true, the stack is full. Sample Java Code Implementation Using an Array class Stack { private int[] stackArray; private int top; private int maxSize; // Constructor to initialize the stack with a given size public Stack(int size) { maxSize = size; stackArray = new int[maxSize]; // Create an array for the stack top = -1; // Top is -1 when the stack is empty } // Method to add an element to the stack (Push) public void push(int value) { if (isFull()) { System.out.println("Stack is full. Cannot push " + value); } else { stackArray[++top] = value; // Increment top and add value } } // Method to remove an element from the stack (Pop) public int pop() { if (isEmpty()) { System.out.println("Stack is empty. Nothing to pop."); return -1; // Return -1 or some error code } else { return stackArray[top--]; // Return the value at the top and decrement top } } 42 // Method to view the top element (Peek) public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; // Return -1 or some error code } else { return stackArray[top]; // Return the top element without removing it } } // Method to check if the stack is empty public boolean isEmpty() { return (top == -1); // True if top is -1 } // Method to check if the stack is full public boolean isFull() { return (top == maxSize - 1); // True if top reached maxSize - 1 } // Method to get the current size of the stack public int size() { return top + 1; // The number of elements in the stack } } // Testing the Stack Implementation public class StackDemo { public static void main(String[] args) { Stack stack = new Stack(5); // Create a stack of size 5 // Push elements to the stack stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); // Display the top element System.out.println("Top element is: " + stack.peek()); // Pop elements from the stack System.out.println("Popped element: " + stack.pop()); System.out.println("Popped element: " + stack.pop()); // Check the size of the stack System.out.println("Current stack size: " + stack.size()); // Check if the stack is empty System.out.println("Is stack empty? " + stack.isEmpty()); } } 43 Explanation of the Code: 1. Stack Class: o Contains the core methods to handle stack operations: push(), pop(), peek(), isEmpty(), isFull(), and size(). o top keeps track of the top element in the stack. o stackArray stores the stack elements. 2. push(): o Before adding an element, it checks if the stack is full using the isFull() method. o If the stack is not full, it increments top and places the element in the stack. 3. pop(): o It first checks if the stack is empty using the isEmpty() method. o If it's not empty, it removes the top element and decrements the top. 4. peek(): o It returns the element at the top without removing it. This operation is useful when you just need to view the top element. 5. isEmpty() and isFull(): o These methods help determine the current state of the stack, whether it's full or empty. 6. size(): o This method returns the current number of elements in the stack. Stack Implementation Using a Linked List Here is another way to implement a stack, this time using a linked list, which can dynamically grow without worrying about array size limitations. class Node { int data; Node next; // Constructor to create a new node public Node(int data) { this.data = data; this.next = null; } } class StackLinkedList { private Node top; // Constructor to initialize the stack public StackLinkedList() { this.top = null; } 44  // Push method to add an element to the stack public void push(int value) { Node newNode = new Node(value); // Create a new node newNode.next = top; // Set the next of the new node to the current top top = newNode; // Set the new node as the top } // Pop method to remove and return the top element public int pop() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } int poppedValue = top.data; top = top.next; // Move the top to the next node return poppedValue; } // Peek method to return the top element without removing it public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Method to check if the stack is empty public boolean isEmpty() { return top == null; // True if top is null } } // Testing the Linked List Stack Implementation public class StackLinkedListDemo { public static void main(String[] args) { StackLinkedList stack = new StackLinkedList(); // Push elements to the stack stack.push(100); stack.push(200); stack.push(300); // Display the top element System.out.println("Top element is: " + stack.peek()); // Pop elements from the stack System.out.println("Popped element: " + stack.pop()); System.out.println("Popped element: " + stack.pop()); // Check if the stack is empty System.out.println("Is stack empty? " + stack.isEmpty()); } } 45 Explanation of Linked List Implementation: Node class represents each element (node) in the linked list. StackLinkedList uses a top pointer to manage the stack. push() inserts a new node at the top of the stack. pop() removes the node from the top of the stack and returns its value. Complete Stack Example with User Input (using array) Stack Class This class includes methods for pushing, popping, peeking, and checking if the stack is empty, along with basic error handling. import java.util.Scanner; // Custom Stack class class Stack { private int maxSize = 10; // Maximum size of the stack private int[] stackArray; // Array to store stack elements private int top; // Index of the top element // Constructor to initialize the stack public Stack() { stackArray = new int[maxSize]; // Create an array of the specified size top = -1; // Initialize the top to -1 (stack is empty) } // Method to push an element onto the stack public void push(int value) { if (top >= maxSize - 1) { System.out.println("Stack Overflow! Unable to push " + value); } else { stackArray[++top] = value; // Increment top and push the value System.out.println(value + " pushed onto stack."); } } // Method to pop an element from the stack public void pop() { if (top == -1) { System.out.println("Stack Underflow! No element to pop."); } else { int poppedValue = stackArray[top--]; // Pop the element and decrement top System.out.println("Popped: " + poppedValue); } } 46 // Method to peek at the top element of the stack public int peek() { if (top == -1) { System.out.println("Stack is empty. No top element."); return -1; // Return -1 to indicate an empty stack } else { return stackArray[top]; // Return the top element } } // Method to check if the stack is empty public boolean isEmpty() { return top == -1; // Return true if the stack is empty, false otherwise } // Method to get the size of the stack public int size() { return top + 1; // Size is top + 1 (since top starts at -1) } } // Main class public class StackDemo { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Stack stack = new Stack(); // Create a new stack instance while (true) { System.out.println("\nStack Operations:"); System.out.println("1. Push"); System.out.println("2. Pop"); System.out.println("3. Peek"); System.out.println("4. Check if Empty"); System.out.println("5. Display Size"); System.out.println("6. Exit"); System.out.print("Enter your choice (1-6): "); int choice = scanner.nextInt(); switch (choice) { case 1: // Push System.out.print("Enter value to push: "); int pushValue = scanner.nextInt(); stack.push(pushValue); break; 47  case 2: // Pop stack.pop(); break; case 3: // Peek int topValue = stack.peek(); if (topValue != -1) { System.out.println("Top element is " + topValue); } break; case 4: // Check if Empty if (stack.isEmpty()) { System.out.println("Stack is empty"); } else { System.out.println("Stack is not empty"); } break; case 5: // Display Size System.out.println("Stack size is " + stack.size()); break; case 6: // Exit System.out.println("Exiting..."); scanner.close(); System.exit(0); break; default: System.out.println("Invalid choice. Please enter a number between 1 and 6."); } } } } Explanation of the Stack Class Methods: push(int value): Adds an element to the top of the stack if it is not full. pop(): Removes the top element from the stack if it's not empty and prints the value. peek(): Displays the value of the top element without removing it. isEmpty(): Returns true if the stack is empty, otherwise false. size(): Returns the number of elements currently in the stack. Flow of the Program: 1. The program displays a menu with various stack operations. 2. The user selects an option, and the appropriate operation is performed. 3. The program loops until the user chooses to exit. 48 Stack implementation using a linked list in Java, with user input to interact with the stack: Code Explanation: Node class: Represents each element in the linked list (stack node). StackUsingLinkedList class: Implements the stack operations (push, pop, peek, isEmpty, size) using a linked list. StackDemo class: Provides a menu for the user to interact with the stack. import java.util.Scanner; // Node class to represent each element in the stack class Node { int data; // Data stored in the node Node next; // Reference to the next node // Constructor to initialize the node with data public Node(int data) { this.data = data; this.next = null; } } // Stack class implementing stack operations using linked list class StackUsingLinkedList { private Node top; // Top of the stack private int size; // Size of the stack // Constructor to initialize an empty stack public StackUsingLinkedList() { this.top = null; this.size = 0; } // Push an element onto the stack public void push(int value) { Node newNode = new Node(value); // Create a new node newNode.next = top; // Point the new node to the current top top = newNode; // Update the top to the new node size++; // Increment the size of the stack System.out.println(value + " pushed onto stack."); } 49 // Pop an element from the stack public void pop() { if (top == null) { System.out.println("Stack Underflow! No element to pop."); } else { System.out.println("Popped: " + top.data); top = top.next; // Move the top to the next node size--; // Decrease the size } } // Peek at the top element of the stack public int peek() { if (top == null) { System.out.println("Stack is empty. No top element."); return -1; } else { return top.data; } } // Check if the stack is empty public boolean isEmpty() { return top == null; } // Get the size of the stack public int size() { return size; } } 50 // Main class to handle user interaction public class StackDemo { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); StackUsingLinkedList stack = new StackUsingLinkedList(); // Create a stack instance while (true) { System.out.println("\nStack Operations:"); System.out.println("1. Push"); System.out.println("2. Pop"); System.out.println("3. Peek"); System.out.println("4. Check if Empty"); System.out.println("5. Display Size"); System.out.println("6. Exit"); System.out.print("Enter your choice (1-6): "); int choice = scanner.nextInt(); switch (choice) { case 1: // Push System.out.print("Enter value to push: "); int pushValue = scanner.nextInt(); stack.push(pushValue); break; case 2: // Pop stack.pop(); break; case 3: // Peek int topValue = stack.peek(); if (topValue != -1) { System.out.println("Top element is " + topValue); } break; 51  case 4: // Check if Empty if (stack.isEmpty()) { System.out.println("Stack is empty"); } else { System.out.println("Stack is not empty"); } break; case 5: // Display Size System.out.println("Stack size is " + stack.size()); break; case 6: // Exit System.out.println("Exiting..."); scanner.close(); System.exit(0); break; default: System.out.println("Invalid choice. Please enter a number between 1 and 6."); } } } } Explanation of Operations: Node class: Each node contains an int data (element) and a Node next (reference to the next node in the stack). StackUsingLinkedList class: o push(): Adds a new node to the top of the stack. o pop(): Removes the node at the top of the stack. o peek(): Returns the value of the top node without removing it. o isEmpty(): Checks if the stack is empty. o size(): Returns the number of nodes in the stack. StackDemo class: Handles user input to perform stack operations. How It Works: 1. The user is presented with a menu that allows them to choose stack operations like push, pop, peek, checking if the stack is empty, and displaying the size. 2. The stack is implemented using a linked list, where each node points to the next node. 3. The program runs in a loop until the user chooses to exit. 52 UNIT 1: Data Structures LESSON 4: QUEUES OBJECTIVES:  Elaborate the purpose and mathematical background of algorithm analysis, particularly queue data structure.  Introduce the idea of Queue Data Structure with real-world examples.  Discuss the operations that can be used to utilize queues.  Apply all the data structures and algorithm concepts using several IDE’s, such as, Code Blocks, Dev C++, Java, etc.  Infuse in the minds of the learners that in each problem a single programmer could develop a unique solution, far different from the other’s solution, but will arrive on the same result.  Let the students be aware of the different IDE’s that they could use in developing a program. IT 201: DATA STRUCTURES AND ALGORITHMS 58  UNIT 1: Data Structures PRETEST WHAT DO YOU ALREADY KNOW? Name: Date: Course & Section: Result: Identification: Select the appropriate answer from the box below, and write the answer on the space provided before the number. Enqueue ispeek() isfull() Queue Tail 1 FIFO 2 Dequeue Head isempty() 1. Defined as a line of people or things waiting for something. 2. Also known as the idea of “first-come, first-served” method. 3. Another term to the “front” element from a queue. 4. The removal of an element from a queue is called as? 5. Another term to the “rear” element from a queue. 6. The insertion of an element from a queue is called as? 7. What function can be used to display the value of “front”? 8. Function used to check if there’s no space in queue. 9. How many pointers do we need to maintain so we can access the queue? 10. Function used to check if there’s no element in queue  UNIT 1: Data Structures True or False: Write T if the statement is true, and F is the statement is false 1. After deleting an element from a queue that is full, you can still add another element. 2. In circular queue, elements from a queue that is full can be replaced once dequeued. 3. The priority queue only applies to the rear element of the queue. 4. If an element has lower priority, it will be deleted first. 5. In a circular queue, the front always stays in the 0th index of array. 6. The queue data structure can be applied using class 7. Queues cannot be applied with arrays. 8. Priority queues follows the FIFO principle. 9. Ring buffer is another term for circular queues. 10. The dequeuing of an element happens in the rear element.  UNIT 1: Data Structures What is a Queue? The known description of “queue” is a line, usually of people or things waiting for something. It implements the idea of “first come, first serve”, in which the first person or thing coming from that line will be prioritized first before turning to the next, then afterwards they can get out from the line. This idea is often experienced in different real-world situations such as waiting in line for a movie, waiting at a check- out line in the grocery store, or ordering from a fast-food restaurant. Source: lttps://www.vecteezy.com/vector-art/1237890-people-standing-in-line Figure 1: Sample image of a waiting line for a movie In programming concept approach, “Queue” is an abstract data type or linear data structure, somewhat similar to stacks. But unlike stacks, a queue is open at both ends. It is considered as an ordered collection of items where the insertion of new element happens at one end, which is called as the “rear” (also called as the “tail”), and the removal of existing element takes place from the other end called as the “front” (also called as the head). Figure 2: Sample image of a Queue Data Structure The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called “FIFO” (first-in first-out), which is also known as the idea of “first-come first-served” method. Well-behaved lines, or queues, are very restrictive that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front. Another real-world example of FIFO can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops. CC105: DATA STRUCTURES AND ALGORITHMS 61  UNIT 1: Data Structures Just like in stacks, a queue can also be implemented using arrays, linked-lists, pointers and structures. For the example, we shall implement queues using one- dimensional array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index. The following diagram given below tries to explain queue representation using array. Figure 3: Sample image of a Queue Data Structure using an array When we remove an element from Queue, we remove the element from head position and then move head to the next position. Whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time. CC105: DATA STRUCTURES AND ALGORITHMS 62  UNIT 1: Data Structures Figure 4: After removing an element from the queue Difference Between Queues and Stacks In this table, it shows the comparisons between stacks and queues. Stacks Queues Uses LIFO (Last in, First out) Uses FIFO (First in, First out) approach. approach. Items are added or deleted from Items are added from “Rear” end of the only one end called “Top” of the queue and are removed from the “front” of stack. the queue. The basic operations for the stack The basic operations for a queue are are “push” and “Pop”. “enqueue” and “dequeue”. We can do all operations on the In queues, we need to maintain two pointers, stack by maintaining only one one to access the front of the queue and the pointer to access the top of the second one to access the rear of the queue. stack. The stack is mostly used to solve Queues are used to solve problems related recursive problems. to ordered processing. Basic Operations To fully utilize or define a queue, there are basic operations that can be used. These are: 1. enqueue – adds (store) an item to the queue. And; 2. dequeue – removes (access) an item from the queue. In a queue, we dequeue (or access) the data from the front pointer and enqueuing (or storing) data in the queue to the rear pointer. There are also few functions that can be used to make the above-mentioned queue operation efficient. These are:  peek() − Gets the element at the front of the queue without removing it.  isfull() − Checks if the queue is full.  isempty() − Checks if the queue is empty. CC105: DATA STRUCTURES AND ALGORITHMS 63  UNIT 1: Data Structures Let's first learn about supportive functions of a queue – 1. peek() This function helps to see the data at the front of the queue. The algorithm of peek() function is as follows − Algorithm: begin procedure peek return queue[front] end procedure Implementation of peek() function example: int peek() { return queue[front]; } 2. isfull() Assume that we are using a single dimension array to implement queue, we just need to check for the rear pointer and compare it to size we set for the array to determine if the queue is full. Algorithm of isfull() function is as follows − Algorithm: begin procedure full if rear equals to MAXSIZE return true else return false endif end procedure Implementation of isfull() function example: bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; } 3. isempty() In contrast to isfull() function, the isempty() function determines whether the queue is empty or not by determining the value that the front holds. Algorithm of isempty() function is as follows− CC105: DATA STRUCTURES AND ALGORITHMS 64  UNIT 1: Data Structures Algorithm: begin procedure isempty if front is less than MIN OR front is greater than rear return true else return false endif end procedure If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty. Implementation of isempty() function example: bool isempty() { if(front < 0 || front > rear) return true; else return false; } Applications of Queue Let us discuss the various applications of the queue data structure below.  The queue data structure is used in various CPU and disk scheduling. Here we have multiple tasks requiring CPU or disk at the same time. The CPU or disk time is scheduled for each task using a queue.  The queue can also be used for print spooling wherein the number of print jobs is placed in a queue.  Handling of interrupts in real-time systems is done by using a queue data structure. The interrupts are handled in the order they arrive.  Call center phone systems use queues to hold the calls until they are answered by the service representatives. In general, we can say that the queue data structure is used whenever we require the resources or items to be serviced in First in, First Out order. CC105: DATA STRUCTURES AND ALGORITHMS 65  UNIT 1: Data Structures Enqueue and Dequeue Operation What is Enqueue and Dequeue? On the previous chapter, enqueue and dequeue were defined as the operations used to add and remove an item from a queue. It is the most necessary operation to utilize the queue data structure. But what are the steps to perform these operations? Enqueue Operation In this process, the following steps are performed:  Check if the queue is full.  If full, produce overflow error and exit.  Else, increment ‘rear’.  Add an element to the location pointed by ‘rear’.  Return success. Dequeue Operation Dequeue operation consists of the following steps:  Check if the queue is empty.  If empty, display an underflow error and exit.  Else, the access element is pointed out by ‘front’.  Increment the ‘front’ to point to the next accessible data.  Return success. Next, we will see a detailed illustration of insertion and deletion operations in queue. Illustration This is an empty queue and thus we have rear and empty set to -1. Figure 5: Shows the structure of an empty queue Next, we add 1 to the queue and as a result, the rear pointer moves ahead by one location. Figure 5.1: Shows the result after adding an element CC105: DATA STRUCTURES AND ALGORITHMS 66  UNIT 1: Data Structures In the next figure, we add element 2 to the queue by moving the rear pointer ahead by another increment. Figure 5.2: Shows the result after adding an element In the following figure, we add element 3 and moved the rear pointer. Figure 5.3: Shows the result after adding an element At this point, the rear pointer is at the 2nd location while the front pointer is at the 0th location. Next, we delete the element pointed by the front pointer. As the front pointer is at 0, the element that is deleted is 1. Figure 5.4: Shows the result after deleting an element Thus, the first element entered in the queue i.e. 1 happens to be the first element removed from the queue. As a result, after the first dequeue, the front pointer now will be moved ahead to the next location which is 1. CC105: DATA STRUCTURES AND ALGORITHMS 67  UNIT 1: Data Structures Algorithm for Enqueue and Dequeue Operation Here’s how you can implement Enqueue and Dequeue operations using a queue data structure in Java. Algorithm for Enqueue Operation: 1. Create a new node for the element to be enqueued. 2. Check if the queue is empty: o If the queue is empty, make the new node the front and rear of the queue. o If the queue is not empty, set the rear node’s next pointer to the new node, and then make the new node the rear of the queue. 3. Update the size of the queue. Algorithm for Dequeue Operation: 1. Check if the queue is empty: o If the queue is empty, print a message indicating that the queue is empty (underflow condition). 2. If the queue is not empty: o Store the current front node to return later. o Move the front pointer to the next node. o If the queue becomes empty (i.e., front becomes null after moving to the next node), set the rear to null as well. 3. Return the value of the dequeued node. In this example code, it will show how the insertion and deletion of an element in a queue is applied using Java. Using Linked List class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } class Queue { private Node front, rear; private int size; public Queue() { front = rear = null; size = 0; } CC105: DATA STRUCTURES AND ALGORITHMS 68 UNIT 1: Data Structures // Enqueue operation public void enqueue(int data) { Node newNode = new Node(data); // If queue is empty if (rear == null) { front = rear = newNode; } else { rear.next = newNode; // Link the new node at the end rear = newNode; // Update the rear pointer } size++; System.out.println(data + " enqueued to the queue"); } // Dequeue operation public int dequeue() { if (front == null) { System.out.println("Queue is empty! Cannot dequeue."); return -1; // Return -1 if the queue is empty } int dequeuedData = front.data; front = front.next; // Move the front pointer to the next node // If the queue becomes empty, update rear to null if (front == null) { rear = null; } size--; System.out.println(dequeuedData + " dequeued from the queue"); return dequeuedData; } // Check if the queue is empty public boolean isEmpty() { return front == null; } // Get the size of the queue public int size() { return size; } } CC105: DATA STRUCTURES AND ALGORITHMS 69 UNIT 1: Data Structures public class Main { public static void main(String[] args) { Queue queue = new Queue(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println("Dequeued element: " + queue.dequeue()); System.out.println("Dequeued element: " + queue.dequeue()); } } Using Array public class ArrayQueue { private int front, rear, capacity; private int[] queue; // Constructor to initialize the queue public ArrayQueue(int size) { front = rear = 0; capacity = size; queue = new int[capacity]; } // Method to add an element to the queue public void enqueue(int data) { if (capacity == rear) { System.out.println("Queue is full"); return; } queue[rear] = data; rear++; } CC105: DATA STRUCTURES AND ALGORITHMS 70 UNIT 1: Data Structures // Method to remove an element from the queue public void dequeue() { if (front == rear) { System.out.println("Queue is empty"); return; } System.out.println("Removed element: " + queue[front]); for (int i = 0; i < rear - 1; i++) { queue[i] = queue[i + 1]; } rear--; } // Method to display the queue public void display() { if (front == rear) { System.out.println("Queue is empty"); return; } for (int i = front; i < rear; i++) { System.out.print(queue[i] + " "); } System.out.println(); } // Method to get the front element of the queue public void peek() { if (front == rear) { System.out.println("Queue is empty"); return; } System.out.println("Front element: " + queue[front]); } CC105: DATA STRUCTURES AND ALGORITHMS 71 UNIT 1: Data Structures public static void main(String[] args) { // Create a queue of capacity 5 ArrayQueue q = new ArrayQueue(5); // Adding elements to the queue q.enqueue(10); q.enqueue(20); q.enqueue(30); q.enqueue(40); q.enqueue(50); // Display the queue System.out.println("Queue:"); q.display(); // Peek at the front element q.peek(); // Remove elements from the queue q.dequeue(); q.dequeue(); // Display the queue after removal System.out.println("Queue after dequeue:"); q.display(); // Peek again q.peek(); // Add another element q.enqueue(60); // Display final queue System.out.println("Queue after adding new element:"); q.display(); } } CC105: DATA STRUCTURES AND ALGORITHMS 72  UNIT 1: Data Structures Circular Queues A circular queue or “ring buffer” is a type of queue in which the last position is connected to the first position, which is represented by the shape of a circle. It is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle of queues. Figure 7: Shows the structure of a Circular Queue In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we cannot insert the next element even if there is a space in front of queue. Figure 8: Shows the limitation of a regular queue As you can see in the above image, after a bit of enqueuing and dequeuing, the size of the queue has been reduced. If you will try to enter an element, it will prompt that the queue is full although there is still space from the queue. The indexes 0 and 1 can only be used after the queue is reset when all the elements have been dequeued. How it works? Circular Queue works by the process of circular increment. For example, when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue. With the implementation of Circular Queues, it avoids the wastage of space in a regular queue implementation using arrays. Circular Queue also uses the algorithm of enqueue and dequeue. CC105: DATA STRUCTURES AND ALGORITHMS 73  UNIT 1: Data Structures Circular Queue Operations The circular queue work as follows:  two pointers front and rear  front track the first element of the queue  rear track the last elements of the queue  initially, set value of front and rear to -1 1. enqueue operation  check if the queue is full  for the first element, set value of front to 0  circularly increase the rear index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)  add the new element in the position pointed to by rear 2. dequeue operation  check if the queue is empty  return the value pointed by front  circularly increase the front index by 1  for the last element, reset the values of front and rear to -1 however, the check for full queue has a new additional case:  case 1: front = 0 && rear == size - 1  case 2: front = rear + 1 the second case happens when rear starts from 0 due to circular increment and when its value is just 1 less than front, the queue is full. Figure 9.1: Shows the structure of an empty circular queue Figure 9.2: Shows the result after adding an element CC105: DATA STRUCTURES AND ALGORITHMS 74 UNIT 1: Data Structures Figure 9.3: Shows the result after adding an element Figure 9.4: Shows the result of a queue with full elements Figure 9.5: Shows the result after the deletion of 2 elements Figure 9.6: Shows the result of a adding an element on 0th location CC105: DATA STRUCTURES AND ALGORITHMS 75  UNIT 1: Data Structures Figure 9.7: Shows the result of a adding an element on 1st location Here’s the basic algorithm for operations in a circular queue: 1. Initialization You need to initialize the queue with a fixed size and two pointers, front and rear, both initialized to -1. This helps in keeping track of the elements' insertion and deletion. Initialize: front = -1 rear = -1 size = N (size of the queue) queue[] = array of size N 2. Enqueue (Adding an element to the queue) This operation inserts an element into the queue.  Steps: 1. Check if the queue is full. If (rear + 1) % size == front, the queue is full. 2. If empty (front == -1), set both front and rear to 0. 3. Else, update rear to (rear + 1) % size. 4. Insert the element at queue[rear]. Algorithm: Enqueue(Q, element) if ( (rear + 1) % size == front ): Queue is full else if (front == -1): front = rear = 0 else: rear = (rear + 1) % size queue[rear] = element 3. Dequeue (Removing an element from the queue) This operation removes an element from the queue. Steps: 1. Check if the queue i