The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
29 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.
asked in Programming by Active (1.2k points) | 29 views
0
Both are true
0
delete stack() how will it happen in both cases?
0
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
0
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).
0
delete_stack() has been defined as new operation?
0
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.

Related questions

0 votes
0 answers
2
asked 5 days ago in Programming by himgta Active (3.3k points) | 28 views
0 votes
1 answer
4
asked Jan 11 in Programming by Shadan Karim Junior (939 points) | 28 views
0 votes
0 answers
5
asked Jan 11 in Programming by Ajit J (423 points) | 55 views


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

47,080 questions
51,333 answers
177,706 comments
66,675 users