Time and House Complexity Evaluation of Queue operations

August 24, 2022

1

What’s Queue?

Queue is a linear information construction that follows FIFO strategy (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 through which insertions are finished at one finish which is called the rear and deletions are finished from the opposite finish often called the entrance. A superb instance of a queue is any queue of customers for a useful resource the place the buyer that got here first is served first. A queue could be carried out 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.

Beneath 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 essential()

{

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 factor is inserted on the final place. This takes a single reminiscence allocation operation which is completed in fixed time.
Auxiliary House: O(1). As no additional area is getting used.

Beneath is the implementation of enqueue() utilizing Linked Record :

C++

#embody <iostream>

utilizing namespace std;

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = 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->information = val;

entrance = rear;

}

else {

node* temp = new node(val);

rear->subsequent = temp;

rear = temp;

}

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

}

};

int essential()

{

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 contains solely reminiscence allocation operations. Therefore it may be stated that insertion is completed in fixed time.
Auxiliary House: O(1). No additional area is used.

2) dequeue():

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

Beneath 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 essential()

{

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. This can be a fixed time operate.
Auxiliary House: O(1). No additional area is utilized for deleting a component from the queue.

Beneath is the implementation of dequeue utilizing Linked Record :

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = 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->information = 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->information << endl;

free(entrance);

entrance = temp;

}

else {

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

free(entrance);

entrance = NULL;

rear = NULL;

}

};

int essential()

{

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. This can be a fixed time operation.
Auxiliary House: O(1). No additional area is utilized for deleting a component from the queue.

3) peek():

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

Beneath 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 essential()

{

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 tackle is accessed. This can be a fixed time operation.
Auxiliary House: O(1). No additional area is utilized to entry the primary worth.

Beneath is the implementation of peek() utilizing Linked Record:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = 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->information = 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->information << "n";

}

};

int essential()

{

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 tackle is accessed. It takes fixed time.
Auxiliary House: O(1). No additional area is utilized to entry the primary factor.

4) initialize():

This operation takes an array and provides the factor 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 essential()

{

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 factor is a continuing time operation. So for inserting N parts N unit of time is required.
Auxiliary House: O(N). N parts are inserted.

Implementation of initialize() utilizing LinkedList:

C++

#embody <iostream>

utilizing namespace std;

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = 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->information = 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->information << " ";

temp = temp->subsequent;

}

};

int essential()

{

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 parts (i.e., creating N nodes and linking them) N unit of instances is required.
Auxiliary House: O(N). N parts must be inserted.

5) isfull():

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

Beneath 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 essential()

{

Queue q;

if (q.isfull()) {

cout << "Queue is filledn";

}

else {

cout << "Queue will not be crammed completelyn";

}

return 0;

}

Output

Queue will not be crammed utterly

Complexity Evaluation:

Time Complexity: O(1). It solely performs an arithmetic operation to test if the queue is full or not.
Auxiliary House: O(1). It requires no additional area.

Beneath is the implementation of isfull() utilizing Linked Record:

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = 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 essential()

{

Queue q;

if (q.isfull()) {

cout << "Queue is filledn";

}

else {

cout << "Queue will not be crammed completelyn";

}

return 0;

}

Output

Queue will not be crammed utterly

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 House: O(1). No additional area is required.

6) isempty():

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

Beneath 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 essential()

{

Queue q;

if (q.isempty()) {

cout << "Queue is emptyn";

}

else {

cout << "Queue will not be empty n";

}

return 0;

}

Complexity Evaluation:

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

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

C++

#embody <iostream>

utilizing namespace std;

#outline capability 10

class node {

public:

int information;

node* subsequent;

node(int val)

{

information = val;

subsequent = NULL;

}

};

class Queue {

public:

node* entrance;

node* rear;

Queue()

{

entrance = rear = NULL;

}

bool isempty()

{

if (entrance == NULL) {

return 1;

}

return 0;

}

};

int essential()

{

Queue q;

if (q.isempty()) {

cout << "Queue is filledn";

}

else {

cout << "Queue will not be 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 House: O(1). No additional area is required.

Previous articleLook Up Your Personal Cellphone Quantity In Android and iOS

Time and House Complexity Evaluation of Queue operations

What’s Queue?

Complexity evaluation of various Queue operations:

1) enqueue():

C++

C++

2) dequeue():

C++

C++

3) peek():

C++

C++

4) initialize():

C++

C++

5) isfull():

C++

C++

6) isempty():

C++

C++

errors – What are the problems utilizing the Check Cookie Repair?

Perfecto now helps integration testing for Flutter

Find out how to power overwrite native adjustments with ‘git pull’

LEAVE A REPLY Cancel reply

Most Popular

Look Up Your Personal Cellphone Quantity In Android and iOS

Unit testing Flutter code with Mockito

errors – What are the problems utilizing the Check Cookie Repair?

New Fabs to be Collectively Owned

Recent Comments

ABOUT US

POPULAR POSTS

Look Up Your Personal Cellphone Quantity In Android and iOS

Unit testing Flutter code with Mockito

errors – What are the problems utilizing the Check Cookie Repair?

POPULAR CATEGORY