Queue is an Abstract Data Type (ADT), which has its own values called front and rear, and operation on those values called enqueue and dequeue.
Queue is an Abstract Data Type (ADT), which follows the principle of FIFO (First In First Out).
Operations on Queue
- Enqueue – Insert element from the end of the queue.
- Dequeue – Remove the element from the front of the queue.
- Peek – Return the front element of the queue.
- Isfull – Return true if the queue is full, else return false.
- Isempty – Return true if the queue is empty, else return false.
Implementation of Queue
We can implement queue using the following ways:-
- Array
- Linked
Implementation of Queue using Array
// implementation of queue using array
#include <iostream>
#define MAX_SIZE 5
using namespace std;
struct Queue {
int data[MAX_SIZE];
int front=-1,rear=-1;
};
struct Queue q1;
bool isEmpty() {
if(q1.front == -1) {
return true;
}
return false;
}
bool isFull() {
if(q1.front == 0 && q1.rear == MAX_SIZE-1) {
return true;
}
return false;
}
void enQueue(int val) {
if(isFull()) {
cout << "Queue is full, can't insert" << endl;
} else {
if(q1.front == -1) {
q1.front=0;
}
q1.rear++;
q1.data[q1.rear] = val;
}
}
int deQueue() {
if(isEmpty() ) {
cout << "Queue is empty, can't remove" << endl;
return 0;
} else {
int n = q1.data[q1.front];
if(q1.front >= q1.rear) {
q1.rear = q1.front=-1;
} else {
q1.front++;
}
return n;
}
}
int peek() {
if(isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
} else {
int n = q1.data[q1.front];
return n;
}
}
void display() {
if(isEmpty()) {
cout << "Queue is empty" << endl;
} else {
for(int i=q1.front; i<=q1.rear; i++) {
cout << q1.data[i] << endl;
}
}
}
int main(int argc, char const *argv[])
{
enQueue(4); // [4]
enQueue(3); // [4,3]
enQueue(5); // [4,3,5]
enQueue(9); // [4,3,5,9]
enQueue(9); // [4,3,5,9,9]
enQueue(9); // queue is full
// [4,3,5,9,9]
cout << deQueue() << endl; // return 4
// [3,5,9,9]
cout << deQueue() << endl; // return 3
// [5,9,9]
cout << deQueue() << endl; // return 9
cout << deQueue() << endl; // return 9
cout << peek() << endl;
cout << "Display : \n";
display();
return 0;
}
// Output
// Queue is full, can't insert
// 4
// 3
// 5
// 9
// 9
// Display :
// 9
// adding soon
// adding soon
// adding soon
Implementation of Queue using Linked List
// implemenetation of queue using linked list
#include <iostream>
using namespace std;
// queue node
struct Queue {
int data;
struct Queue *next = NULL;
};
// front, rear are pointer
struct Queue *front = NULL, *rear = NULL;
void enQueue(int val) {
struct Queue *newNode = new Queue();
newNode->data = val;
if(front == NULL) {
rear = front=newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
void deQueue() {
if(front == NULL) {
return;
} else {
struct Queue *t = front;
front = front->next;
delete(t);
}
}
// traverse all nodes and display its data
void display() {
Queue *t = front;
while (t != NULL) {
cout << t->data << "->";
t=t->next;
}
cout << "NULL\n";
}
// return front of the element without removing it
int peek() {
// if front is null mean node is not inserted so we return -1 and print NULL
if(front == NULL) {
cout << "NULL\n";
return -1;
}
int n = front->data;
return n;
}
int main(int argc, char const *argv[])
{
display(); // NULL
enQueue(4); // 4
enQueue(6); // 4 6
enQueue(8); // 4 6 8
enQueue(10); // 4 6 8 10
display(); // 4 6 8 10
deQueue(); // remove 4
display(); // 6 8 10
return 0;
}
// NULL
// 4->6->8->10->NULL
// 6->8->10->NULL// adding soon
// adding soon
// adding soon
Applications of Queue
- CPU Scheduling
- Disk Scheduling
- Job Sequencing
- Breadth First Search(BFS)
Frequently Asked Questions (FAQ)
What is Queue? Linked list implementation of queue. Array implementation of queue. Application of queue data structure?