In: Computer Science
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)
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