When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized.
This will result in constant amortized time operations, but ~N in worst case.
Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links.
If occasional slow ops are bearable, then arrays would be a better option than linked lists.
Following is the complete program:
Related Posts:
No comments:
Post a Comment