# 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 ` `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 ` `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 ` `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 ` `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 ` `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 ` `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 ` `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);` ` `  `    ` `    ``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 ` `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);` ` `  `    ` `    ``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 ` `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 ` `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 ` `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 ` `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.