Question 3: Queue Implementation A programmer proposes the following implementat

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

1)
Queue

Operation ArrayList LinkedList
Creation time O(1) O(1)
add(T)/enqueue O(1) O(1)
remove(0)/dequeue O(n) O(1)
get(0)/front O(1) O(1)

add(T)/enqueue : Need to add the rear(last), so it takes constant time to add an element at end in both array and linked list
remove(0).dequeue: Nedd to remove first element
In array, removing first element needs to shift all elements right to first, one by left
But in linked list removing first element is constant time operation

get(0)/front : getting first element from both array/linkedlist is a constant operation

2)
Stack:
In stack implementation
using ArrayList: In this case : starting point(head of array) => bottom of stack, last part (end point) => top of stack
using LinkedlIst: In this case : starting point(head) => top of stack, end part => bottom of stack

Operation ArrayList LinkedList
Creation time O(1) O(1)
add(T)/enqueue O(1) O(1)
remove(0)/dequeue O(1) O(1)
get(0)/front O(1) O(1)

add(T)/enqueue : Need to add the rear(last), so it takes constant time to add an element at end in both array and
starting of linked list
remove(0).dequeue: Nedd to remove top element
In array, removing last element needs takes constant time
In linked list removing first element is constant time operation

get(0)/front : getting first element fromlinkedlist and last element from array takes constant time

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.