Question 3: Queue Implementation A programmer proposes the following implementat
ID: 3577410 • Letter: Q
Question
Question 3: Queue Implementation
A programmer proposes the following implementation of a queue using a List:
Create a queue by creating the List: List myQueue = new ... // some list constructor
Use myQueue.add( item ) to implement the enqueue operation. This adds at the end of the list, so the end of the list will be the rearof the queue, and the beginning of the list will be the front of the queue.
Use myQueue.get( 0 ) to implement the front operation -- examine the item at the front of the queue.
Use myQueue.remove( 0 ) to implement the dequeue operation -- remove the item at the front of the queue.
One question remains unanswered: which kind of list should be used: ArrayList or LinkedList? Evaluate and comment on the efficiency of each of these options. Would one of these be more efficient? If so, why? Use "Big-O" notation to describe the complexity of each of the four operations listed.
Question 4: Stack Implementation
In a manner similar to that used in the previous question, explain how a List could be used to implement a stack. List each operation required for a stack and explain exactly how a List operation (a method from the list interface) could be used to implement it. When the List method requires a parameter, explain what value should be used. Draw a diagram that illustrates the operations in action.
Explanation / Answer
linked list implementation of quueue:
import java.util.*;
public class queue_implementation {
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
//Scanner sc=new Scanner(System.in);
List<Integer>llist=new LinkedList<Integer>();
while(true){
System.out.println("enter choice:");
System.out.println("1.insert");
System.out.println("2.remove");
System.out.println("3.display");
int choice=sc.nextInt();
switch(choice){
case 1:enqueue(llist);
break;
case 2:dequeue(llist);
break;
case 3:display(llist);
break;
}
}
}
public static void display(List<Integer> llist) {
for(int i=0;i<llist.size();i++)
System.out.println(llist.get(i));
}
public static void dequeue(List<Integer> llist) {
llist.remove(0);
}
public static void enqueue(List<Integer> llist) {
System.out.println("enter element to be inserted:");
int element=sc.nextInt();
llist.add(element);
}
}
import java.util.*;
public class queue_implementation {
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
//Scanner sc=new Scanner(System.in);
List<Integer>llist=new LinkedList<Integer>();
while(true){
System.out.println("enter choice:");
System.out.println("1.insert");
System.out.println("2.remove");
System.out.println("3.display");
int choice=sc.nextInt();
switch(choice){
case 1:enqueue(llist);
break;
case 2:dequeue(llist);
break;
case 3:display(llist);
break;
}
}
}
public static void display(List<Integer> llist) {
for(int i=0;i<llist.size();i++)
System.out.println(llist.get(i));
}
public static void dequeue(List<Integer> llist) {
llist.remove(0);
}
public static void enqueue(List<Integer> llist) {
System.out.println("enter element to be inserted:");
int element=sc.nextInt();
llist.add(element);
}
}
output:
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
1
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
2
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
3
enter choice:
1.insert
2.remove
3.display
3
1
2
3
enter choice:
1.insert
2.remove
3.display
2
enter choice:
1.insert
2.remove
3.display
3
2
3
enter choice:
1.insert
2.remove
3.display
if use linkedlist for enqueue the complexity is O(1)
whre as if we use Arraylist the complexity is O(1) best case and worst case is O(n)
in order to dequue the time complexity is O(n/4) that is for average case and for in Arraylist the time complexity is O(n/2) average case
and for to get an element is O(n/4) in linked list and for arraylist is O(1)
linked list implementation of stack
import java.util.*;
public class queue_implementation {
static Scanner sc=new Scanner(System.in);
public static void main(String[] args) {
//Scanner sc=new Scanner(System.in);
List<Integer>llist=new LinkedList<Integer>();
while(true){
System.out.println("enter choice:");
System.out.println("1.insert");
System.out.println("2.remove");
System.out.println("3.display");
int choice=sc.nextInt();
switch(choice){
case 1:push(llist);
break;
case 2:pop(llist);
break;
case 3:display(llist);
break;
}
}
}
public static void display(List<Integer> llist) {
for(int i=llist.size()-1;i>=0;i--)
System.out.println(llist.get(i));
}
public static void pop(List<Integer> llist) {
llist.remove(llist.size()-1);
}
public static void push(List<Integer> llist) {
System.out.println("enter element to be inserted:");
int element=sc.nextInt();
llist.add(element);
}
}
output:
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
1
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
2
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
3
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
4
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
5
enter choice:
1.insert
2.remove
3.display
3
5
4
3
2
1
enter choice:
1.insert
2.remove
3.display
2
enter choice:
1.insert
2.remove
3.display
3
4
3
2
1
enter choice:
1.insert
2.remove
3.display
2
enter choice:
1.insert
2.remove
3.display
3
3
2
1
enter choice:
1.insert
2.remove
3.display
2
enter choice:
1.insert
2.remove
3.display
3
2
1
enter choice:
1.insert
2.remove
3.display
1
enter element to be inserted:
9
enter choice:
1.insert
2.remove
3.display
3
9
2
1
enter choice:
1.insert
2.remove
3.display
2
enter choice:
1.insert
2.remove
3.display
3
2
1
enter choice:
1.insert
2.remove
3.display
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.