GO Classes Test Series 2023 | Data Structures | Test 3 | Question: 8

Answer 1

Option D : If queue is implemented as a linked list –

Then we can maintain two pointers viz one pointing to the head of the LL and other pointing to the the tail of the LL. Enqueue operation can be done at the end pointed by the tail (creating new node at tail) and Dequeue operation can be done at the end pointed by the head (deleting a node at head).

In this way, both operations can be done in O(1) time.

*** Here, tail $\equiv$ rear and head $\equiv$ front. ***

---

Option B : If stack is implemented as a linked list –

Then we can maintain one pointer ie pointing to the head of the LL. Push operation can be done by creating new node at head and Pop operation can be done by deleting a node at head.

In this way, both operations can be done in O(1) time.

*** Here, head $\equiv$ top. ***

---

Option C : If queue is implemented as an array (Circular array implementation) – 

Then we can maintain two variables viz one indicating position of front and other indicating position of rear.

Enqueue operation can be done by first incrementing rear appropriately then inserting element at rear.

Dequeue operation can be done by taking element from location front and then incrementing front appropriately.

In this way, both operations can be done in O(1) time.

*** |queuq| = |array| = n, empty and full conditions must also be checked, incrementing front/rear must be followed by mod n operation. ***

---

Option A : If stack is implemented as an array – 

Then we can maintain one variable ie indicating position of top.

Push operation can be done by first incrementing top then inserting element at top.

Pop operation can be done by taking element from location top and then decrementing top.

In this way, both operations can be done in O(1) time.

​​​​​​​*** |stack| = |array| = n, empty and full conditions must also be checked. ***

---

Answer :- A, B, C, D.

Comments

In option B When u maintain head as top and add nodes your top must increment too, when during pop how do u do it in O(1) time? I didnt understand it.

---

We can insert new node at the beginning of LL in O(1) time, this is our push operation. And we make head point to this new node.

We can delete a node pointed by head (first node) of a LL in O(1) time, this is our pop operation. Here, we make head point to second node, which becomes first after deletion. And before deleting we save value of node pointed by head to return later.

(All these are standard implementations)

---

@shishir__roy

if the head/top pointer points to the 1^st  node of the linked list

when to delete/pop the last element of stack, we need to traverse to the last and previous of last node of the linked list(as the stack follows( LIFO) which can not be done in a constant time when pointing to 1^st node of linked list

plz correct me...

Answer 2

By “Udhay Brahmi”

By “Udhay Brahmi”