Last Updated on December 14, 2022 by Prepbytes
Queue
A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.
The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
Basic Operations of Queue:
- Enqueue: This operation is used to Insert an element at the rear end of the queue.
- Dequeue: This operation is used to remove and return an element from the front end of the queue.
- isEmpty(): This operation
- is used to check whether the queue is empty or not. It returns bool value, if the queue is empty then this operation will return true else false.
- isFull(): This operation is used to check whether the queue is full or not. It return true is the queue is full, else it will return false.l
- Peek(): This operation is used to get the value of the element from the front of the queue.
Working of queue:
- We can implement queue by using two pointers i.e. FRONT and REAR.
- FRONT is used to track the first element of the queue.
- REAR is used to track the last element of the queue.
- Initially, we’ll set the values of FRONT and REAR to -1.
Dry Run
Array representation of queue which contains 5 elements along with the respective values of front and rear:
The above figure shows the queue of numbers. Since, we didn’t perform any deletion in the queue. Therefore, the value of front will remain -1. However the value of rear increases by 1 every time whenever the insertion operation is performed in the queue.
#include <bits/stdc++.h>
using namespace std;
struct Queue {
int front, rear, capacity;
int* queue;
Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int;
}
~Queue() { delete[] queue; }
void queueEnqueue(int data)
{
if (capacity == rear) {
printf("\nQueue is full\n");
return;
}
else {
queue[rear] = data;
rear++;
}
return;
}
void queueDequeue()
{
if (front == rear) {
printf("\nQueue is empty\n");
return;
}
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
rear--;
}
return;
}
void queueDisplay()
{
int i;
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
for (i = front; i < rear; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
void queueFront()
{
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[front]);
return;
}
};
int main(void)
{
Queue q(4);
q.queueDisplay();
q.queueEnqueue(200);
q.queueEnqueue(300);
q.queueEnqueue(400);
q.queueEnqueue(500);
q.queueDisplay();
q.queueEnqueue(600);
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
printf("\n\nafter two node deletion\n\n");
q.queueDisplay();
q.queueFront();
return 0;
}
class Queue {
private int front, rear, capacity;
private int queue[];
Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int[capacity];
}
static void queueEnqueue(int data)
{
if (capacity == rear) {
System.out.printf("\nQueue is full\n");
return;
}
else {
queue[rear] = data;
rear++;
}
return;
}
static void queueDequeue()
{
// if queue is empty
if (front == rear) {
System.out.printf("\nQueue is empty\n");
return;
}
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
if (rear < capacity)
queue[rear] = 0;
rear--;
}
return;
}
static void queueDisplay()
{
int i;
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}
for (i = front; i < rear; i++) {
System.out.printf(" %d <-- ", queue[i]);
}
return;
}
static void queueFront()
{
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}
System.out.printf("\nFront Element is: %d", queue[front]);
return;
}
}
class StaticQueueinjava {
public static void main(String[] args)
{
Queue q = new Queue(4);
q.queueDisplay();
q.queueEnqueue(200);
q.queueEnqueue(300);
q.queueEnqueue(400);
q.queueEnqueue(500);
q.queueDisplay();
q.queueEnqueue(600);
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
System.out.printf("\n\nafter two node deletion\n\n");
q.queueDisplay();
q.queueFront();
}
}
class Queue:
def __init__(self, c):
self.queue = []
self.front = self.rear = 0
self.capacity = c
def queueEnqueue(self, data):
if(self.capacity == self.rear):
print("\nQueue is full")
else:
self.queue.append(data)
self.rear += 1
def queueDequeue(self):
if(self.front == self.rear):
print("Queue is empty")
else:
x = self.queue.pop(0)
self.rear -= 1
def queueDisplay(self):
if(self.front == self.rear):
print("\nQueue is Empty")
for i in self.queue:
print(i, "<--", end = '')
def queueFront(self):
if(self.front == self.rear):
print("\nQueue is Empty")
print("\nFront Element is:",
self.queue[self.front])
if __name__=='__main__':
q = Queue(4)
q.queueDisplay()
q.queueEnqueue(200)
q.queueEnqueue(300)
q.queueEnqueue(400)
q.queueEnqueue(500)
q.queueDisplay()
q.queueEnqueue(600)
q.queueDisplay()
q.queueDequeue()
q.queueDequeue()
print("\n\nafter two node deletion\n")
q.queueDisplay()
q.queueFront()
This article tried to discuss Array implementation of queue simple Hope this blog helps you understand and solve the problem. To practice more problems you can MYCODE | Competitive Programming at Prepbytes.