DATA STRUCTURES
A Data Structure is a method of organizing and storing data in a computer so that it can be
accessed, processed, and modified efficiently. In Simple Words, it is a way to arrange data
so that operations like searching, inserting, and deleting can be done easily.
Every Data Structure provides:
1) A specific way of storing data in memory .
2) A set of well-defined operations that can be performed easily once the data is
organized in that fashion.
For Eg: An Array is a data structure that allows us to store data of similar datatype in
contiguous memory locations under a single name . By storing data in this format, it
becomes easy to perform operations such as searching, sorting, traversing, inserting a new
element or deleting an existing element etc.
CLASSIFICATION OF DATA STRUCTURES:
NOTE : Our Scope of Syllabus only covers Linear Data Structures (Arrays, Stack,
Linear Queue, Circular Queue, Deque, Linked Lists) and Binary Trees.
Linear data structures : are the single- level data structures where elements form a
sequence.
LINKED LIST
STACK
• The stack is a linear data-structure.
• It works on the principle of LIFO (LAST IN FIRST OUT) which means the data
inserted at the last in Stack will be deleted first.
• A stack is an array or a list with the restriction that insertions and deletions can only be
performed at one end called the top .
IMPLEMENTATION OF STACK
A Stack may be implemented in two ways:
1) Using an array: When a stack is implemented through an array, it is known as Static
Stack.
2) Using a linked List : When a stack is implemented through a linked list, it is known
as Dynamic Stack.
NOTE: Our Scope of syllabus is limited to implementation of Stack, Linear Queue,
Circular Queue and Dequeue using an array only.
When an array is restricted to follow the principle of LIFO, such an array is termed as Static
Stack.
Operations on Stack:
1) PUSH Operation: means inserting an element at the top of the stack.
2) POP Operation: means the topmost element from the stack.
3) PEEK Operation: returns the topmost element of the stack without removing it.
4) DISPLAY Operation: is used to display all the elements of the Stack usually from
Top through Index No . 0.
Exceptional Situations to be handled during Stack Operations:
While performing operations on a Stack (LIFO), certain error conditions must be handled to
avoid incorrect execution.
[Link] Overflow: Occurs when we try to push (insert) an element into a full stack.
Condition: if (top == size – 1)
Explanation:
• The stack has reached its maximum capacity.
• No more elements can be added.
Example: If stack size = 5 and top = 4, pushing another element → Overflow
2. Stack Underflow: Occurs when we try to pop (delete) an element or display elements
from an empty stack.
Condition: if ( top == -1)
Explanation:
• There are no elements in the stack.
• Deletion is not possible.
Example:
If top = -1, performing pop → Underflow
If top = -1, displaying elements of Stack → Underflow
CODING :
IMPLEMENTING STACK USING AN ARRAY
import [Link];
public class stack
{
int a[];
int top,size;
public stack(int s)
{
size=s;
a=new int[size];
top=-1;
}
public void push(int e)
{
if(top==size-1)
[Link]("Stack overflow");
else
{
top++;
a[top]=e;
[Link](e+ "inserted successfully");
}
}
public int pop()
{
if(top==-1) // Stack Empty
return -999;
else
return a[top--]; // returning the deleted element and updating top
}
void display()
{
if(top==-1)
[Link]("Stack Empty !! Underflow");
else
{
for(int i=top; i>=0; i--)
[Link](a[i]+"--->");
}
}
public static void main()
{
Scanner sc=new Scanner([Link]);
[Link]("Enter Stack size");
int n=[Link]();
stack ob = new stack(n);
int ch, val;
do {
[Link]("\n--- STACK MENU ---");
[Link]("1. Push an element");
[Link]("2. Pop on element");
[Link]("3. Display the elements of Stack");
[Link]("4. Exit");
[Link]("Enter your choice: ");
ch = [Link]();
switch(ch)
{
case 1:
[Link]("Enter element to push: ");
val = [Link]();
[Link](val);
break;
case 2:
val = [Link]();
if(val == -999)
[Link]("Stack Underflow");
else
[Link]("Deleted element: " + val);
break;
case 3:
[Link]();
break;
case 4:
[Link]("Exiting...");
break;
default:
[Link]("Invalid Choice");
}
} while(ch != 4);
}
}
APPLICATIONS OF STACK:
1. Expression Evaluation
• Used to evaluate postfix and prefix expressions
• Helps in solving mathematical expressions efficiently.
2. Conversion of Expressions
• Infix → Postfix
• Infix → Prefix
Stack is used to handle operators and precedence.
3. Function Calls / Recursion
• Stack is used internally by the system (Call Stack)
• Stores:
o Function calls
o Local variables
o Return addresses
Example: Recursive functions
4. Checking Balanced Parentheses
• Used to check whether brackets are properly matched
Example:
• { ( ) } → Valid
• { ( ] } → Invalid
5. Undo / Redo Operations
• Used in applications like text editors
Example:
• Undo last typing action
• Redo previously undone action