Data structures: Array implementation of stacks

See completeon data structures here:\r
\r
\r
In this lesson, we have discussed array based implementation of stack data structure.\r
\r
Source Code:\r
C code: \r
\r
C++ code (Object oriented implementation) : \r
\r
Time complexity of push for dynamic array implementation:\r
\r
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\r
\r
(1 + 2 + 4 + 8 + . + n/2 + n) \r
= n *( 1+ 1/2 + 1/4 + 1/8 + . 1/n) - taking out n \r
= n*2 - the expression in bracket above will evaluate to 2. \r
\r
So, cost of copy in n pushes = O(n)\r
Cost of n normal pushes = O(n) - each push takes constant time\r
Total cost of n pushes = O(n)\r
Average cost of 1 push = O(1). \r
\r
\r
For price problems and more, visit: \r
\r
Like us on Facebook: \r
\r
Follow us on twitter: