Time and Area Complexity Evaluation of Queue operations


What’s Queue?

Queue is a linear knowledge construction that follows FIFO method (First In First Out). One can think about a queue as a line of individuals ready in sequential order which begins from the start of the road. It’s an ordered record wherein insertions are accomplished at one finish which is named the rear and deletions are accomplished from the opposite finish generally known as the entrance. instance of a queue is any queue of shoppers for a useful resource the place the patron that got here first is served first. A queue could be applied utilizing Arrays or Linked Lists.

Complexity evaluation of various Queue operations:

1) enqueue(): 

This operation inserts a component in the back of the queue. It takes one parameter, the worth that’s to be inserted in the back of the queue.

Under is the implementation of enqueue() utilizing Array:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    void enqueue(int val)

    {

        if (entrance == -1) {

            entrance++;

        }

  

        if (rear == capability - 1) {

            cout << "Queue overflow!!!n";

            return;

        }

  

        queue[++rear] = val;

        cout << val << " inserted successfullyn";

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(1);

    q.enqueue(2);

  

    return 0;

}

Output

1 inserted efficiently
2 inserted efficiently

Complexity Evaluation:

  • Time Complexity: O(1), In enqueue operate a single component is inserted on the final place. This takes a single reminiscence allocation operation which is completed in fixed time.
  • Auxiliary Area: O(1). As no additional house is getting used.

Under is the implementation of enqueue() utilizing Linked Checklist :

C++

#embody <iostream>

utilizing namespace std;

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    void enqueue(int val)

    {

        

        if (rear == NULL) {

            

            rear = new node(val);

            rear->subsequent = NULL;

            rear->knowledge = val;

  

            

            

            entrance = rear;

        }

        else {

            

            node* temp = new node(val);

  

            

            rear->subsequent = temp;

  

            

            rear = temp;

        }

        cout << val << " inserted efficiently n";

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(1);

    q.enqueue(2);

  

    return 0;

}

Output

1 inserted efficiently 
2 inserted efficiently 

Complexity Evaluation:

  • Time Complexity: O(1). Solely a brand new node is created and the pointer of the final node is up to date. This consists of solely reminiscence allocation operations. Therefore it may be stated that insertion is completed in fixed time.
  • Auxiliary Area: O(1). No additional house is used.

2) dequeue(): 

This operation removes a component current on the entrance of the queue. Additionally, it ends in an error if the queue is empty.

Under is the implementation of dequeue() utilizing Array :

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    void enqueue(int val)

    {

        if (entrance == -1) {

            entrance++;

        }

  

        if (rear == capability - 1) {

            cout << "Queue overflow!!!n";

            return;

        }

  

        queue[++rear] = val;

    }

    void dequeue()

    {

        if (entrance == -1 || entrance > rear) {

            cout << "Queue is empty!!!n";

            return;

        }

  

        cout << "Component deleted from queue : " << queue[front++] << "n";

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(1);

    q.enqueue(2);

  

    

    

    q.dequeue();

  

    return 0;

}

Output

Component deleted from queue : 1

Complexity Evaluation:

  • Time Complexity: O(1). In array implementation, solely an arithmetic operation is carried out i.e., the entrance pointer is incremented by 1. It is a fixed time operate.
  • Auxiliary Area: O(1). No additional house is utilized for deleting a component from the queue.

Under is the implementation of dequeue utilizing Linked Checklist :

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    void enqueue(int val)

    {

        

        if (rear == NULL) {

            

            rear = new node(val);

            rear->subsequent = NULL;

            rear->knowledge = val;

  

            

            

            entrance = rear;

        }

        else {

            

            node* temp = new node(val);

  

            

            rear->subsequent = temp;

  

            

            rear = temp;

        }

    }

  

    void dequeue()

    {

        

        node* temp = entrance;

        

        if (entrance == NULL) {

            cout << "Underflow" << endl;

            return;

        }

        else if (temp->subsequent != NULL) {

            temp = temp->subsequent;

            cout << "Component deleted from queue is : " << front->knowledge << endl;

            free(entrance);

            entrance = temp;

        }

        

        else {

            cout << "Component deleted from queue is : " << front->knowledge << endl;

            free(entrance);

            entrance = NULL;

            rear = NULL;

        }

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(5);

    q.enqueue(7);

  

    

    

    q.dequeue();

  

    return 0;

}

Output

Component deleted from queue is : 5

Complexity Evaluation:

  • Time Complexity: O(1). In dequeue operation, solely the primary node is deleted and the entrance pointer is up to date. It is a fixed time operation.
  • Auxiliary Area: O(1). No additional house is utilized for deleting a component from the queue.

3) peek(): 

This operation prints the component current on the entrance of the queue.

Under is the implementation of peek() utilizing Array:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    void enqueue(int val)

    {

        if (entrance == -1) {

            entrance++;

        }

  

        if (rear == capability - 1) {

            cout << "Queue overflow!!!n";

            return;

        }

  

        queue[++rear] = val;

    }

  

    void peek()

    {

        if (entrance == -1 || entrance > rear) {

            cout << "Queue is empty !n";

            return;

        }

  

        cout << "Component on the entrance of queue: " << queue[front] << "n";

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(1);

    q.enqueue(2);

  

    

    

    q.peek();

  

    return 0;

}

Output

Component on the entrance of queue: 1

Complexity Evaluation:

  • Time Complexity: O(1). On this operation, solely a reminiscence handle is accessed. It is a fixed time operation.
  • Auxiliary Area: O(1). No additional house is utilized to entry the primary worth.

Under is the implementation of peek() utilizing Linked Checklist:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    void enqueue(int val)

    {

        

        if (rear == NULL) {

            

            rear = new node(val);

            rear->subsequent = NULL;

            rear->knowledge = val;

  

            

            

            entrance = rear;

        }

        else {

            

            node* temp = new node(val);

  

            

            rear->subsequent = temp;

  

            

            rear = temp;

        }

    }

  

    void peek()

    {

        

        if (entrance == NULL) {

            cout << "Queue is empty!!!" << endl;

        }

        else {

            

            cout << "Component current on the entrance of queue: " << front->knowledge << "n";

        }

    }

};

int most important()

{

    Queue q;

  

    

    

    q.enqueue(5);

    q.enqueue(7);

  

    

    

    q.peek();

  

    return 0;

}

Output

Component current on the entrance of queue: 5

Complexity Evaluation:

  • Time Complexity: O(1). In linked record implementation additionally a single reminiscence handle is accessed. It takes fixed time.
  • Auxiliary Area: O(1). No additional house is utilized to entry the primary component.

4) initialize(): 

This operation takes an array and provides the component in the back of the Queue.

Implementation of initialize() utilizing array:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    void enqueue(int val)

    {

        if (entrance == -1) {

            entrance++;

        }

  

        if (rear == capability - 1) {

            cout << "Queue overflow !n";

            return;

        }

  

        queue[++rear] = val;

    }

    void initialize(int arr[], int N)

    {

  

        for (int i = 0; i < N; i++) {

            

            int val = arr[i];

  

            

            enqueue(val);

        }

  

        

        for (int i = entrance; i <= rear; i++) {

            cout << queue[i] << " ";

        }

    }

};

  

int most important()

{

    Queue q;

  

    int arr[] = { 2, 4, 7, 9, 1 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    q.initialize(arr, N);

  

    return 0;

}

Complexity Evaluation:

  • Time Complexity: O(N). Inserting every component is a continuing time operation. So for inserting N components N unit of time is required.
  • Auxiliary Area: O(N). N components are inserted.

Implementation of initialize() utilizing LinkedList:

C++

#embody <iostream>

utilizing namespace std;

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    void enqueue(int val)

    {

        

        if (rear == NULL) {

            

            rear = new node(val);

            rear->subsequent = NULL;

            rear->knowledge = val;

  

            

            

            entrance = rear;

        }

        else {

            

            node* temp = new node(val);

  

            

            rear->subsequent = temp;

  

            

            rear = temp;

        }

    }

    void initialize(int arr[], int N)

    {

  

        for (int i = 0; i < N; i++) {

            

            int val = arr[i];

  

            

            enqueue(val);

        }

  

        node* temp = entrance;

        

        whereas (temp != NULL) {

            cout << temp->knowledge << " ";

            temp = temp->subsequent;

        }

    }

};

  

int most important()

{

    Queue q;

  

    int arr[] = { 2, 8, 7, 3, 1 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    q.initialize(arr, N);

  

    return 0;

}

Complexity Evaluation:

  • Time Complexity: O(N). Creating a brand new node and making a hyperlink takes unit time. So to insert N components (i.e., creating N nodes and linking them) N unit of instances is required.
  • Auxiliary Area: O(N). N components have to be inserted.

5) isfull(): 

Perform that returns true if the queue is crammed fully else returns false.

Under is the implementation of isfull() utilizing array:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    bool isfull()

    {

        if (rear == capability - 1)

            return 1;

  

        return 0;

    }

};

int most important()

{

    Queue q;

  

    if (q.isfull()) {

        cout << "Queue is filledn";

    }

    else {

        cout << "Queue is just not crammed completelyn";

    }

    return 0;

}

Output

Queue is just not crammed fully

Complexity Evaluation:

  • Time Complexity: O(1). It solely performs an arithmetic operation to verify if the queue is full or not.
  • Auxiliary Area: O(1). It requires no additional house.

Under is the implementation of isfull() utilizing Linked Checklist:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    bool isfull()

    {

        

        int size = 0;

  

        

        node* temp = entrance;

  

        

        if (temp == NULL)

            return 0;

  

        whereas (temp->subsequent != NULL) {

            size++;

            temp = temp->subsequent;

        }

  

        

        if (size == capability) {

            return 1;

        }

  

        return 0;

    }

};

int most important()

{

    Queue q;

  

    if (q.isfull()) {

        cout << "Queue is filledn";

    }

    else {

        cout << "Queue is just not crammed completelyn";

    }

  

    return 0;

}

Output

Queue is just not crammed fully

Complexity Evaluation:

  • Time Complexity: O(N). The entire linked record is traversed to calculate the size after which the size is checked with the capability. The traversal of the linked record takes O(N) time.
  • Auxiliary Area: O(1). No additional house is required.

6) isempty(): 

Perform that returns true if the queue is empty else returns false.

Under is the implementation of isempty() operation utilizing array:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class Queue {

public:

    int queue[capacity];

    int entrance;

    int rear;

  

    Queue()

    {

        entrance = -1;

        rear = -1;

    }

  

    bool isempty()

    {

        

        

        if (entrance == -1 || entrance > rear) {

            return 1;

        }

  

        return 0;

    }

};

int most important()

{

    Queue q;

  

    if (q.isempty()) {

        cout << "Queue is emptyn";

    }

    else {

        cout << "Queue is just not empty n";

    }

  

    return 0;

}

Complexity Evaluation:

  • Time Complexity: O(1) It solely checks the place saved within the first and final pointer
  • Auxiliary Area: O(1) NO additional house is required to verify the values of the primary and the final pointer.

Under is the implementation of isempty() operation utilizing LinkedList:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

    int knowledge;

    node* subsequent;

  

    node(int val)

    {

        knowledge = val;

        subsequent = NULL;

    }

};

class Queue {

public:

    node* entrance;

    node* rear;

  

    Queue()

    {

        entrance = rear = NULL;

    }

  

    bool isempty()

    {

        

        if (entrance == NULL) {

            return 1;

        }

  

        return 0;

    }

};

int most important()

{

    Queue q;

  

    if (q.isempty()) {

        cout << "Queue is filledn";

    }

    else {

        cout << "Queue is just not crammed completelyn";

    }

  

    return 0;

}

Complexity Evaluation:

  • Time Complexity: O(1), It checks if the pointer of first is Null or not. This operation takes fixed time.
  • Auxiliary Area: O(1). No additional house is required.

Leave a Reply

Your email address will not be published.