3,976 views

3 Answers

2 votes
2 votes

For all the standard stack operations (push, pop, isEmpty, size), the worst-case run-time complexity can be O(1). We say can and not is because it is always possible to implement stacks with an underlying representation that is inefficient. However, with the representations we have looked at (static array and a reasonable linked list) these operations take constant time. It's obvious that size and isEmpty constant-time operations. push and pop are also O(1) because they only work with one end of the data structure - the top of the stack. The upshot of all this is that stacks can and should be implemented easily and efficiently.

ref:http://pages.cs.wisc.edu/~siff/CS367/Notes/stacks.html

1 votes
1 votes
stack data structure be like :1)STACK 2)STACK POINTER (points to top of stack) let's say stack starts from address AA1 and ends in KK1.initially stack pointer points to address (AA1-001)... ok now lets come to the operation isempty() if stack pointer points to (AA1-001) isfull() if stack pointer points to KK1 size() STACK POINTER - AA1 delete() pop STACK[STACK POINTER] and free[STACK POINTER] all of these operations take constant time
0 votes
0 votes
Let me assume you are using list.is empty will just check the tos pointer.so order 1.similarly for isfull.no need to traverse the whole list.however delete will take order n if list is used.order 1 if array.

1->2->3->4

Try.

Related questions

1 votes
1 votes
1 answer
2
radha gogia asked Jul 24, 2018
1,312 views
Suppose one character at a time comes as an input from a string of letters . There is an option either to 1) print the incoming letter or to 2) put the incoming letter on...