The Gateway to Computer Science Excellence
+1 vote

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 by Boss (18k points)
edited by | 419 views
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.
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)?
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.
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

" 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


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
@ 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
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.
delete_stack will take o(n) time because you have to free every element in the stack.

@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 ???


1 Answer

0 votes
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 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)

Related questions

+3 votes
3 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,834 questions
57,753 answers
108,201 users