+1 vote
419 views

Consider the following statements:
S1: If stack is implemented as an array, all the operation push, pop, is_empty stack ( ), delete stack ( ) can be performed in constant time.
S2: If stack is implemented as a linked list, all the operations is_empty stack, delete stack ( ) can be performed in constant time.
S3: Stack and queue both can be implemented will the help of same data structure.
S4: Circular queues can be implemented with the help of the stack data structure.
Which of the following option is false?

in DS
edited | 419 views
0
S1 S2 are true

S3. I didn't get it. If they mean as.. can be implemented by array, linked list then true.

I googled S4 and I find no solution to implement circular queue using stack. Must be false.
0
Answer is given as:

S1, S3, S4 -> true.

S2 -> false.

S3 seems ambiguous so leave it.

S4 should be true, because we can implement it with two stacks.

I think S2 should be true. But the given solution says: delete_stack() will take O(n).

We can delete the complete stack just by setting top pointer to NULL. But what about when we doit in C. We need to free the memory of each node, so can be said as O(n)?
+1
Queue can be implemented. I don't know about circular queue.

Yes. May be to avoid memory leak we need to free the memory.

But deletion can be done. Even push and pops in O(1) by making head of LL as stack top.
+1
delete stack cannot be done in O(1) time. Suppose it is last element of stack

Then deletion will take O(n) time, instead of O(1) time
+1

" S1: If stack is implemented as an array, all the operation push, pop, is_empty stack ( ), delete stack ( ) can be performed in constant time. "

how delete stack could be done in constant time?

Suppose it is last element of array, then u have to search every element to delete

right??

0
delete stack refers to delete the entire stack. Pop will refer to removing last element. Both can be done in O(1)

Delete stack -> set stack top to 0

Pop -> stack_top = stack_top -1

incase of array
+1
@ gauravkc
do u think, it is because of implement with linked list or array?
how far I know, implementation through stack using queue delete stack ( ) takes O(n)  time

like  think about deletion of 2nd element from top of stack
+1
Yes. Stack using queue and queue using stack can perform O(1) only in case of insertion or deletion but not both. Deleting a particular element might not happen in constant time though. Must be O(n) for any implementation.

But in question by delete stack they mean clear entire stack. If they were to refer to deleting a particular element, they would have named the function delete_element.
0
delete_stack will take o(n) time because you have to free every element in the stack.
0

@Arjun @Bikram sir, plz answer which one is false...

i think.

S4). Queue can be implemented using two stack or vice versa....but not sure about circular queue.

S3).  Don't understand ( i think ambiguous)

S2).  True

S1).  Push in constant time but confusion on delete stack- constant time ??

Pop ???

Delete_stack () using array cannot be performed in constant time since if we delete any element except last we have to shift all the other elements..so it will take O(n) time...

While empty_stack means emptying whole stack which takes O(1) time...correct me if i m wrong..
by (73 points)