Introduction to Queue in Knowledge Constructions and Algorithms

August 7, 2022

1

What’s Queue?

A queue is a linear information construction that’s open at each ends and the operations are carried out in First In First Out (FIFO) order.

We outline a queue to be a listing during which all additions to the listing are made at one finish, and all deletions from the listing are made on the different finish. The component which is first pushed into the order, the operation is first carried out on that.

FIFO Precept of Queue:

A Queue is sort of a line ready to buy tickets, the place the primary individual in line is the primary individual served. (i.e. First come first serve).
Place of the entry in a queue able to be served, that’s, the primary entry that can be faraway from the queue, is named the entrance of the queue(typically, head of the queue), equally, the place of the final entry within the queue, that’s, the one most not too long ago added, is named the rear (or the tail) of the queue. See the beneath determine.

FIFO property of queue

Traits of Queue:

Queue can deal with a number of information.
We are able to entry each ends.
They’re quick and versatile.

Queue Illustration:

Array Illustration:

Like stacks, Queues can be represented in an array: On this illustration, the Queue is applied utilizing the array. Variables used on this case are

Queue: the identify of the array storing queue components.
Entrance: the index the place the primary component is saved within the array representing the queue.
Rear: the index the place the final component is saved in an array representing the queue.

Array illustration of queue:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

class Queue {

public:

int entrance, rear, measurement;

unsigned cap;

int* arr;

};

Queue* createQueue(unsigned cap)

{

Queue* queue = new Queue();

queue->cap = cap;

queue->entrance = queue->measurement = 0;

queue->rear = cap - 1;

queue->arr = new int[(queue->cap * sizeof(int))];

return queue;

}

Linked Listing Illustration:

A queue can be represented in Linked-lists, Pointers, and Constructions.

Linked-list illustration of Queue:

C++

struct QNode {

int information;

QNode* subsequent;

QNode(int d)

{

information = d;

subsequent = NULL;

}

};

struct Queue {

QNode *entrance, *rear;

Queue()

{

entrance = rear = NULL;

}

};

Varieties of Queue:

There are several types of queue:

Enter Restricted Queue

It is a easy queue. In such a queue, the enter could be taken from just one finish however deletion could be finished from any of the ends.

Output Restricted Queue

That is additionally a easy queue. In such a queue, the enter could be taken from each ends however deletion could be finished from just one finish.

Round Queue

It is a particular sort of queue the place the final place is related again to the primary place. Right here additionally the operations are carried out in FIFO order.

Double-Ended Queue (Deque)

In a double-ended queue the insertion and deletion operations, each could be carried out from each ends.

Precedence Queue

A precedence queue is a particular queue the place the weather are accessed based mostly on the precedence assigned to them.

To study extra about several types of queues, learn the article on “Varieties of Queues“.

Fundamental Operations of Queue:

There are few supporting operations (auxiliary operations):

entrance():

This operation returns the component on the entrance finish with out eradicating it.

C++

int entrance(Queue* queue)

{

if (isempty(queue))

return INT_MIN;

return queue->arr[queue->front];

}

rear():

This operation returns the component on the rear finish with out eradicating it.

C++

int rear(Queue* queue)

{

if (isempty(queue))

return INT_MIN;

return queue->arr[queue->rear];

}

isEmpty():

This operation returns a boolean worth that signifies whether or not the queue is empty or not.

C++

boolisEmpty()

{

if (entrance == -1)

return true;

else

return false;

}

isFull():

This operation returns a boolean worth that signifies whether or not the queue is full or not.

C++

boolisFull()

{

if (entrance == 0 && rear == MAX_SIZE - 1) {

return true;

}

return false;

}

Enqueue():

Provides (or shops) a component to the top of the queue.

The next steps ought to be taken to enqueue (insert) information right into a queue:

Step 1: Verify if the queue is full.
Step 2: If the queue is full, return overflow error and exit.
Step 3: If the queue shouldn’t be full, increment the rear pointer to level to the subsequent empty area.
Step 4: Add the information component to the queue location, the place the rear is pointing.
Step 5: return success.

Enqueue illustration

Implementation of Enqueue:

C++

void queueEnqueue(int information)

{

if (capability == rear) {

printf("nQueue is fulln");

return;

}

else {

queue[rear] = information;

rear++;

}

return;

}

Dequeue():

Removes (or entry) the primary component from the queue.

The next steps are taken to carry out the dequeue operation:

Step 1: Verify if the queue is empty.
Step 2: If the queue is empty, return the underflow error and exit.
Step 3: If the queue shouldn’t be empty, entry the information the place the entrance is pointing.
Step 4: Increment the entrance pointer to level to the subsequent accessible information component.
Step 5: The Return success.

Dequeue operation

Implementation of dequeue:

C++

void queueDequeue()

{

if (entrance == rear) {

printf("nQueue is emptyn");

return;

}

else {

for (int i = 0; i < rear - 1; i++) {

queue[i] = queue[i + 1];

}

rear--;

}

return;

}

Implementation of queue:

Beneath is an implementation of all of the operations utilized in a queue.

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

class Queue {

public:

int entrance, rear, measurement;

unsigned cap;

int* arr;

};

Queue* createQueue(unsigned cap)

{

Queue* queue = new Queue();

queue->cap = cap;

queue->entrance = queue->measurement = 0;

queue->rear = cap - 1;

queue->arr = new int[(queue->cap * sizeof(int))];

return queue;

}

int isFull(Queue* queue)

{

return (queue->measurement == queue->cap);

}

int isempty(Queue* queue) { return (queue->measurement == 0); }

void enqueue(Queue* queue, int merchandise)

{

if (isFull(queue))

return;

queue->rear = (queue->rear + 1) % queue->cap;

queue->arr[queue->rear] = merchandise;

queue->measurement = queue->measurement + 1;

cout << merchandise << " enqueued to queuen";

}

int dequeue(Queue* queue)

{

if (isempty(queue))

return INT_MIN;

int merchandise = queue->arr[queue->front];

queue->entrance = (queue->entrance + 1) % queue->cap;

queue->measurement = queue->measurement - 1;

return merchandise;

}

int entrance(Queue* queue)

{

if (isempty(queue))

return INT_MIN;

return queue->arr[queue->front];

}

int rear(Queue* queue)

{

if (isempty(queue))

return INT_MIN;

return queue->arr[queue->rear];

}

int most important()

{

Queue* queue = createQueue(1000);

enqueue(queue, 10);

enqueue(queue, 20);

enqueue(queue, 30);

enqueue(queue, 40);

cout << dequeue(queue);

cout << " dequeued from queuen";

cout << "Entrance merchandise is " << entrance(queue) << endl;

cout << "Rear merchandise is " << rear(queue);

return 0;

}

Output

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Entrance merchandise is 20
Rear merchandise is 40

Time complexity: All of the operations have O(1) time complexity.
Auxiliary House: O(N)

Functions of Queue:

Software of queue is frequent. In a pc system, there could also be queues of duties ready for the printer, for entry to disk storage, and even in a time-sharing system, to be used of the CPU. Inside a single program, there could also be a number of requests to be saved in a queue, or one activity might create different duties, which have to be finished in flip by maintaining them in a queue.

It has a single useful resource and a number of shoppers.
It synchronizes between gradual and quick units.
In a community, a queue is utilized in units resembling a router/change and mail queue.
Variations: dequeue, precedence queue and double-ended precedence queue.

FAQs (Incessantly requested questions):

1. What information construction can be utilized to implement a precedence queue?

Precedence queues could be applied utilizing a wide range of information constructions, together with linked lists, arrays, binary search timber, and heaps. Precedence queues are greatest applied utilizing the heap information construction.

2. Queues are used for what objective?

Along with making your information persistent, queues scale back errors that happen when totally different components of your system are down.

3. In information constructions, what’s a double-ended queue?

In a double-ended queue, components could be inserted and eliminated at each ends.

4. What is healthier, a stack or a queue?

If you would like issues to return out within the order you set them in, use a queue. Stacks are helpful once you wish to reorder issues after placing them in.

Associated articles:

Previous articleGoogle Pixel Fold Resurfaces In Leak Revealing A Body Mounted Digicam

Introduction to Queue in Knowledge Constructions and Algorithms

What’s Queue?

FIFO Precept of Queue:

Traits of Queue:

Queue Illustration:

Array Illustration:

C++

Linked Listing Illustration:

C++

Varieties of Queue:

Enter Restricted Queue

Output Restricted Queue

Round Queue

Double-Ended Queue (Deque)

Precedence Queue

Fundamental Operations of Queue:

entrance():

C++

rear():

C++

isEmpty():

C++

isFull():

C++

Enqueue():

C++

Dequeue():

C++

Implementation of queue:

C++

Functions of Queue:

FAQs (Incessantly requested questions):

1. What information construction can be utilized to implement a precedence queue?

2. Queues are used for what objective?

3. In information constructions, what’s a double-ended queue?

4. What is healthier, a stack or a queue?

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

ABOUT US

POPULAR POSTS

POPULAR CATEGORY