Uploaded October 2013 | Updated September 2026, 2 weeks ago

---

See complete series on data structures here:
youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P

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

Source Code:
C code: gist.github.com/mycodeschool/6878252

C++ code (Object oriented implementation) : gist.github.com/mycodeschool/6878628

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: mycodeschool.com

Like us on Facebook: facebook.com/MyCodeSchool

Follow us on twitter: twitter.com/mycodeschool