Data structures I


Updated On 02 Feb, 19


Introduction to data structures - Data Structures: List as abstract data type - Introduction to linked list - Data Structures: Arrays vs Linked Lists - Linked List - Implementation in C/C++,Linked List in C/C++:Inserting a node at beginning,Insert a node at nth position,Delete a node at nth position - Reverse a linked list - Iterative method - Print elements of a linked list in forward and reverse order using recursion - Reverse a linked list using recursion - Data structures: Introduction to Doubly Linked List - Doubly Linked List - Implementation in C/C++ - Data structures: Introduction to stack - Data structures: Array implementation of stacks - Data Structures: Linked List implementation of stacks - Reverse a string or linked list using stack - Check for balanced parentheses using stack - Infix, Prefix and Postfix - Evaluation of Prefix and Postfix expressions using stack - Infix to Postfix using stack - Data structures: Introduction to Queues,Array implementation of Queue,Linked List implementation of Queue,Introduction to Trees,Binary Tree,Binary Search Tree - Binary search tree - Implementation in C/C++ - BST implementation - memory allocation in stack and heap - Find min and max element in a binary search tree - Find height of a binary tree - Binary tree traversal - breadth-first and depth-first strategies - Binary tree: Level Order Traversal - Binary tree traversal: Preorder, Inorder, Postorder - Check if a binary tree is binary search tree or not - Delete a node from Binary Search Tree - Inorder Successor in a binary search tree - Data structures: Introduction to graphs - Data structures: Properties of Graphs - Graph Representation:Edge List,Adjacency Matrix


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

Like us on Facebook httpswww.facebook.comMyCodeSchool

Follow us on twitter httpstwitter.commycodeschool



0 Ratings
comment person image


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

comment person image


Great course. Thank you very much.