Arrays:
An array is a programming data structure for storing elements in a linear sequence.
Each element is identified by an index, typically a whole number, and they’re stored in contiguous memory for efficient access and manipulation.
How arrays are stored in memory
Contiguous Memory Allocation:
-> Arrays are stored in contiguous memory locations.
-> This means that all elements of the array are stored next to each other in memory.
-> The address of each element is calculated by adding the size of the element to the address of the previous element.
-> In this case, the elements of the arr array are integers, which are 4 bytes in size.
-> Therefore, the address of the second element in the array is 4 bytes more than the address of the first element, and so on.
Brute Force Solution:
Brute force is a basic and exhaustive method that involves trying all possible options until the desired outcome is achieved.
Implementing a brute-force solution is typically straightforward, but it may not be the most efficient approach in many cases.
Optimal Solution:
An optimal solution in programming is the most efficient way to solve a problem, aiming to minimize time and memory usage while achieving the correct results.
Optimal solutions are highly valued for their ability to lead to faster and more resource-efficient programs.
->Given an array of integers, your task is to remove any duplicate elements from the array. After removing duplicates, print the number of unique elements and the modified array.
->Ensure that the first ‘k’ elements in the array contain the final result, where ‘k’ is the number of unique elements.
->There are no specific requirements for the order of elements beyond ‘k’ in the array.
Brute Force Approach:
->Initialize a set to store unique elements.
->Iterate through the array and add each element to the set.
->Use a variable to keep track of the updated array index while iterating through the set.
Program:
#include<bits/stdc++.h>
using namespace std;
int remove_duplicates(int a[], int n)
{
set s;
for(int i=0;i<=n-1;i++) { s.insert(a[i]); } int j=0; for(auto k: s) { a[j]=k; j++; } return s.size(); } int main() { int n; cin>>n;
int a[n];
for(int i=0;i<n;i++) { cin>>a[i];
}
cout<<remove_duplicates(a,n)<<endl;
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Optimal Approach:
->Set the index variable i to 0 as an initial step.
->Traverse the array starting from the second element using the variable j.
->If the current element (j) differs from the previous one (i), replace the element at index i+1 with the current element and increment the value of i.
Program:
#include<bits/stdc++.h>
using namespace std;
int remove_duplicates(int a[], int n)
{
int i = 0;
for(int j=1;j<=n-1;j++) { if(a[i]!=a[j]) { a[i+1]=a[j]; i++; } } return (i+1); } int main() { int n; cin>>n;
int a[n];
for(int i=0;i<n;i++) { cin>>a[i];
}
cout<<remove_duplicates(a,n)<<endl;
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Stacks:
A stack is a collection of elements that are inserted and removed according to the Last-In-First-Out (LIFO) principle.
The stack has two principal operations:
push() : adds an element to the collection.
pop() : removes the most recently added element.
The condition of trying to push an element into a full stack is called overflow.
The condition of trying to pop out an empty stack is called underflow.
Stack Operations:
push()
Inserts a new element at the top of the stack.
mystack.push(10);
pop()
Removes the element from the top of the stack.
mystack.pop();
size()
Returns number of elements in the stack.
mystack.size();
top()
Returns a reference to the top element in the stack.
mystack.top();
empty()
Returns whether the stack is empty or not.
mystack.empty();
Program:
#include<iostream>
#include<vector>
class Stack {
private:
std::vector stack;
public:
void push(int value) {
stack.push_back(value);
}
void pop() {
if (!isEmpty()) {
stack.pop_back();
} else {
std::cout << "Stack is empty. Cannot pop.\n";
}
}
int top() const {
if (!isEmpty()) {
return stack.back();
} else {
std::cerr << "Stack is empty. No top element.\n";
return -1; // You may choose a different way to handle this situation
}
}
bool isEmpty() const {
return stack.empty();
}
};
int main() {
Stack myStack;
myStack.push(5);
myStack.push(10);
myStack.push(15);
std::cout << "Top element: " << myStack.top() << "\n";
myStack.pop();
std::cout << "Top element after pop: " << myStack.top() << "\n";
return 0;
}
About Vector:
Vectors are like dynamic arrays, automatically resizing as elements are added or removed with contiguous storage for easy access
To use the vector library in C++, include the <vector> header and can also be used by adding <bits/stdc++.h>
Arrays v/s Vectors:
Vectors are dynamic arrays, whereas arrays have a fixed size.
Vectors automatically manage their memory, while arrays require manual memory management.
Queue:
In C++ STL (Standard Template Library), a queue is a container that adheres to the First-In-First-Out (FIFO) principle, ensuring the first element added is the first to be removed.
Real Life Use Case:
The supermarket checkout queue exemplifies a real-life application of a queue, where customers arrive, join in FIFO order, are served one at a time, and new arrivals continue to join the back.
Basic Operations:
#include<iostream>
#include<queue>
int main() {
std::queue myQueue;
// Push elements to the queue
myQueue.push(10); // {10}
myQueue.push(20); // {10, 20}
myQueue.push(30); // front -> {10, 20, 30} -> back
// Front and Back
std::cout << "Front element: " << myQueue.front() << std::endl; // Output: Front element: 10
std::cout << "Back element: " << myQueue.back() << std::endl; // Output: Back element: 30
// Pop the front element
myQueue.pop();
std::cout << "After popping, front element: " << myQueue.front() << std::endl; // Output: After popping, front element: 20
return 0;
}
->queue<int> myQueue Declare a queue named myQueue for storing integers
->myQueue.push() Push an integer into the queue
->myQueue.front() Print the front element of the queue
->myQueue.back() Print the back element of the queue
->myQueue.pop() Remove the front element from the queue. After this, the front element becomes the next element in the queue
Priority Queue:
->In C++ STL, a priority queue is a container for elements arranged in a specific priority order, with the highest-priority element at the top by default, typically implemented as a max heap.
->Priority queues, not linear structures, are often implemented as binary heaps, offering efficient operations to keep the highest-priority element at the forefront.
Max Heap or Max Priority Queue:
#include<iostream>
#include // or use #include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue pq; // Creating a max heap priority queue
// Push elements into the priority queue
pq.push(30); // pq = {30}
pq.push(10); // pq = {30,10}
pq.push(50); // pq = {50, 30, 10}
pq.push(20); // pq = {50, 30, 20, 10}
// Print the top element (element with the highest priority) without removing it
cout << "Top element: " << pq.top() << endl; // 50
// Pop the top element
pq.pop();
// Get the size of the priority queue
cout << "Size of the priority queue: " << pq.size() << endl; // 3
// Check if the priority queue is empty
if (pq.empty()) {
cout << "The priority queue is empty." << endl;
} else {
cout << "The priority queue is not empty." << endl; // Not empty
}
// Create a second priority queue
priority_queue pq2;
// Swap the content of the first priority queue with the second one
pq.swap(pq2);
cout << "After swapping, the first priority queue size: " << pq.size() << endl; // 0
cout << "After swapping, the second priority queue size: " << pq2.size() << endl; // 3
return 0;
}
Linked Lists:
A linked list stores a sequence of items in separate nodes. These nodes are linked using pointers.
It is one of the implementations of List ADT which supports
Inserting an element
Deleting an element
Accessing an element
Types of Linked Lists:
Singly Linked Lists
The single linked list is a sequence of elements in which every element has a link to its next element in the sequence.
Doubly Linked Lists
The double linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.
Circular Linked Lists
A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence, and the last element has a link to the first element.
Linked Lists vs Arrays
The size of the arrays is fixed, whereas linked lists can grow and shrink during execution.
The elements in arrays are stored consecutively, whereas in linked lists we store elements at random positions.
In arrays, we can access elements randomly, whereas in linked lists elements can be accessed sequentially.
Linked Lists in STL
Forward Lists
Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence.
Forward lists are implemented as singly linked lists. ##### Operations on Forward Lists
insert_after()
Inserts elements into container after the specified position.
my_forward_list.insert_after(itr, 10);
To insert a range of elements, we can pass iterators specifing range of elements.
my_forward_list.insert_after(itr, myarray.begin(), myarray.end());
erase_after()
Removes specified elements after the given position from the container.
my_forward_list.erase_after(itr);
To erase a range of elements from the container, we can pass iterators specifing the range of elements.
my_forward_list.erase_after(itr1, itr2);
front()
Returns reference to the first element in the container.
my_forward_list.front()
push_front()
Inserts a new element in the beginning of the forward_list.
my_forward_list.push_front(12)
pop_front()
Removes the first element in the forward list.
my_forward_list.pop_front() ##### Lists
Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence.
List containers are implemented using doubly-linked lists.
List container provides bi-directional iteration capability. ##### Operations on Lists
insert()
Inserts new elements before the element at the specified position.
my_list.insert(itr)
To insert range of elements, we can pass iterators specifing range of elements.
my_list.insert(itr, myarray.begin(), myarray.end())
erase()
Removes specified elements at the given position from the container.
my_list.erase(v.begin())
To erase range of elements from the container, we can pass iterators specifing the range of elements.
my_list.erase(itr1, itr2);
front()
Returns reference to the first element in the container.
my_list.front()
back()
Returns reference to the last element in the container.
my_list.back()
push_front()
Inserts a new element in the beginning of the list.
my_list.push_front(12)
push_back()
Inserts a new element at the end of the list.
my_list.push_back(12) #### Know more about Linked Lists