The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
364 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 by Boss (17.2k points)
edited by | 364 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.

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

Related questions

+3 votes
1 answer
2
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
49,984 questions
55,135 answers
190,487 comments
85,107 users