Data structures: Array implementation of stacks

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

• Category

  Film & Animation