Stack

Question

Consider a stack and we wish to perform an operation StackDelete() in which we wish to delete all the elements of the stack .What is the worst case time complexity of doing this if stack is implemented:

1) Using an array

2)Using a Linked list

Comments

it will be O(n) time in an array,

in linked list, it can take O(1) time, if you simply remove pointer from top of stack, but if you want that memory also be needed to free up, then it will take O(n) time.

---

array takes worst time ....

---

@joshi_nitish

Linked list point , I agree with you

Array I was thinking like this :

Suppose in array implementation we have 2 variables one pointing to starting and one ending of stack(TOS variable).Now, as you mentioned 2 cases here:

1) Set TOS=-1

2) If memory needs to be deallocated we could use free()  in C , Delete() in C++ , and in java set arr=null(as we have garbage collection in it)

In any case O(1) time :)

---

i was answering in accordance with C, assuming no predefined functions are available and assuming that to delete each element of array simply means setting  $A[i]=0$  $\forall i\epsilon [0,n]$

---

In the question asked to delete the elements.

So even we change the top of the stack the array is not empty, we can access the elements of the array So they are not deleted untill we again replace with some other elements or delete them.

But in case of linked lists if we change the pointer once we cant again access them so in this case the elements are deleted even they may be in the memory but we cant access them

---

@joshi_nitish

Agreed !

But, if a question like this is asked in gate , shouldn't we consider functions like free() are by default there ?

---

in case of linked list, free() is trivial function, but for array i don't think predefined function is to be taken until mentioned exlplicitly.

---

@joshi_nitish

https://stackoverflow.com/questions/15298822/delete-whole-array-in-c

---

@VS

there array is dynamic array, where memory is allocated using malloc(). but generally by default we take static array in which memory is binded up throughout lifetime of a function(in which array is declared) or throughout lifetime of program(if array declared globally).

in case of static allocation deallocation of a array memory is not possible(i think so) because memory is allocated during compile time itself rather than runtime.

---

@joshi_nitish

I think then the answer depends on how memory is allocated to an array.

1) Dynamic --> StackDelete() -->O(1)

2)Static --> StackDelete() -->O(n)

But, what is the default case then ?

---

@VS

if asked in GATE, qsn will be properly framed avoiding any type of abguity that may arise