CSCI 143: Object Oriented Programming 2 with Java LinkedList In-class Exercise I
ID: 3846915 • Letter: C
Question
CSCI 143: Object Oriented Programming 2 with Java
LinkedList In-class Exercise
It is often the case that new data structures are written using other existing data structures as an underlying model. In this practice exercise we will be creating a Queue class using Java’s LinkedList as a basis for our new class.
A Queue data structure behaves similarly to a set of people waiting in line. There are restrictions on entering and exiting the line:
1. You may only enter the line at the back, referred to as an “enqueue” operation. 2. You may only exit the line at the front, referred to as a “dequeue” operation. 3. You may also look at the person in the front of the line, referred to as a “peek”
operation. 4. You cannot be helped if you are in the middle of the line.
Because of these restrictions, a Queue data type is referred to as a FIFO structure (first-in-first-out).
Note: because we only allow access to elements at the front/back of a Queue, this removes the index-based access of structures such as Arrays and ArrayLists
Write a new Queue class using a LinkedList as the underlying storage structure (in other words, a private instance field). You can simulate the behavior described above by adding items to the front of your LinkedList and removing items from the back.
Hint: I would suggest looking for helpful methods in the Java API for the LinkedList class.
In particular the following methods: addFirst, addLast, removeFirst, removeLast
Use the following class diagram as a basis for your class:
Queue<T>
- data : LinkedList<T>
+ enqueue(newElement : T) : void + dequeue() : T + peek() : T + isEmpty() : boolean + size() : int
Note: your Queue<T> class should throw an appropriate exception when dequeue() is called on an empty Queue.
Write a test class to show that your Queue class is working correctly.
CSCI 143: Object Oriented Programming 2 with Java
Challenge: create a new class called BoundedQueue that enforces a maximum number of elements in your queue.
1. Use the code from your Queue class as a starting point in your new BoundedQueue class 2. Include only a parameterized constructor that takes a positive integer that specifies the
maximum number of elements in your bounded queue 3. Throw an appropriate exception if you queue size exceeds the bounds given
Error! We couldn’t load the file.
Retry?
1 / 2
Explanation / Answer
package listclasses;
public class singlelinkedlist {
int data;
singlelinkedlist next;
singlelinkedlist(int data){
this.data=data;
}
singlelinkedlist(int data,singlelinkedlist next){
this.data=data;
this.next=next;
}
public String tostring(){
return data+"";
}
}
main class:
package listclasses;
import java.util.*;
public class singlelinkedlistmain {
static singlelinkedlist head;
static int size;
static int rear;
static {
head=null;
size=0;
rear=5;
}
public static void main(String[] args) {
enque(10);
enque(20);
enque(30);
enque(40);
enque(50);
display();
System.out.println(" height:"+size);
dequee();
display();
}
public static void display(){
singlelinkedlist curent=head;
while(curent!=null){
System.out.print(curent.data+" ");
curent=curent.next;
}
//System.out.println(" "+size);
}
public static void insertat(int data,int index){
if(index<1 || index>size)
return;
int i=1;
singlelinkedlist curent=head;
if(curent==null){
singlelinkedlist newlist=new singlelinkedlist(data,null);
}
while(i<index){
curent=curent.next;
i++;
}
singlelinkedlist newlist=new singlelinkedlist(data,null);
newlist.next=curent.next.next;
curent.next=null;
curent.next=newlist;
size++;
}
public static int height(){
return size;
}
public static void insertfront(int data){
if(head==null){
head=new singlelinkedlist(data,null);
size++;
}else{
singlelinkedlist newlist=new singlelinkedlist(data,null);
newlist.next=head;
head=newlist;
size++;
}
}
public static void enque(int data){
if(size<rear){
singlelinkedlist curnt=head;
if(head==null){
head=new singlelinkedlist(data,null);
size++;
}else{
while(curnt.next!=null){
curnt=curnt.next;
}
singlelinkedlist newlist=new singlelinkedlist(data,null);
curnt.next=newlist;
size++;
}
}else{
System.out.println("queeu is full:");
}
}
public static void dequee(){
if(head==null){
System.out.println("queue is empty:");
return;
}
if(head.next!=null){
head=head.next;
size--;
}
}
}
output:
10 20 30 40 50
height:5
20 30 40 50