Array implementation of queue (Simple)
How to implement Queue using Array?
To implement a queue using an array,
- create an array arr of size n and
- take two variables front and rear both of which will be initialized to 0 which means the queue is currently empty.
- Element
- rear is the index up to which the elements are stored in the array and
- front is the index of the first element of the array.
Now, some of the implementations of queue operations are as follows:
- Enqueue: Addition of an element to the queue. Adding an element will be performed after checking whether the queue is full or not. If rear == size then it is said to be an Overflow condition as the array is full.else which indicates that the array is not full then store the element at arr[rear] and increment rear by 1 .
- Dequeue: Removal of an element from the queue. An element can only be deleted when there is at least an element to delete. If front == rear, then it is said to be an Underflow condition as the array is empty . else, the element at arr[front] can be deleted but all the remaining elements have to shift to the left by one position in order for the dequeue operation to delete the second element from the left on another dequeue operation.
- Front: Get the front element from the queue i.e. arr[front] if the queue is not empty.
- Display: Print all elements of the queue. If the queue is non-empty, traverse and print all the elements from the index front to rear.
Below is the implementation of a queue using an array:
In the below code , we are initializing front and rear as 0, but in general we have to initialize it with -1.
If we assign rear as 0, rear will always point to next block of the end element, in fact , rear should point the index of last element,
eg. When we insert element in queue , it will add in the end i.e. after the current rear and then point the rear to the new element ,
According to the following code:
IN the first dry run, front=rear = 0;
in void queueEnqueue(int data)
else part will be executed,
so arr[rear] =data;// rear =0, rear pointing to the latest element
rear++; //now rear = 1, rear pointing to the next block after end element not the end element
//that’s against the original definition of rear
// C++ program to implement a queue using an array
#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[c];
}
~Queue() { delete[] queue; }
// function to insert an element
// at the rear of the queue
void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
printf("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = data;
rear++;
}
return;
}
// function to delete an element
// from the front of the queue
void queueDequeue()
{
// if queue is empty
if (front == rear) {
printf("\nQueue is empty\n");
return;
}
// shift all the elements from index 2 till rear
// to the left by one
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
// decrement rear
rear--;
}
return;
}
// print queue elements
void queueDisplay()
{
int i;
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i < rear; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
// print front of queue
void queueFront()
{
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[front]);
return;
}
};
// Driver code
int main(void)
{
// Create a queue of capacity 4
Queue q(4);
// print Queue elements
q.queueDisplay();
// inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
// print Queue elements
q.queueDisplay();
// insert element in the queue
q.queueEnqueue(60);
// print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
printf("\n\nafter two node deletion\n\n");
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
return 0;
}
// Java program to implement a queue using an array
class Queue {
static private int front, rear, capacity;
static private int queue[];
Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int[capacity];
}
// function to insert an element
// at the rear of the queue
static void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
System.out.printf("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = data;
rear++;
}
return;
}
// function to delete an element
// from the front of the queue
static void queueDequeue()
{
// if queue is empty
if (front == rear) {
System.out.printf("\nQueue is empty\n");
return;
}
// shift all the elements from index 2 till rear
// to the right by one
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
// store 0 at rear indicating there's no element
if (rear < capacity)
queue[rear] = 0;
// decrement rear
rear--;
}
return;
}
// print queue elements
static void queueDisplay()
{
int i;
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i < rear; i++) {
System.out.printf(" %d <-- ", queue[i]);
}
return;
}
// print front of queue
static void queueFront()
{
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}
System.out.printf("\nFront Element is: %d",
queue[front]);
return;
}
}
public class StaticQueueinjava {
// Driver code
public static void main(String[] args)
{
// Create a queue of capacity 4
Queue q = new Queue(4);
// print Queue elements
q.queueDisplay();
// inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
// print Queue elements
q.queueDisplay();
// insert element in the queue
q.queueEnqueue(60);
// print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
System.out.printf(
"\n\nafter two node deletion\n\n");
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
}
}
# Python3 program to implement
# a queue using an array
class Queue:
# To initialize the object.
def __init__(self, c):
self.queue = []
self.front = self.rear = 0
self.capacity = c
# Function to insert an element
# at the rear of the queue
def queueEnqueue(self, data):
# Check queue is full or not
if(self.capacity == self.rear):
print("\nQueue is full")
# Insert element at the rear
else:
self.queue.append(data)
self.rear += 1
# Function to delete an element
# from the front of the queue
def queueDequeue(self):
# If queue is empty
if(self.front == self.rear):
print("Queue is empty")
# Pop the front element from list
else:
x = self.queue.pop(0)
self.rear -= 1
# Function to print queue elements
def queueDisplay(self):
if(self.front == self.rear):
print("\nQueue is Empty")
# Traverse front to rear to
# print elements
for i in self.queue:
print(i, "<--", end='')
# Print front of queue
def queueFront(self):
if(self.front == self.rear):
print("\nQueue is Empty")
print("\nFront Element is:",
self.queue[self.front])
# Driver code
if __name__ == '__main__':
# Create a new queue of
# capacity 4
q = Queue(4)
# Print queue elements
q.queueDisplay()
# Inserting elements in the queue
q.queueEnqueue(20)
q.queueEnqueue(30)
q.queueEnqueue(40)
q.queueEnqueue(50)
# Print queue elements
q.queueDisplay()
# Insert element in queue
q.queueEnqueue(60)
# Print queue elements
q.queueDisplay()
q.queueDequeue()
q.queueDequeue()
print("\n\nafter two node deletion\n")
# Print queue elements
q.queueDisplay()
# Print front of queue
q.queueFront()
# This code is contributed by Amit Mangal
// C# program to implement a queue using an array
using System;
public class Queue {
private int front, rear, capacity;
private int[] queue;
public Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int[capacity];
}
// function to insert an element
// at the rear of the queue
public void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
Console.Write("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = data;
rear++;
}
return;
}
// function to delete an element
// from the front of the queue
public void queueDequeue()
{
// if queue is empty
if (front == rear) {
Console.Write("\nQueue is empty\n");
return;
}
// shift all the elements from index 2 till rear
// to the right by one
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
// store 0 at rear indicating there's no element
if (rear < capacity)
queue[rear] = 0;
// decrement rear
rear--;
}
return;
}
// print queue elements
public void queueDisplay()
{
int i;
if (front == rear) {
Console.Write("\nQueue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i < rear; i++) {
Console.Write(" {0} <-- ", queue[i]);
}
return;
}
// print front of queue
public void queueFront()
{
if (front == rear) {
Console.Write("\nQueue is Empty\n");
return;
}
Console.Write("\nFront Element is: {0}",
queue[front]);
return;
}
}
public class StaticQueueinjava {
// Driver code
public static void Main(String[] args)
{
// Create a queue of capacity 4
Queue q = new Queue(4);
// print Queue elements
q.queueDisplay();
// inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
// print Queue elements
q.queueDisplay();
// insert element in the queue
q.queueEnqueue(60);
// print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
Console.Write("\n\nafter two node deletion\n\n");
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
}
}
// This code has been contributed by 29AjayKumar
<script>
// Javascript program to implement a queue using an array
class Queue{
constructor(c)
{
this.front = this.rear = 0;
this.capacity = c;
this.queue = new Array(this.capacity);
}
// Function to insert an element
// at the rear of the queue
queueEnqueue(data)
{
// Check queue is full or not
if (this.capacity == this.rear)
{
document.write("<br>Queue is full<br>");
return;
}
// insert element at the rear
else
{
this.queue[this.rear] = data;
this.rear++;
}
return;
}
// Function to delete an element
// from the front of the queue
queueDequeue()
{
// If queue is empty
if (this.front == this.rear)
{
document.write("<br>Queue is empty<br>");
return;
}
// Shift all the elements from index 2 till rear
// to the right by one
else
{
for(let i = 0; i < this.rear - 1; i++)
{
this.queue[i] = this.queue[i + 1];
}
// Store 0 at rear indicating there's no element
if (this.rear < this.capacity)
this.queue[this.rear] = 0;
// Decrement rear
this.rear--;
}
return;
}
// Print queue elements
queueDisplay()
{
let i;
if (this.front == this.rear)
{
document.write("<br>Queue is Empty<br>");
return;
}
// Traverse front to rear and print elements
for(i = this.front; i < this.rear; i++)
{
document.write(this.queue[i] + " <-- ");
}
return;
}
// Print front of queue
queueFront()
{
if (this.front == this.rear)
{
document.write("<br>Queue is Empty<br>");
return;
}
document.write("<br>Front Element is: " +
this.queue[this.front]);
return;
}
}
// Driver code
// Create a queue of capacity 4
let q = new Queue(4);
// Print Queue elements
q.queueDisplay();
// Inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
// Print Queue elements
q.queueDisplay();
// Insert element in the queue
q.queueEnqueue(60);
// Print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
document.write("<br><br> after two node deletion <br><br>");
// Print Queue elements
q.queueDisplay();
// Print front of the queue
q.queueFront();
// This code is contributed by rag2127
</script>
Output
Queue is Empty 20 <-- 30 <-- 40 <-- 50 <-- Queue is full 20 <-- 30 <-- 40 <-- 50 <-- after two node deletion 40 <-- 50 <-- Front Element is: 40
Time Complexity: O(1) for Enqueue (element insertion in the queue) as we simply increment pointer and put value in array and O(N) for Dequeue (element removing from the queue) as we use for loop to implement that.
Auxiliary Space: O(N), as here we are using an N size array for implementing Queue
Optimizations :
We can implement both enqueue and dequeue operations in O(1) time. To achieve this, we can either use Linked List Implementation of Queue or circular array implementation of queue.
Contact Us