The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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.
asked in Programming by Active (1.5k points) | 32 views
Both are true
delete stack() how will it happen in both cases?
Depends on how are you implementing stack using linked list and array .

You're convinced that with array it's constant right?

I'll explain with linked list .

Keep adding at head and keep updating start pointer.

While deletion , delete from head and set start pointer to start->next
if we have n elements in the link list deleting complete link list will take O(n) as we will delete each node and advance the head pointer to point the next node.

another way is that we can free() the head pointer but it is not the efficient way.

and in array too if we want to delete complete stack then we have to make each element as 0 (or defined otherwise)

here also it is taking O(n).
delete_stack() has been defined as new operation?
Then using linked list it will take O(n) , but with array , it is debatable .

Using free() might do the job , but my only concern is time complexity .

Please log in or register to answer this question.

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,540 questions
54,099 answers
71,006 users