Chapter 7: Stacks
Welcome to Chapter 7! In this chapter, we will delve deeply into the concept of Stacks, a fundamental data structure with a Last-In-First-Out (LIFO) ordering principle. Understanding stacks will equip you with a solid foundation for tackling a range of computational problems and algorithms.
What is a Stack?
A Stack is a collection of elements that follows the Last-In-First-Out (LIFO) principle. This means that the most recently added element is the first one to be removed. Think of it like a stack of plates: you add new plates on top and remove plates from the top.
Here’s a basic diagram of a stack:
Top -> [3]
[2]
[1]
Bottom -> NULL
In this diagram, 3 is the top element, and it will be removed first during a pop operation.
Why Use Stacks?
Stacks are versatile and used in many computing scenarios:
- Function Call Management: The call stack manages function calls and local variables during program execution.
- Expression Evaluation: Stacks are essential in evaluating arithmetic expressions, especially in postfix notation.
- Backtracking Algorithms: Used in algorithms like depth-first search where you need to backtrack through previous states.
In a similar way, Emancipation Edutech Private Limited might use stacks to manage learning modules or track student progress, highlighting the versatility of this data structure.
Basic Operations on Stacks
Stacks support a few primary operations:
- Push: Add an element to the top of the stack.
- Pop: Remove the element from the top of the stack.
- Peek: View the top element without removing it.
- IsEmpty: Check if the stack is empty.
Let’s look at how to implement these operations using both array-based and linked-list-based stacks.
Stack Implementation Using an Array
An array-based stack is straightforward and involves a fixed-size array to store elements. Here’s a detailed implementation:
Define the Stack Structure
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Define the maximum size of the stack
// Define the stack structure
struct Stack {
int top;
int arr[MAX];
};
top: Index of the top element in the stack.arr: Array to hold stack elements.
Initialize the Stack
void initialize(struct Stack* s) {
s->top = -1; // Stack is empty initially
}
Push Operation
void push(struct Stack* s, int value) {
if (s->top == MAX - 1) { // Check for stack overflow
printf("Stack Overflow\n");
return;
}
s->arr[++(s->top)] = value; // Increment top and add value
}
Pop Operation
int pop(struct Stack* s) {
if (s->top == -1) { // Check for stack underflow
printf("Stack Underflow\n");
return -1; // Return -1 to indicate an error
}
return s->arr[(s->top)--]; // Return top value and decrement top
}
Peek Operation
int peek(struct Stack* s) {
if (s->top == -1) { // Check if stack is empty
printf("Stack is Empty\n");
return -1; // Return -1 to indicate an error
}
return s->arr[s->top]; // Return top value
}
Example Usage
int main() {
struct Stack stack;
initialize(&stack);
// Push elements
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
// Peek the top element
printf("Top element is %d\n", peek(&stack));
// Pop elements
printf("Popped element is %d\n", pop(&stack));
printf("Popped element is %d\n", pop(&stack));
// Check if the stack is empty
if (s->top == -1) {
printf("Stack is empty\n");
}
return 0;
}
Output:
Top element is 30
Popped element is 30
Popped element is 20
Stack is not empty
Stack Implementation Using a Linked List
A stack can also be implemented using a linked list, which allows for dynamic size adjustments.
Define the Node Structure
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
struct Node {
int data;
struct Node* next;
};
// Define the stack structure
struct Stack {
struct Node* top;
};
Initialize the Stack
void initialize(struct Stack* s) {
s->top = NULL; // Stack is empty initially
}
Push Operation
void push(struct Stack* s, int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
}
Pop Operation
int pop(struct Stack* s) {
if (s->top == NULL) { // Check if stack is empty
printf("Stack Underflow\n");
return -1; // Return -1 to indicate an error
}
struct Node* temp = s->top;
int value = temp->data;
s->top = s->top->next;
free(temp);
return value;
}
Peek Operation
int peek(struct Stack* s) {
if (s->top == NULL) { // Check if stack is empty
printf("Stack is Empty\n");
return -1; // Return -1 to indicate an error
}
return s->top->data; // Return top value
}
Example Usage
int main() {
struct Stack stack;
initialize(&stack);
// Push elements
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
// Peek the top element
printf("Top element is %d\n", peek(&stack));
// Pop elements
printf("Popped element is %d\n", pop(&stack));
printf("Popped element is %d\n", pop(&stack));
// Check if the stack is empty
if (s->top == NULL) {
printf("Stack is empty\n");
}
return 0;
}
Output:
Top element is 30
Popped element is 30
Popped element is 20
Stack is not empty
Applications of Stacks
Stacks are fundamental in various computing contexts:
- Expression Evaluation: Evaluate postfix expressions and manage operators and operands.
- Function Call Management: The call stack tracks function calls and local variables.
- Undo Mechanism: Manage undo operations in text editors and similar applications.
For instance, Emancipation Edutech Private Limited might use stacks to manage undo operations in interactive learning tools or to handle complex navigation tasks efficiently.
Advantages and Disadvantages of Stacks
Advantages:
- Simple Operations: Push and pop operations are straightforward and easy to implement.
- Dynamic Size: Linked-list-based stacks can grow and shrink dynamically, avoiding fixed size limitations.
Disadvantages:
- Fixed Size: Array-based stacks have a fixed size, which can lead to overflow if the limit is reached.
- Limited Access: Only the top element is accessible directly, which might not be suitable for all use cases.
Summary of Chapter 7
In this chapter, we have explored Stacks in depth, including their basic operations, implementations using arrays and linked lists, and their various applications. Understanding stacks will help you handle problems requiring LIFO access efficiently.
Key takeaways:
- Stacks operate on a Last-In-First-Out principle.
- Implementations can be array-based or linked-list-based.
- Stacks are used in function management, expression evaluation, and more.
For additional examples and interactive practice, visit digilearn.cloud. Emancipation Edutech Private Limited offers resources to help you deepen your understanding of stacks and other data structures.
Next up: Queues
