Data Structures in C / C++
Section 8: Data Structures in C/C++
Lesson 1: Introduction to Data Structures
1.1 Overview of Data Structures
Data structures are fundamental components for organizing and storing data efficiently. They provide a way to represent and manipulate information in a computer's memory.
1.2 Importance of Data Structures
Efficiency: Data structures enable efficient storage and retrieval of data.
Functionality: Different data structures serve various purposes, supporting tasks like searching, sorting, and organizing information.
Problem Solving: Effective use of data structures is crucial for solving complex problems in computer science.
Lesson 2: Arrays, Linked Lists, Stacks, and Queues
2.1 Arrays
Arrays are a contiguous collection of elements with each element accessible by its index. They provide constant-time access to elements but have a fixed size.
Example (Arrays in C):
#include <stdio.h>
int main() {
// Declaration and initialization of an array
int numbers[5] = {1, 2, 3, 4, 5};
// Accessing elements
printf("Element at index 2: %d\n", numbers[2]);
return 0;
}
2.2 Linked Lists
Linked lists consist of nodes, each containing data and a reference (link) to the next node. They offer dynamic size and efficient insertion and deletion.
Example (Linked List in C):
#include <stdio.h>
#include <stdlib.h>
// Node structure for a singly linked list
struct Node {
int data;
struct Node* next;
};
int main() {
// Creating nodes
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 2;
// Linking nodes
head->next = second;
second->next = NULL;
return 0;
}
2.3 Stacks
Stacks follow the Last In, First Out (LIFO) principle, allowing operations at one end (top). They are used in functions like undo, redo, and expression evaluation.
Example (Stack in C++):
#include <iostream>
#include <stack>
int main() {
// Stack declaration
std::stack<int> myStack;
// Pushing elements onto the stack
myStack.push(1);
myStack.push(2);
myStack.push(3);
// Popping elements from the stack
while (!myStack.empty()) {
std::cout << "Popped: " << myStack.top() << std::endl;
myStack.pop();
}
return 0;
}
2.4 Queues
Queues follow the First In, First Out (FIFO) principle, allowing operations at both ends (enqueue and dequeue). They are used in scenarios like task scheduling and print spooling.
Example (Queue in C++):
#include <iostream>
#include <queue>
int main() {
// Queue declaration
std::queue<int> myQueue;
// Enqueuing elements
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
// Dequeuing elements
while (!myQueue.empty()) {
std::cout << "Dequeued: " << myQueue.front() << std::endl;
myQueue.pop();
}
return 0;
}
Lesson 3: Implementing Data Structures in C/C++
3.1 Implementation of Arrays
Arrays can be implemented using static or dynamic memory allocation. Dynamic arrays allow flexibility in size but require manual memory management.
Example (Dynamic Array in C):
#include <stdio.h>
#include <stdlib.h>
int main() {
// Dynamic array declaration and initialization
int* dynamicArray = (int*)malloc(5 * sizeof(int));
if (dynamicArray != NULL) {
for (int i = 0; i < 5; i++) {
dynamicArray[i] = i + 1;
}
// Accessing elements
printf("Element at index 2: %d\n", dynamicArray[2]);
// Freeing allocated memory
free(dynamicArray);
}
return 0;
}
3.2 Implementation of Linked Lists
Linked lists can be implemented using structures to define nodes and pointers to establish connections between nodes.
Example (Singly Linked List in C):
#include <stdio.h>
#include <stdlib.h>
// Node structure for a singly linked list
struct Node {
int data;
struct Node* next;
};
int main() {
// Creating nodes
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 2;
// Linking nodes
head->next = second;
second->next = NULL;
// Accessing elements
printf("Element at head: %d\n", head->data);
printf("Element at second: %d\n", second->data);
// Freeing allocated memory
free(head);
free(second);
return 0;
}
3.3 Implementation of Stacks and Queues
Stacks and queues can be implemented using arrays or linked lists, depending on the requirements.
Example (Stack Implementation using Array in C++):
#include <iostream>
class Stack {
private:
static const int maxSize = 5;
int top;
int stackArray[maxSize];
public:
Stack() : top(-1) {}
void push(int value) {
if (top < maxSize - 1) {
stackArray[++top] = value;
std::cout << "Pushed: " << value << std::endl;
} else {
std::cerr << "Stack Overflow!" << std::endl;
}
}
void pop() {
if (top >= 0) {
std::cout << "Popped: " << stackArray[top--] << std::endl;
} else {
std::cerr << "Stack Underflow!" << std::endl;
}
}
};
int main() {
// Stack usage
Stack myStack;
myStack.push(1);
myStack.push(2);
myStack.pop();
myStack.push(3);
return 0;
}
Example (Queue Implementation using Linked List in C++):
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
void enqueue(int value) {
Node* newNode = new Node(value);
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
std::cout << "Enqueued: " << value << std::endl;
}
void dequeue() {
if (front != nullptr) {
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
std::cout << "Dequeued: " << temp->data << std::endl;
delete temp;
} else {
std::cerr << "Queue Underflow!" << std::endl;
}
}
};
int main() {
// Queue usage
Queue myQueue;
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.dequeue();
myQueue.enqueue(3);
return 0;
}
Understanding data structures and their implementations in C and C++ is foundational for efficient algorithm design and problem-solving. Practice creating and using arrays, linked lists, stacks, and queues to build a strong foundation in data structures.