This content requires JavaScript and Macromedia Flash Player 7 or higher. Get Flash

Data structures: Array implementation of stacks


See complete series on data structures here:

In this lesson, we have discussed array based implementation of stack data structure.

Source Code:

C code:

C++ code (Object oriented implementation) :

Time complexity of push for dynamic array implementation:

If we start with an array of size 1 and keep doubling the size with each overflow, for n pushes.. cost of copy will be

(1 + 2 + 4 + 8 + ... + n/2 + n)

= n *( 1+ 1/2 + 1/4 + 1/8 + ... 1/n) - taking out n

= n*2 - the expression in bracket above will evaluate to 2.

So, cost of copy in n pushes = O(n)

Cost of n normal pushes = O(n) - each push takes constant time

Total cost of n pushes = O(n)

Average cost of 1 push = O(1).

For practice problems and more, visit:

Like us on Facebook:

Follow us on twitter:

Category:  uncategorized
Published:  3 years ago

Please select playlist name from following
Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn't appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don't do it.
Comments 0