+1 vote
377 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 | 377 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

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.