x # Data structures I

Other,

Updated On 02 Feb, 19

## Lecture 15: Data structures Array implementation of stacks

4.1 ( 11 )

###### Lecture Details

See complete series on data structures here

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

Source Code
C code httpsgist.github.commycodeschool6878252

C++ code (Object oriented implementation) httpsgist.github.commycodeschool6878628

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 + ... + n2 + n)
= n ( 1+ 12 + 14 + 18 + ... 1n) - taking out n
= n2 - 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 httpwww.mycodeschool.com

#### 0

0 Ratings
55%
30%
10%
3%
2% Sam

Excellent course helped me understand topic that i couldn't while attendinfg my college. 