Implementation of Queue Data Structure
Queue can be implemented using following data structures:
We have discussed the implementation of Queue below:
// Implementation of queue(enqueue, dequeue).
#include <bits/stdc++.h>
using namespace std;
class Queue {
public:
int front, rear, size;
unsigned cap;
int* arr;
};
Queue* createQueue(unsigned cap)
{
Queue* queue = new Queue();
queue->cap = cap;
queue->front = queue->size = 0;
queue->rear = cap - 1;
queue->arr = new int[(queue->cap * sizeof(int))];
return queue;
}
int isFull(Queue* queue)
{
return (queue->size == queue->cap);
}
int isempty(Queue* queue) { return (queue->size == 0); }
// Function to add an item to the queue.
// It changes rear and size.
void enqueue(Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->cap;
queue->arr[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(Queue* queue)
{
if (isempty(queue))
return INT_MIN;
int item = queue->arr[queue->front];
queue->front = (queue->front + 1) % queue->cap;
queue->size = queue->size - 1;
return item;
}
int front(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];
}
// Driver code
int main()
{
Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
cout << dequeue(queue);
cout << " dequeued from queue\n";
cout << "Front item is " << front(queue) << endl;
cout << "Rear item is " << rear(queue);
return 0;
}
// C program for array implementation of queue
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a queue
struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
};
// function to create a queue
// of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue
= (struct Queue*)malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array
= (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
// Queue is full when size becomes
// equal to the capacity
int isFull(struct Queue* queue)
{
return (queue->size == queue->capacity);
}
// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{
return (queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d enqueued to queue\n", item);
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
// Driver program to test above functions./
int main()
{
struct Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
printf("%d dequeued from queue\n", dequeue(queue));
printf("Front item is %d\n", front(queue));
printf("Rear item is %d\n", rear(queue));
return 0;
}
// This code is contributed by Susobhan Akhuli
// Java program for array
// implementation of queue
// A class to represent a queue
class Queue {
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity)
{
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
// Queue is full when size becomes
// equal to the capacity
boolean isFull(Queue queue)
{
return (queue.size == queue.capacity);
}
// Queue is empty when size is 0
boolean isEmpty(Queue queue)
{
return (queue.size == 0);
}
// Method to add an item to the queue.
// It changes rear and size
void enqueue(int item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}
// Method to remove an item from queue.
// It changes front and size
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
return item;
}
// Method to get front of queue
int front()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.front];
}
// Method to get rear of queue
int rear()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.rear];
}
}
// Driver class
public class Test {
public static void main(String[] args)
{
Queue queue = new Queue(1000);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
System.out.println(queue.dequeue()
+ " dequeued from queue");
System.out.println("Front item is "
+ queue.front());
System.out.println("Rear item is " + queue.rear());
}
}
// This code is contributed by Susobhan Akhuli
# Python3 program for array implementation of queue
# Class Queue to represent a queue
class Queue:
# __init__ function
def __init__(self, capacity):
self.front = self.size = 0
self.rear = capacity - 1
self.Q = [None]*capacity
self.capacity = capacity
# Queue is full when size becomes
# equal to the capacity
def isFull(self):
return self.size == self.capacity
# Queue is empty when size is 0
def isEmpty(self):
return self.size == 0
# Function to add an item to the queue.
# It changes rear and size
def EnQueue(self, item):
if self.isFull():
print("Full")
return
self.rear = (self.rear + 1) % (self.capacity)
self.Q[self.rear] = item
self.size = self.size + 1
print("% s enqueued to queue" % str(item))
# Function to remove an item from queue.
# It changes front and size
def DeQueue(self):
if self.isEmpty():
print("Empty")
return
print("% s dequeued from queue" % str(self.Q[self.front]))
self.front = (self.front + 1) % (self.capacity)
self.size = self.size - 1
# Function to get front of queue
def que_front(self):
if self.isEmpty():
print("Queue is empty")
print("Front item is", self.Q[self.front])
# Function to get rear of queue
def que_rear(self):
if self.isEmpty():
print("Queue is empty")
print("Rear item is", self.Q[self.rear])
# Driver Code
if __name__ == '__main__':
queue = Queue(30)
queue.EnQueue(10)
queue.EnQueue(20)
queue.EnQueue(30)
queue.EnQueue(40)
queue.DeQueue()
queue.que_front()
queue.que_rear()
# This code is contributed by Susobhan Akhuli
// C# program for array implementation of queue
using System;
namespace w3wiki {
// A class to represent a linearqueue
class Queue {
private int[] ele;
private int front;
private int rear;
private int max;
public Queue(int size)
{
ele = new int[size];
front = 0;
rear = -1;
max = size;
}
// Function to add an item to the queue.
// It changes rear and size
public void enqueue(int item)
{
if (rear == max - 1) {
Console.WriteLine("Queue Overflow");
return;
}
else {
ele[++rear] = item;
}
}
// Function to remove an item from queue.
// It changes front and size
public int dequeue()
{
if (front == rear + 1) {
Console.WriteLine("Queue is Empty");
return -1;
}
else {
Console.WriteLine(ele[front]
+ " dequeued from queue");
int p = ele[front++];
Console.WriteLine("Front item is {0}",
ele[front]);
Console.WriteLine("Rear item is {0} ",
ele[rear]);
return p;
}
}
// Function to print queue.
public void printQueue()
{
if (front == rear + 1) {
Console.WriteLine("Queue is Empty");
return;
}
else {
for (int i = front; i <= rear; i++) {
Console.WriteLine(ele[i]
+ " enqueued to queue");
}
}
}
}
// Driver code
class Program {
static void Main()
{
Queue Q = new Queue(5);
Q.enqueue(10);
Q.enqueue(20);
Q.enqueue(30);
Q.enqueue(40);
Q.printQueue();
Q.dequeue();
}
}
}
// This code is contributed by Susobhan Akhuli
<script>
// Queue class
class Queue
{
// Array is used to implement a Queue
constructor()
{
this.items = [];
}
isEmpty()
{
// return true if the queue is empty.
return this.items.length == 0;
}
enqueue(element)
{
// adding element to the queue
this.items.push(element);
document.write(element + " enqueued to queue<br>");
}
dequeue()
{
// removing element from the queue
// returns underflow when called
// on empty queue
if(this.isEmpty())
return "Underflow<br>";
return this.items.shift();
}
front()
{
// returns the Front element of
// the queue without removing it.
if(this.isEmpty())
return "No elements in Queue<br>";
return this.items[0];
}
rear()
{
// returns the Rear element of
// the queue without removing it.
if(this.isEmpty())
return "No elements in Queue<br>";
return this.items[this.items.length-1];
}
}
// creating object for queue class
var queue = new Queue();
// Adding elements to the queue
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
// queue contains [10, 20, 30, 40]
// removes 10
document.write(queue.dequeue() + " dequeued from queue<br>");
// queue contains [20, 30, 40]
// Front is now 20
document.write("Front item is " + queue.front() + "<br>");
// printing the rear element
// Rear is 40
document.write("Rear item is " + queue.rear() + "<br>");
// This code is contributed by Susobhan Akhuli
</script>
Output
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40
Introduction to Queue Data Structure
Queue Data Structure is a linear data structure that follows FIFO (First In First Out) Principle, so the first element inserted is the first to be popped out. In this article, we will cover all the basics of Queue, Operations on Queue, its implementation, advantages, disadvantages which will help you solve all the problems based on Queue.
Table of Content
- What is Queue Data Structure?
- Representation of Queue Data Structure:
- Types of Queue Data Structure
- Basic Operations in Queue Data Structure
- 1. Enqueue Operation in Queue Data Structure
- 2. Dequeue Operation in Queue Data Structure
- 3. Front Operation in Queue Data Structure
- 4. Rear Operation in Queue Data Structure
- 5. isEmpty Operation in Queue Data Structure
- 6. isFull Operation in Queue Structure
- Implementation of Queue Data Structure
- Complexity Analysis of Operations on Queue Data Structure
- Applications of Queue Data Structure
- Advantages of Queue Data Structure
- Disadvantages of Queue Data Structure
- FAQs (Frequently asked questions) on Queue Data Structure