Data Structures and Algorithms. JAVA. 6. A circularly linked list is used to rep

Question

Data Structures and Algorithms. JAVA.

6.    A circularly linked list is used to represent a Queue. A single variable P is used to access the Queue. To which Node should P point such that both the operations enqueue (item) and item = dequeue() can be performed in constant time: O(1) –no looping necessary?

Answer:

7. Show what is written by the following segment of code:

<String> stack = new MyStack<String>();

String item0 = “”;

String item1 = “EE”;

String item2 = “B” + item1;

String item3 = “P”;

push (item2);       

push (item1);       

push (item3 + item1);

item0 = stack.peek();     

pop();              

push (item2 + item3);

push (item0);       

push (item0 + item3);

item0 = stack.peek();     

pop();              

print (“Item0: ” + item0);

print (“Item1: ” + item1);

print (“Item2: ” + item2);

print (“Item3: ” + item3);

while (!stack.isEmpty())

item0 = stack.peek();   

pop();            

print (“Item: ” + item0);

    Answer:

8. A single array, stk[MAXELEMS], is used to implement two stacks. The two stacks are grown in an array – one from each end. Two variables, head1 and head2 (head1 < head2), hold the index of the location of the top element in each of the stacks. Which of the following is the best for implementing the check for a full stack, given we want a space efficient algorithm.

(head1 = MAXELEMS / 2) and (head2 = MAXELEMS / 2+1)

head1 + head2 = MAXELEMS

(head1 = MAXELEMS / 2) or (head2 = MAXELEMS)

head1 = head2 – 1

     Answer:

Explanation / Answer

Q6.

   P should points to 'rear' of linked list, so that enqueue and dequeue can be performed in O(1) time.

   Because to add an element in queue(enqueue) we just need to point 'current rear' to new node and 'new node' point to front
   and at last update 'rear' to 'new node'

   TO dequeue, we just update rear->next to rear->next->next, because rear-next = front, so we remove 'front' this way

Q7.

I have mentioned output at each line of code.

<String> stack = new MyStack<String>();

We have empty stack: top => {empty} <= bottom

String item0 = “”;
String item1 = “EE”;
String item2 = “B” + item1; // item2 = "BEE"
String item3 = “P”;
push (item2); // top => { "BEE" } <= bottom
push (item1);    // top => { "EE", "BEE" } <= bottom
push (item3 + item1); // top => { "PEE", "EE", "BEE" } <= bottom

item0 = stack.peek(); // item0 = "PEE"

pop(); // top => { EE", "BEE" } <= bottom
push (item2 + item3); // top => { "BEEP" ,"EE", "BEE" } <= bottom
push (item0); // top => { "PEE", "BEEP" ,"EE", "BEE" } <= bottom
push (item0 + item3); // top => { "PEEP", "PEE", "BEEP" ,"EE", "BEE" } <= bottom
item0 = stack.peek(); // item0 = "PEEP"
pop(); // top => { PEE", "BEEP" ,"EE", "BEE" } <= bottom

print (“Item0: ” + item0); // Item0: PEEP
print (“Item1: ” + item1); // Item1: EE
print (“Item2: ” + item2); // Item2: BEE
print (“Item3: ” + item3); // item3: P

while (!stack.isEmpty())
   item0 = stack.peek();   
   pop();
   print (“Item: ” + item0);

Output of while loop:
   Item: PEE
   Item: BEEP
   Item: EE
   Item: BEE

Please repos last question in separate post

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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