Data Structures
Hello, All In today’s blog we are going to see what Data Structures and What are different types of Data Structures and In the blog we are going to focus on Stack. So, let’s begin.
First, We will see what Data Structures are -
Data Structures are one of the core component of computer science department. Data Structures help you to solve a given problem in a efficient way and help you to think for the solution of problem in a better way.
Types of Data Structures :-
Linear Data Structures :-
A linear data structure has data elements connected to each other so that elements are arranged in a sequential manner and each element is connected to the element in front of it and behind it. This way, the structure can be traversed in a single run.
Non-Linear Data Structures :-
Data structures where data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the elements in single run only.
Now, Let’s Dive into first type of Linear Data Structure-
(i) Stack
Stack is a LIFO List means it works on the principle of Last In First Out. Means the Element which is on the Top of Stack are the Elements first get deleted from stack.
In Stack Insertion of an element is known as “Push” and deletion of an element is known as “Pop”. In Data Structures “Stack”, “Queue”, and “Linked List” are “Abstract Data Types”.
Now, let us see what is Abstract Data Types.
Abstract Data Types just shows what are different types of operations implement on the Data Type but how to implement is not a part of there Defination.
Implementation of Stacks are of Two Types in the Overview of C Programming Language.
We can also say that a Stack is a list with a pointer known as “Top Of Stack”. Every operation in stack is perform on the top of the Stack.
Now, Let’s get a deep dive into implementation of Stack with the help of Array.
Implemementation Of Stack In Array :-
Whenever there is Push operation we increment the Top. Whenever there is a Pop operation we Decrement the Top.
Complexity of isFull() is O(1).
Stack Overflow :- When our Stack is Full and we further want to Push an element in a Stack the condition is Known as “Stack OverFlow”.
Complexity of isEmpty() is O(1).
Stack support four types of functions-
(i)Full
(ii)Empty
(iii)Push
(iv)Pop
(v)Pep
Push and Pop Operation In Stack -
Now, We Will see Some Question Related to Stack.
Ques-1 Can You find the element which element is at bottom of stack?
Ans-1 Yes, we can say that we are implementing stack with the help of array. But practically, it is not possible because Stack only supports five operations only.
Ques-2 If we are implemenating stack with the help of the array such that top is at index zero always ? What is the Complexity of Push and Pop than ?
Ans -2 Let’s take an Example to understand these question.
If Top is at Index Zero always we need to shift the elements before pushing the elements in stack. Like We have Element 10 and 20 in stack and now we want to Push 30 in Stack so before pushing 30 we need to shift 10 and 20 first.
So, in these condition the complexity of Push and Pop becomes -
Push
Best Case = O(1) — — → When Stack is Empty
Worst Case = O(n) — — -> We need to traverse the Stack.
Pop
Best Case = O(1) — — → we get element at top of the stack only
Worst Case = O(n) — — -> We need to traverse the Stack.
That’s it for these Blog in next blog we will see Application of Stack. Thanks for reading my blog see u in next blog.