Data structures - Data structures: Array implementation of stacks

See complete series on data structures here: http://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P In this lesson, we have discussed array based implementation of stack data structure. Source Code: C code: https://gist.github.com/mycodeschool/6878252 C++ code (Object oriented implementation) : https://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: http://www.mycodeschool.com Like us on Facebook: https://www.facebook.com/MyCodeSchool Follow us on twitter: https://twitter.com/mycodeschool