Name - Rahul Dhandore

Branch - DSAI
Roll No. - 231020438

STACK:

#include<iostream>
using namespace std;

int top=-1;

void push(int stack[],int s,int n){

if(top==s-1){
cout<<"The stack is full"<<endl;
}

else{
top++;
stack[top]=n;
cout<<"Element inserted"<<endl;
}
}

void pop(int stack[],int s){

 if(top==-1){
cout<<"The stack is empty"<<endl;
}
else{
cout<<"Popped element is "<<stack[top]<<endl;
top--;
}
}

void display(int stack[],int s){

if(top==-1){
cout<<"Stack is empty"<<endl;
}

else{
for(int i=0;i<=top;i++){
cout<<stack[i]<<' ';
}
cout<<endl;
}
}

int main(){

int s;
cout<<"Enter the size of stack: ";
cin>>s;
int stack[s];

char ans='y';
while(ans=='y'){

int choice;
cout<<"Enter your choice (1,2,3) ";
cin>>choice;
switch(choice){

case 1:
int x;
cout<<"Enter the number to be pushed: ";
cin>>x;
push(stack,s,x);
break;

case 2:
pop(stack,s);
break;

case 3:
display(stack,s);
break;
}
 cout<<"Want to perform more operations ? ";
cin>>ans;
}

QUEUE

Queue Implementation:

#include<iostream>
using namespace std;

int rear=0,front=-1;

void push(int q[],int s,int n){

int *ptr=q;

if(front==s-1){
cout<<"The Queue is full"<<endl;
}

else{
front++;
*(q+front)=n;
 cout<<"Element Inserted"<<endl;
}

void pop(int q[],int s){

int *ptr=q;

if(front<rear){
cout<<"The Queue is empty"<<endl;
}

else{
cout<<"The popped element is "<<*(q+rear)<<endl;
rear++;
}
}

void display(int q[],int s){

int *ptr=q;

if(front<rear){
cout<<"The Queue is empty"<<endl;
}

else{
for(int i=rear;i<=front;i++){
 cout<<*(q+i)<<' ';
}
cout<<endl;
}
}

int main(){
int s;
cin>>s;
int queue[s];

char ans='y';
while(ans=='y'){

int choice;
cout<<"Enter your choice (1,2,3) ";
cin>>choice;

switch(choice){

case 1:
int x;
cout<<"Enter number to be pushed: ";
cin>>x;
push(queue,s,x);
break;
 case 2:
pop(queue,s);
break;

case 3:
display(queue,s);
break;
}

cout<<"Want to perform more operations ? ";

cin>>ans;
}
}

Circular Queue:

// Circular Queue implementation in C++

#include <iostream>
#define SIZE 5 /* Size of Circular Queue */

using namespace std;

class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
// Check if the queue is full
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == (rear + 1) % SIZE) {
return true;
}
return false;
}

// Check if the queue is empty

bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full" << endl;
 } else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element,
// so we reset the queue after deleting it.
else {
front = (front + 1) % SIZE;
}
return (element);
}
 }

void display() {
// Function to display status of Circular Queue
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << "Front -> " << front;
cout << endl
<< "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)
cout << items[i] << "\t";
cout << items[i];
cout << endl
<< "Rear -> " << rear << endl;
}
}
};

int main() {
Queue q;

// Fails because front = -1

q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);

// Fails to enqueue because front == 0 && rear == SIZE - 1

q.enQueue(6);

q.display();

int elem = q.deQueue();

if (elem != -1)
cout << endl
<< "Deleted Element is " << elem << endl;

q.display();

q.enQueue(7);

q.display();

// Fails to enqueue because front == rear + 1

q.enQueue(8);

return 0;
}

Deque:

#include<iostream>
using namespace std;
#define SIZE 10

class dequeue {
int a[SIZE], f, r; // SIZE instead of 20
public:
dequeue();
void insert_at_beg(int);
void insert_at_end(int);
void delete_fr_front();
void delete_fr_rear();
void show();
};

dequeue::dequeue() {
f = -1;
r = -1;
}

void dequeue::insert_at_end(int i) {
if (r >= SIZE - 1) {
cout << "\n Insertion is not possible, overflow!!!!";
 } else {
if (f == -1) {
f = 0;
r = 0;
} else {
r = r + 1;
}
a[r] = i;
cout << "\nInserted item is: " << a[r];
}
}

void dequeue::insert_at_beg(int i) {
if (f == -1) {
f = 0;
r = 0;
a[f] = i;
cout << "\nInserted element is: " << i;
} else if (f != 0) {
a[--f] = i;
cout << "\nInserted element is: " << i;
} else {
cout << "\nInsertion is not possible, overflow!!!";
}
}

void dequeue::delete_fr_front() {
 if (f == -1) {
cout << "Deletion is not possible::dequeue is empty";
} else {
cout << "The deleted element is: " << a[f];
if (f == r) {
f = r = -1; // Reset to empty
} else {
f = f + 1;
}
}
}

void dequeue::delete_fr_rear() {
if (f == -1) {
cout << "Deletion is not possible::dequeue is empty";
} else {
cout << "The deleted element is: " << a[r];
if (f == r) {
f = r = -1;
} else {
r = r - 1;
}
}
}

void dequeue::show() {
if (f == -1) {
 cout << "Dequeue is empty";
} else {
for (int i = f; i <= r; i++) {
cout << a[i] << " ";
}
}
}

int main() {
int c, i;
dequeue d;
do { // Corrected loop syntax
cout << "\n 1. Insert at beginning";
cout << "\n 2. Insert at end";
cout << "\n 3. Show";
cout << "\n 4. Deletion from front";
cout << "\n 5. Deletion from rear";
cout << "\n 6. Exit";
cout << "\n Enter your choice: ";
cin >> c;

switch (c) {
case 1:
cout << "Enter the element to be inserted: ";
cin >> i;
d.insert_at_beg(i);
break;
 case 2:
cout << "Enter the element to be inserted: ";
cin >> i;
d.insert_at_end(i);
break;
case 3:
d.show();
break;
case 4:
d.delete_fr_front();
break;
case 5:
d.delete_fr_rear();
break;
case 6:
exit(0); // Changed to proper exit
default:
cout << "Invalid choice";
break;
}
} while (c != 6); // Exit on case 6
return 0;
}

LINKED LIST
Implementation:
#include <iostream>
using namespace std;

// Node structure for a singly linked list

struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

// Linked List class

class LinkedList {
private:
Node* head;

public:
// Constructor
LinkedList() : head(nullptr) {}

// Append a node to the end

void append(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
 while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}

// Prepend a node at the beginning

void prepend(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}

// Insert a node at the nth position (0-based index)

void insertAt(int index, int value) {
if (index < 0) {
cout << "Invalid index!" << endl;
return;
}

Node* newNode = new Node(value);

// If index is 0, insert at head

if (index == 0) {
newNode->next = head;
head = newNode;
 return;
}

Node* temp = head;

for (int i = 0; i < index - 1 && temp != nullptr; ++i) {
temp = temp->next;
}

if (temp == nullptr) {
cout << "Index out of bounds!" << endl;
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}

// Display the linked list

void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "nullptr" << endl;
}

// Destructor to free up memory

 ~LinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
};

int main() {
LinkedList list;

list.append(10); // 10
list.append(20); // 10 -> 20
list.prepend(5); // 5 -> 10 -> 20
list.insertAt(1, 15); // 5 -> 15 -> 10 -> 20
list.insertAt(0, 1); // 1 -> 5 -> 15 -> 10 -> 20
list.insertAt(4, 25); // 1 -> 5 -> 15 -> 10 -> 25 -> 20

cout << "Linked List: ";

list.display(); // Output the list

return 0;
}

Circular Singly Linked List:

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int val) {
data = val;
next = nullptr;
}
};

class CircularLinkedList {
public:
Node* head;

// Constructor to initialize an empty linked list

CircularLinkedList() {
head = nullptr;
}

// Append a node to the end of the circular linked list

void append(int data) {
Node* newNode = new Node(data);
 if (head == nullptr) {
head = newNode;
newNode->next = head; // Pointing to itself
return;
}

Node* temp = head;

while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head; // Completing the circular connection
}

// Prepend a node to the beginning of the circular linked list

void prepend(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
newNode->next = head; // Pointing to itself
return;
}

Node* temp = head;

while (temp->next != head) {
temp = temp->next;
}
 temp->next = newNode; // Set the last node's next to the new node
newNode->next = head; // New node's next is the current head
head = newNode; // Update head to the new node
}

// Insert a node at the nth position (1-based index)

void insertAtNth(int data, int position) {
if (position < 1) {
cout << "Position should be >= 1" << endl;
return;
}

Node* newNode = new Node(data);

if (position == 1) {
prepend(data);
return;
}

Node* temp = head;

for (int i = 1; temp->next != head && i < position - 1; i++) {
temp = temp->next;
}

if (temp->next == head) {
append(data); // If position is beyond the length, append
return;
 }

newNode->next = temp->next;
temp->next = newNode;
}

// Delete the nth node (1-based index)

void deleteNth(int position) {
if (head == nullptr || position < 1) {
cout << "Invalid position or list is empty." << endl;
return;
}

Node* temp = head;

// Deleting the head node

if (position == 1) {
if (head->next == head) { // If there's only one node
delete head;
head = nullptr;
return;
}

Node* last = head;

while (last->next != head) { // Find the last node
last = last->next;
}
 last->next = head->next;
temp = head;
head = head->next;
delete temp;
return;
}

Node* prev = nullptr;

for (int i = 1; temp->next != head && i < position; i++) {
prev = temp;
temp = temp->next;
}

if (temp->next == head && position > 1) {

cout << "Position is beyond the list length." << endl;
return;
}

prev->next = temp->next;
delete temp;
}

// Print the circular linked list

void printList() {
if (head == nullptr) {
cout << "List is empty." << endl;
 return;
}

Node* temp = head;

do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(head)" << endl;
}
};

int main() {
CircularLinkedList list;

// Testing the circular linked list

list.append(10);
list.append(20);
list.append(30);
cout << "After appending: ";
list.printList();

list.prepend(5);
cout << "After prepending: ";
list.printList();

list.insertAtNth(15, 3);
 cout << "After inserting at 3rd position: ";
list.printList();

list.deleteNth(4);
cout << "After deleting 4th node: ";
list.printList();

return 0;
}

Doubly Linked List:

#include <iostream>

class Node {
public:
int data;
Node* next;
Node* prev;

Node(int value) : data(value), next(nullptr), prev(nullptr) {}

};

class DoublyLinkedList {
private:
Node* head;
 Node* tail;

public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}

// Insert at the beginning

void insertAtHead(int value) {
Node* newNode = new Node(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}

// Insert at the end

void insertAtTail(int value) {
Node* newNode = new Node(value);
if (!tail) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}

// Delete a node by value

void deleteNode(int value) {
Node* current = head;
while (current && current->data != value) {
current = current->next;
}

if (!current) return; // Value not found

if (current == head) head = head->next;

if (current == tail) tail = tail->prev;
if (current->prev) current->prev->next = current->next;
if (current->next) current->next->prev = current->prev;

delete current;
}

// Display list forward

void displayForward() const {
Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << "\n";
 }

// Display list backward

void displayBackward() const {
Node* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << "\n";
}

// Destructor to free memory

~DoublyLinkedList() {
Node* current = head;
while (current) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
};

int main() {
DoublyLinkedList dll;
dll.insertAtHead(1);
dll.insertAtHead(2);
 dll.insertAtTail(3);
dll.insertAtTail(4);

std::cout << "Forward: ";

dll.displayForward();

std::cout << "Backward: ";

dll.displayBackward();

dll.deleteNode(2);
std::cout << "After deletion (forward): ";
dll.displayForward();

return 0;
}