University:
California State University, Northridge
Course:
COMP 322/L | Introduction to Operating Systems and System Architecture and Lab
Academic year:

2025
Views:

208

Pages:

7
Author:

Ismail Allaham

Data Structures and Algorithms CSCI 215 – Sec 1 Homework 3 – 4/05/24 Queues Worth: 4% Instructor: Dr. Mohammed Awad Ali Algawish – 2022005426 The code: #include using namespace std; // Node struct defines elements of the linked list used in the stack struct Node { double data; // Data value of the node Node* next; // Pointer to the next node in the list // Constructor initializes a node with data and sets next to null Node(double val) : data(val), next(nullptr) {} }; // Class to manage a sorted stack using a singly linked list class SortedStack { private: Node* head; // Head pointer for the stack's top public: // Constructor initializes an empty stack SortedStack() : head(nullptr) {} // Method to insert a value in sorted order void insert(double val) { Node* newNode = new Node(val); // Creates a new node // Place the new node at the start if appropriate if (!head || val <= head->data) { newNode->next = head; head = newNode; } else { // Insert the node in the correct sorted position Node* current = head; while (current->next && current->next->data < val) { current = current->next; } newNode->next = current->next; current->next = newNode; } } // Method to remove a node with a specific value void remove(double val) { // Return immediately if the stack is empty if (!head) return; Node* temp; // Special case for removing the head node if (head->data == val) { temp = head; head = head->next; delete temp; return; } // Find the node before the node we want to remove Node* current = head; while (current->next && current->next->data != val) { current = current->next; } // Remove the node if it exists if (current->next) { temp = current->next; current->next = current->next->next; delete temp; } } // Print all elements in the stack void print() { Node* current = head; while (current) { cout << current->data << " "; current = current->next; } cout << endl; } }; // Demonstrates usage of the SortedStack class int main() { SortedStack aStack; // Demonstrating insertion and display aStack.insert(5.0); cout << "After inserting 5.0: "; aStack.print(); aStack.insert(2.9); cout << "After inserting 2.9: "; aStack.print(); aStack.insert(3.3); cout << "After inserting 3.3: "; aStack.print(); // Removing and then printing the updated stack aStack.remove(3.3); cout << "After removing 3.3: "; aStack.print(); } Screen shot of the program: Analyzing the Problem: To tackle this issue, we need a data structure that can effectively manage a sorted list of double values, while also supporting insertion, deletion, and printing functionalities. I've selected a 'Stack Implemented Using a Linked List' as the appropriate data structure for this purpose. Description of Data Structure: In a linked list implementation of a stack, elements are stored in nodes, and each node has a pointer to the next node in the queue. To maintain the sorted order, we can push elements in such a way that the stack is always sorted. A diagram To illustrate Stack complexity: Insertion: Adding an element to a stack that is maintained in sorted order might require scanning through the entire stack to locate the correct position for the new element. This gives it a time complexity of O(n), where n is the total number of elements in the stack. Deletion: Removing the top element from a stack is a quick operation, with a time complexity of O( 1). This efficiency stems from simply needing to update the top pointer of the stack, without having to interact with other elements. Printing: To print all elements, the entire stack must be traversed, with each element being printed in turn. Thus, the time complexity for this operation is O(n), correlating directly with the stack's size.

Data Structures and Algorithms

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock