STACK through C
Stack in Data Structures
1. Introduction to Stack
A stack is one of the most important linear data structures used in computer science. It follows a specific order for storing and accessing data known as the LIFO principle (Last In, First Out).
This means that the element inserted last into the stack will be the first one to be removed.
A simple real-life example of a stack is a stack of plates in a kitchen. When plates are placed one on top of another, the last plate placed on top is the first one removed.
Stacks are widely used in:
- Programming languages
- Operating systems
- Expression evaluation
- Memory management
- Undo/redo operations
2. Basic Concept of Stack
A stack works like a vertical structure where elements are inserted and removed from the same end, called the top.
Two important operations are performed on a stack:
- Push – Insert an element into the stack
- Pop – Remove an element from the stack
The position from which insertion and deletion occur is called the TOP.
Example:
Top
|
30
20
10
If we push 40, the stack becomes:
Top
|
40
30
20
10
If we pop an element, 40 will be removed first.
3. Characteristics of Stack
The stack data structure has several important characteristics:
- It follows the LIFO principle (Last In First Out).
- Insertion and deletion happen only from one end (Top).
- It is a linear data structure.
- It can be implemented using arrays or linked lists.
- The stack size may be fixed or dynamic.
4. Basic Operations of Stack
The stack supports several basic operations.
4.1 Push Operation
The push operation is used to insert a new element into the stack.
Steps:
- Check if the stack is full.
- Increase the value of top.
- Insert the element at the top position.
Example:
Before push:
Top
|
30
20
10
Push 40:
Top
|
40
30
20
10
4.2 Pop Operation
The pop operation removes the top element from the stack.
Steps:
- Check if the stack is empty.
- Store the top element.
- Decrease the top value.
Example:
Before pop:
Top
|
40
30
20
10
After pop:
Top
|
30
20
10
4.3 Peek Operation
The peek operation returns the top element of the stack without removing it.
Example:
Stack:
Top
|
30
20
10
Peek → returns 30
4.4 isEmpty Operation
This operation checks whether the stack is empty.
Condition:
top == -1
4.5 isFull Operation
This operation checks whether the stack is full.
Condition:
top == MAX - 1
5. Stack Implementation Using Array in C
A stack can be implemented using arrays in the C programming language.
Stack Structure
We define:
- Array to store elements
- Variable top to track the top position
Example:
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
Push Operation in C
void push(int value)
{
if(top == MAX-1)
{
printf("Stack Overflow\n");
}
else
{
top++;
stack[top] = value;
}
}
Pop Operation in C
void pop()
{
if(top == -1)
{
printf("Stack Underflow\n");
}
else
{
printf("Deleted element: %d\n", stack[top]);
top--;
}
}
Display Stack
void display()
{
int i;
if(top == -1)
{
printf("Stack is empty\n");
}
else
{
for(i = top; i >= 0; i--)
{
printf("%d\n", stack[i]);
}
}
}
6. Stack Implementation Using Linked List
Another way to implement a stack is using a linked list.
In this method:
- Each node contains data
- A pointer to the next node
Structure of node:
struct node
{
int data;
struct node *next;
};
Advantages:
- Dynamic memory allocation
- No fixed size
7. Stack Overflow and Stack Underflow
Stack Overflow
Stack overflow occurs when we try to insert an element into a full stack.
Example condition:
top == MAX - 1
Example message:
Stack Overflow
Stack Underflow
Stack underflow occurs when we try to remove an element from an empty stack.
Example condition:
top == -1
Example message:
Stack Underflow
8. Applications of Stack
Stacks are widely used in computer science.
8.1 Function Calls
When a function is called in a program, the system stores the function details in a call stack.
Example:
- Local variables
- Return address
- Parameters
8.2 Expression Evaluation
Stacks are used to evaluate expressions such as:
- Infix
- Prefix
- Postfix expressions
Example:
A + B
Can be converted to:
AB+
8.3 Parenthesis Checking
Stacks help check balanced parentheses.
Example:
( A + B ) * ( C + D )
8.4 Undo and Redo Operations
Many applications use stacks for undo operations.
Examples:
- Text editors
- Photoshop
- Word processors
8.5 Backtracking Algorithms
Stacks are used in algorithms like:
- Maze solving
- Depth First Search (DFS)
- Path finding
8.6 Browser History
Web browsers use stacks to store visited pages.
Example:
- Back button
- Forward button
9. Advantages of Stack
Stacks provide several benefits:
- Simple implementation
- Efficient insertion and deletion
- Useful in recursion
- Helps manage function calls
- Important for expression evaluation
10. Disadvantages of Stack
Despite its advantages, stacks also have limitations:
- Limited access (only top element)
- Fixed size in array implementation
- Overflow and underflow problems
- Not suitable for searching elements
11. Real Life Examples of Stack
Stacks can be observed in many real-world situations.
Examples:
- Stack of books
- Stack of plates
- Browser history
- Undo operations in software
- Function call stack in programming
12. Conclusion
A stack is a fundamental data structure used in programming and computer science. It follows the Last In First Out (LIFO) principle, meaning the last element inserted is the first one removed.
The main operations of a stack include push, pop, peek, isEmpty, and isFull. Stacks can be implemented using arrays or linked lists in the C programming language.
Stacks are extremely useful in many areas such as function calls, expression evaluation, recursion, browser history, and undo operations. Due to their simplicity and efficiency, stacks remain one of the most widely used data structures in software development.
Understanding stacks is essential for students learning data structures and algorithms, as they form the foundation for solving many complex programming problems.
Comments
Post a Comment