Queues using Array :
- FIFO : First in First Out
- Enqueue: Inserting an element in the queue, insertion is done from the rear end.
- Dequeue: Deleting an element (done from the front)
Queue can be implemented using an Array or a Linked List.
- Drawback w this method: Shifting of all the elements when one element is popped.
- We'll move the starting/front pointer instead of moving all the elements.
Using Struct :
// #include <bits/stdc++.h>
#include<iostream>
using namespace std;
struct Queue {
int size;
int front;
int rear;
int *Q;
};
void create(Queue *q, int size)
{
q->size = size;
q->front = -1;
q->rear = -1;
q->Q = (int *)malloc(size*sizeof(int));
}
void enqueue(Queue *q, int x)
{
if(q->rear == q->size-1)
cout << "Queue is Full\n";
else
{
q->rear++;
q->Q[q->rear] = x;
}
}
int dequeue(Queue *q)
{
int x = -1;
if(q->front == q->rear)
cout << "Queue is empty\n";
else
{
q->front++;
x = q->Q[q->front];
}
return x;
}
void Display(Queue q)
{
for(int i = q.front+1; i<=q.rear; i++)
cout << q.Q[i] << " ";
cout << endl;
}
int main()
{
struct Queue q;
create(&q, 10);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
Display(q);
cout << dequeue(&q) << endl;
cout << dequeue(&q) << endl;
return 0;
}
Using Class :
// #include <bits/stdc++.h>
#include<iostream>
using namespace std;
class Queue{
private:
int size;
int front;
int rear;
int *Q;
public:
// Default constructor
Queue(){front=rear=-1; size = 10; Q=new int[size];}
// Parameterized constructor
Queue(int size) {
size = size;
front = -1;
rear = -1;
Q = new int[size];
}
void enqueue(int x);
int dequeue();
void Display();
};
void Queue::enqueue(int x)
{
if(rear == size-1)
cout << "Queue is Full\n";
else
{
rear++;
Q[rear] = x;
}
}
int Queue::dequeue()
{
int x = -1;
if(front == rear)
cout << "Queue is empty\n";
else
{
front++;
x = Q[front];
}
return x;
}
void Queue::Display()
{
for(int i = front+1; i<=rear; i++)
cout << Q[i] << " ";
cout << endl;
}
int main()
{
Queue q(5);
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.Display();
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
return 0;
}
Drawback of Queue :
- Even though there is some space at the beginning, we will not be able to utilize it.
- Solution to this :
- Solution to this :
Resetting Pointers : Whenever front == rear reset the pointers. However, this doesn't guarantee the reuse of spaces.
Circular Queue :
Wherever the front is pointing, we'll keep that location empty.
// #include <bits/stdc++.h>
#include <iostream>
using namespace std;
struct Queue
{
int size;
int front;
int rear;
int *Q;
};
void create(Queue *q, int size)
{
q->size = size;
q->front = 0; // front and rear should not be at -1 but at 0 instead
q->rear = 0;
q->Q = (int *)malloc(size * sizeof(int));
}
void enqueue(Queue *q, int x)
{
if ((q->rear + 1) % (q->size) == q->front)
cout << "Queue is Full\n";
else
{
q->rear = (q->rear + 1) % (q->size);
q->Q[q->rear] = x;
}
}
int dequeue(Queue *q)
{
int x = -1;
if (q->front == q->rear)
cout << "Queue is empty\n";
else
{
q->front = (q->front + 1) % (q->size);
x = q->Q[q->front];
}
return x;
}
void Display(Queue q)
{
int i = q.front + 1;
do
{
cout << q.Q[i];
i = (i + 1) % q.size;
} while (i != (q.rear + 1) % (q.size));
cout << endl;
}
int main()
{
struct Queue q;
create(&q, 10);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
Display(q);
cout << dequeue(&q) << endl;
cout << dequeue(&q) << endl;
return 0;
}
Queue using Linked List :
- here we are using two pointers front and rear, rear pointer helps us in adding another node in constant time complexity
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
} *front = NULL, *rear = NULL;
void enqueue(int x)
{
struct Node *t;
t = (struct Node *)malloc(sizeof(struct Node));
if (t == NULL)
cout << "Queue is FULL\n";
else
{
t->data = x;
t->next = NULL;
if (front == NULL)
front = rear = t;
else
{
rear->next = t;
rear = t;
}
}
}
int dequeue()
{
int x = -1;
struct Node *t;
if (front == NULL)
cout << "Queue is EMPTY !";
else
{
x = front->data;
t = front;
front = front->next;
free(t);
}
return x;
}
void Display()
{
struct Node *p = front;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
Display();
cout << dequeue() << endl;
return 0;
}
Using Class :
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class Queue
{
private:
Node *front;
Node *rear;
public:
Queue();
~Queue();
void enqueue(int x);
int dequeue();
bool isEmpty();
void display();
};
Queue::Queue()
{
front = nullptr;
rear = nullptr;
}
void Queue::enqueue(int x)
{
Node *t = new Node;
if (t == nullptr)
{
cout << "Queue Overflow" << endl;
}
else
{
t->data = x;
t->next = nullptr;
if (front == nullptr)
{
front = t;
rear = t;
}
else
{
rear->next = t;
rear = t;
}
}
}
int Queue::dequeue()
{
int x = -1;
Node *p;
if (isEmpty())
{
cout << "Queue Underflow" << endl;
}
else
{
p = front;
front = front->next;
x = p->data;
delete p;
}
return x;
}
bool Queue::isEmpty()
{
if (front == nullptr)
{
return true;
}
return false;
}
Queue::~Queue()
{
Node *p = front;
while (front)
{
front = front->next;
delete p;
p = front;
}
}
void Queue::display()
{
Node *p = front;
while (p)
{
cout << p->data << flush;
p = p->next;
if (p != nullptr)
{
cout << " <- " << flush;
}
}
cout << endl;
}
int main()
{
int A[] = {1, 3, 5, 7, 9};
Queue q;
for (int i = 0; i < sizeof(A) / sizeof(A[0]); i++)
{
q.enqueue(A[i]);
}
q.display();
for (int i = 0; i < sizeof(A) / sizeof(A[0]); i++)
{
q.dequeue();
}
q.dequeue();
return 0;
}
Interactive Graph