Pr12

 A double-ended queue (deque) is a linear list in which additions and deletions may be made at

either end. Obtain a data representation mapping a deque into a one-dimensional array. Write C++

program to simulate deque with functions to add and delete elements from either end of the deque.

Objectives:-

1. To understand concept of double ended queue.

2. To study the different types of double ended queues.




#include <iostream>

using namespace std;


class Deque {

private:

    int* arr;       // Array to store deque elements

    int front;      // Front pointer

    int rear;       // Rear pointer

    int capacity;   // Maximum size of deque

    int size;       // Current size of deque


public:

    // Constructor to initialize deque with a given capacity

    Deque(int cap) {

        capacity = cap;

        arr = new int[capacity];

        front = -1;

        rear = -1;

        size = 0;

    }


    // Function to check if deque is full

    bool isFull() {

        return size == capacity;

    }


    // Function to check if deque is empty

    bool isEmpty() {

        return size == 0;

    }


    // Function to add an element at the front of deque

    void addFront(int val) {

        if (isFull()) {

            cout << "Deque is full. Cannot add element." << endl;

            return;

        }

        if (front == -1) {  // Deque is empty

            front = rear = 0;

        } else {

            front = (front - 1 + capacity) % capacity;

        }

        arr[front] = val;

        size++;

    }


    // Function to add an element at the rear of deque

    void addRear(int val) {

        if (isFull()) {

            cout << "Deque is full. Cannot add element." << endl;

            return;

        }

        if (front == -1) {  // Deque is empty

            front = rear = 0;

        } else {

            rear = (rear + 1) % capacity;

        }

        arr[rear] = val;

        size++;

    }


    // Function to delete an element from the front of deque

    void deleteFront() {

        if (isEmpty()) {

            cout << "Deque is empty. Cannot delete element." << endl;

            return;

        }

        if (front == rear) {  // Only one element in deque

            front = rear = -1;

        } else {

            front = (front + 1) % capacity;

        }

        size--;

    }


    // Function to delete an element from the rear of deque

    void deleteRear() {

        if (isEmpty()) {

            cout << "Deque is empty. Cannot delete element." << endl;

            return;

        }

        if (front == rear) {  // Only one element in deque

            front = rear = -1;

        } else {

            rear = (rear - 1 + capacity) % capacity;

        }

        size--;

    }


    // Function to display elements of deque

    void display() {

        if (isEmpty()) {

            cout << "Deque is empty." << endl;

            return;

        }


        cout << "Elements in Deque: ";

        int i = front;

        while (i != rear) {

            cout << arr[i] << " ";

            i = (i + 1) % capacity;

        }

        cout << arr[rear] << endl;

    }


    // Destructor to free dynamically allocated memory

    ~Deque() {

        delete[] arr;

    }

};


int main() {

    // Initialize a deque with a capacity of 5

    Deque dq(5);


    // Add elements to the rear and front

    dq.addRear(10);

    dq.addRear(20);

    dq.addFront(5);

    dq.addFront(3);


    // Display the deque

    dq.display();  // Expected output: 3 5 10 20


    // Delete elements from the front and rear

    dq.deleteFront();

    dq.deleteRear();


    // Display the deque after deletions

    dq.display();  // Expected output: 5 10


    // Try adding more elements

    dq.addRear(30);

    dq.addFront(1);


    // Display the final state of the deque

    dq.display();  // Expected output: 1 5 10 30


    return 0;

}



// Explanation:

// Deque Class:


// Data Members:

// arr[]: A dynamically allocated array to store deque elements.

// front and rear: Pointers to the front and rear elements of the deque, respectively.

// capacity: The maximum capacity of the deque.

// size: The current number of elements in the deque.

// Functions:


// addFront(): Adds an element at the front of the deque by adjusting the front pointer. If the deque is full, it prints an error message.

// addRear(): Adds an element at the rear of the deque by adjusting the rear pointer. If the deque is full, it prints an error message.

// deleteFront(): Removes an element from the front of the deque by adjusting the front pointer. If the deque is empty, it prints an error message.

// deleteRear(): Removes an element from the rear of the deque by adjusting the rear pointer. If the deque is empty, it prints an error message.

// display(): Prints all the elements in the deque from front to rear.

// Circular Array:


// The array is treated as circular, meaning when the pointers reach the end of the array, they wrap around to the beginning using the modulo operator %.

// This allows the deque to efficiently utilize the available space in the array.

// Main Function:


// The main function demonstrates how to use the deque by adding and deleting elements from both ends and displaying the deque's content.

Comments

Post a Comment

Popular posts from this blog

Pr13

 Pizza parlor accepting maximum M orders. Orders are served in first come first served basis. Order once placed cannot be cancelled. Write C++ program to simulate the system using circular queue using array. Objectives:- 1. To understand concept of circular queue. #include <iostream> #include <string> using namespace std; class PizzaParlor { private:     string* orders;    // Array to store pizza orders     int front;         // Front pointer (for serving orders)     int rear;          // Rear pointer (for placing orders)     int capacity;      // Maximum capacity (M orders)     int size;          // Current number of orders public:     // Constructor to initialize the queue with a given capacity     PizzaParlor(int M) {         capacity = M;         orders = new ...
Read more

pr7

 Department of Computer Engineering has student's club named 'Pinnacle Club'. Students of Second, third and final year of department can be granted membership on request. Similarly one may cancel the membership of club. First node is reserved for president of club and last node is reserved for secretary of club. Write C++ program to maintain club member‘s information using singly linked list. Store student PRN and Name. Write functions to a) Add and delete the members as well as president or even secretary. b) Compute total number of members of club c) Display members d) Display list in reverse order using recursion e) Two linked lists exists for two divisions. Concatenate two lists #include <iostream> #include <string> using namespace std; // Define a structure for a student node struct Student {     string prn;     string name;     Student* next; }; // Define a class for managing the club's members class PinnacleClub { private:   ...
Read more