Question

In: Computer Science

COMP 251: Data Structures and Algorithms – Lab 4 Page 1 of 2 Lab 4: Implementing...

COMP 251: Data Structures and Algorithms – Lab 4 Page 1 of 2 Lab 4: Implementing a Stack Using Linked List Implementation Objectives: The aim of this lab session is to make you familiar with using the linked list implementation in week3 and implement a stack using it. In this lab you will complete the partially implemented StackUsingLinkedList. Specifically, you will implement the following methods. • The default constructor: public StackUsingLinkedList() • public void push(AnyType x) • public AnyType pop() • public AnyType peek() • public boolean isEmpty() • public void makeEmpty() You are expected to use Java programming language in Eclipse IDE with EGit tool for completion of this lab exercise. You should upload your completed code repository (the complete parent folder of your work) as a zip file to the assignment in the Blackboard. Task 1: Preliminary Work for Setting up the Git Repository and Project 1. If you have not done already, set your name and email address as instructed in the Eclipse EGit Tutorial: Task 1: Initial Setup section. 2. Create a local Git repository (if one is not available in your eclipse environment). 3. Create a new Java project named Lab4_ (for example Lab4_300321321). 4. Add the newly created project to your local Git repository. (Instructions available in Eclipse EGit Tutorial - Task 2: Creating a New Java Project and Adding it to a New Repository) 5. Make sure the editing history of all the project files are tacked by Git (Add to Index, Instructions available in Eclipse EGit Tutorial - Task 2: Creating a New Java Project and Adding it to a New Repository) 6. Add the Java classes ListNode and SimpleLinkedList classes provided with the code in the week 3 to the new project. 7. Add the StackUsingLinkedList class provided with the Lab 4 to new project. 8. Make sure the editing histories of all the newly created files are tracked by Git by adding it to the index (Add to Index, Instructions available in Eclipse EGit Tutorial - Task 2: Creating a New Java Project and Adding it to a New Repository). 9. For each Java class, update the comments section to indicate that you updated the code. For this add you as the second author of code and include your email address. 10. Commit all the changes done up to this point. COMPUTER INFORMATION SYSTEMS COMP 251: DATA STRUCTURES AND ALGORITHMS COMP 251: Data Structures and Algorithms – Lab 4 Page 2 of 2 Task 2: Implement the Methods Important Considerations: In this lab, you are using the SimpleLinkedList class as a library and you are not allowed to make any changes to the class. You should be only making changes to the StackUsingLinkedList class. Note: If you understand the ideas discussed in week 4, you should be able to complete the implementation of the five methods in 15 minutes. 1. Implement the default constructor public StackUsingLinkedList()method in the StackUsingLinkedList class. The constructor should initialize the stack to an empty stack. 2. Implement the push method in the StackUsingLinkedList class. 3. Implement the pop method in the StackUsingLinkedList class. 4. Implement the peek method in the StackUsingLinkedList class. 5. Implement the isEmpty method in the StackUsingLinkedList class. 6. Implement the makeEmpty method in the StackUsingLinkedList class. 7. Make sure your code is commented and properly indented. 8. Commit code changes. Task 3: Implement Code Testing 1. Add a new class named Lab4Tester class to test your implementation of the stack. Your test class should test all the methods implemented in the class. 2. Make sure your code compiles and executes without any errors. 3. Test the new implementation using Lab4Tester class. 4. Commit code changes. Submission: Upload your code repository to the assignment (named Lab4) in the blackboard. The file should be named as follows. Code Repository: Create a zip file of your final code repository (the complete parent folder of your work) and name it as _Lab4_Code.zip (for example 300321321_Lab4_Code.zip)

Solutions

Expert Solution

As there are multiple tasks/questions, answering the first ONE. For others, please create seperate question for faster resolution

As defined in question - Programming Language is JAVA

Task 1) - Implementing a stack using linked list. Operations like push peek pop isEmpty and makeEmpty.

- Kindly upvote if this helped.

CODE:

- I have included an extra display function for testing the results.



public class StackUsingLinkedList {    
    class Node{    
        int data;    
        Node next;    
            
        public Node(int data) {    
            this.data = data;    
            this.next = null;    
        }    
    }    
    
    StackUsingLinkedList(){
        h = null;
        t = null;
    }
     
    public Node h;    
    public Node t;    
        
    public void push(int data) {    
        Node newNode = new Node(data);    
            
        if(h == null) {    
            h = newNode;    
            t = newNode;    
        }    
        else {    
            t.next = newNode;    
            t = newNode;    
        }    
    }    
    
   
    
   
  
    public void display() {    
        Node current = h;    
        if(h == null) {    
            System.out.println("No data in list");    
            return;    
        }    
        System.out.println("Values in list are ");    
        while(current != null) {    
            System.out.print(current.data + " ");    
            current = current.next;    
        }  
        System.out.println();
    }    
    
    public boolean isEmpty() {
        if(h == null) {
                return true;
        }else {
                return false;
        }
    }
    
    public void makeEmpty() {
        h = null; // pointing head node to null makes the singly linked list empty
    }
    
    
    public Integer pop() {
         Node current = h;    
        Integer data = null;
        if(h == null) {    
            return null;    
        }
        if(h.next == null) { //only one element is list
                h = null;
        }
        while(current != null) {    
                if(current.next == t) {
                        data = t.data;
                        current.next = null;
                        t = current;
                        break;
                }
            current = current.next;    
        }  
        return data;
   }
    
    public Integer peek() {
         Node current = h;    
           
           if(h == null) {    
               return null;    
           }
           while(current != null) {    
                if(current == t) {
                        return current.data;
                }
               current = current.next;    
           }  
           return null;
      }
    
  
    public static void main(String[] args) {    
        StackUsingLinkedList sL = new StackUsingLinkedList();    
        sL.push(4);    
        sL.push(2);    
        sL.push(5);    
        sL.push(8);
        System.out.println(sL.isEmpty());
        sL.display();
        System.out.println("Poped element is:"+sL.pop());
        sL.display();
        sL.peek();
        System.out.println("Peeked value is: "+sL.peek());
        sL.display();
    }    
    
}    



OUTPUT


Related Solutions

Page Replacement Algorithms. Consider the following page reference stream and 3 page frames: 0 1 2...
Page Replacement Algorithms. Consider the following page reference stream and 3 page frames: 0 1 2 3 2 4 3 1 1 5 2 4 6 3 3 4 6 3 4 7. For the MIN, FIFO, and LRU algorithms, show the contents of the page frame after each reference, and then compute the total number of page faults, divided in to cold misses and other misses.
This question is in reference to BFS and DFS for data structures and algorithms Consider a...
This question is in reference to BFS and DFS for data structures and algorithms Consider a graph algorithm with a growth function on V and E: f(V, E). How would you convert f(V,E) to f'(V) such that f(V,E)=O(g(n))=f(V)? (That is, convert a growth function of two variables to be of one variable in such a way that the Big-Oh bound for the one variable function will hold for the two variable function.) Explain the steps in creating f', and explain...
Thoroughly explain the impacts of data structures and algorithms in the development and implementation of computer...
Thoroughly explain the impacts of data structures and algorithms in the development and implementation of computer programs using modern computer technologies.
What are the data structures and algorithms? Why are they important to software developers? Give an...
What are the data structures and algorithms? Why are they important to software developers? Give an example of using a data structure. Give an example of using algorithm. Use Google to search for your answers. Minimum 400 words and a maximum of 1000 words.
Data Structures and Algorithms Activity Requirement: Implement a queue using an array as its underline data...
Data Structures and Algorithms Activity Requirement: Implement a queue using an array as its underline data structure. Your queue should fully implemnted the following methods: first, push_back (enqueue), pop_front (dequeue), size, and isEmpty. Make sure to include a driver to test your newly implemented queue
This is a C++ based question that involves Data Structures and Algorithms. Q. Application: Linked List...
This is a C++ based question that involves Data Structures and Algorithms. Q. Application: Linked List of Bus Transit and Passengers You are to implement a C++ program for City Bus Transit using linked list data structure to maintain record of passengers. Specifically, you are to implement the following methods/functions: For Passenger: o A function which can create a new node of the linked list using new for each newpassenger o A function that prints the time of single passenger...
Questions about NMR. Draw the structures of 2-chlorohexane and 2-chloro-4-methylpentane in your lab notebook and note...
Questions about NMR. Draw the structures of 2-chlorohexane and 2-chloro-4-methylpentane in your lab notebook and note the following: a. the total number of H atoms in each molecule b. the total number of C atoms in each molecule c. the number of different types of H atoms in each molecule d. the number of different types of C atoms in each molecule e. the number of signals expected in the 1H NMR spectrum of each molecule f. the number of...
%Lysis COMP 250 COMP 100 COMP 20 n=1 87.77 81.73 65.8 n=2 81.71 50.45 63.7 n=3...
%Lysis COMP 250 COMP 100 COMP 20 n=1 87.77 81.73 65.8 n=2 81.71 50.45 63.7 n=3 86.64 55.38 59.4 n=4 90.03 82.39 71.67 AVERAGE 87.5 68.4 66.1 STD DEV 4.0 15.6 5.4 SEM 2.5 8.3 3.2 4.Perform a t-test comparing COMP250 to COMP100 and COMP250 to COMP20. A p value when p<0.05 is statistically significant and p value when p>0.05 is not significant. Include all p values and comment on their significance. 5. In your discussion briefly comment on the...
The following page-reference string: 1, 2, 4, 3, 2, 5, 4, 2, 4, 2, 1, 3,...
The following page-reference string: 1, 2, 4, 3, 2, 5, 4, 2, 4, 2, 1, 3, 2, 3, 1, 3, 6, 1, 6, 4. Main memory with 3 frames of 1 kilobyte available and they are all initially empty. Complete a figure, similar to Figure 8.14(in the slides or textbook), showing the frame allocation for each of the following page replacement policies: a. Optimal b. Least recently used c. First-in-first-out Then, find the relative performance of each policy with respect...
Individuals and organizations build various data structures and algorithms to solve real-life problems. Furthermore, many data...
Individuals and organizations build various data structures and algorithms to solve real-life problems. Furthermore, many data analysts tend to use Big-O notation for analyzing algorithms. In your own words, explain ways by which people can specify (i). data structures and (ii) algorithms, that they build and use.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT