Queue - Array Implementation

Queue_CircularArrayImplementation.cpp

/* Queue - Circular Array implementation in C++*/
#include<iostream>
using namespace std; 
#define MAX_SIZE 101  //maximum size of the array that will store Queue. 

// Creating a class named Queue.
class Queue
{
private:
	int A[MAX_SIZE];
	int front, rear; 
public:
	// Constructor - set front and rear as -1. 
	// We are assuming that for an empty Queue, both front and rear will be -1.
	Queue()
	{
		front = -1; 
		rear = -1;
	}

	// To check wheter Queue is empty or not
	bool IsEmpty()
	{
		return (front == -1 && rear == -1); 
	}

	// To check whether Queue is full or not
	bool IsFull()
	{
		return (rear+1)%MAX_SIZE == front ? true : false;
	}

	// Inserts an element in queue at rear end
	void Enqueue(int x)
	{
		cout<<"Enqueuing "<<x<<" \n";
		if(IsFull())
		{
			cout<<"Error: Queue is Full\n";
			return;
		}
		if (IsEmpty())
		{ 
			front = rear = 0; 
		}
		else
		{
		    rear = (rear+1)%MAX_SIZE;
		}
		A[rear] = x;
	}

	// Removes an element in Queue from front end. 
	void Dequeue()
	{
		cout<<"Dequeuing \n";
		if(IsEmpty())
		{
			cout<<"Error: Queue is Empty\n";
			return;
		}
		else if(front == rear ) 
		{
			rear = front = -1;
		}
		else
		{
			front = (front+1)%MAX_SIZE;
		}
	}
	// Returns element at front of queue. 
	int Front()
	{
		if(front == -1)
		{
			cout<<"Error: cannot return front from empty queue\n";
			return -1; 
		}
		return A[front];
	}
	/* 
	   Printing the elements in queue from front to rear. 
	   This function is only to test the code. 
	   This is not a standard function for Queue implementation. 
	*/
	void Print()
	{
		// Finding number of elements in queue  
		int count = (rear+MAX_SIZE-front)%MAX_SIZE + 1;
		cout<<"Queue       : ";
		for(int i = 0; i <count; i++)
		{
			int index = (front+i) % MAX_SIZE; // Index of element while travesing circularly from front
			cout<<A[index]<<" ";
		}
		cout<<"\n\n";
	}
};
int main()
{
	/*Driver Code to test the implementation
	  Printing the elements in Queue after each Enqueue or Dequeue 
	*/
   Queue Q; // creating an instance of Queue. 
   Q.Enqueue(2);  Q.Print();  
   Q.Enqueue(4);  Q.Print();  
   Q.Enqueue(6);  Q.Print();
   Q.Dequeue();	  Q.Print();
   Q.Enqueue(8);  Q.Print();
}

include <stdio.h>

include <stdlib.h>

include <string.h>

define MAX 3

int arr[MAX];
int front, rear;

bool isEmpty(){
return (front == -1 && rear == -1) ? true : false;
}

bool isFull(){
return (rear+1)%MAX == front ? true : false;
}

void enQueue(int x){
if(isFull()){
printf("queue is full\n");
return;
}
if(isEmpty())
front = rear = 0;
else
rear = (rear+1)%MAX;

arr[rear] = x;

}
void deQueue(){
if(isEmpty()){
printf("queue is empty\n");
return;
}
else if(front == rear)
front = rear = -1;
else
front = (front+1)%MAX;

}

void Print(){
int length = (rear + MAX - front)%MAX + 1;
int i;
for( i = 0; i<length;i++){
printf("%d ", arr[(front+i)%MAX]);
}
printf("\n");
}

int main(){
front = -1;
rear = -1;
enQueue(2); Print();
enQueue(4); Print();
enQueue(6); Print();
deQueue(); Print();
enQueue(10); Print();
return 0;
}

include<stdio.h>

define MAXSIZE 3

typedef struct
{
int data[MAXSIZE];
int front,rear;
}QUEUE;

void initq(QUEUE *pq)
{
pq->front=pq->rear=MAXSIZE-1;
}

int isempty(QUEUE *pq)
{
return(pq->front==pq->rear);
}

int isfull(QUEUE *pq)
{
return((pq->rear+1)%MAXSIZE==pq->front);
}

void addq(QUEUE *pq,int num)
{
pq->rear=(pq->rear+1)%MAXSIZE;
pq->data[pq->rear]=num;
}

int removeq(QUEUE *pq)
{
pq->front=(pq->front+1)%MAXSIZE;
return pq->data[pq->front];
}

void main()
{
int n,choice;
QUEUE q1;
initq(&q1);
do
{
printf("\n1.ADD\n2.DELETE\n3.EXIT\n");
printf("\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter element to be added:");
scanf("%d",&n);
if(isfull(&q1))
printf("\nQUEUE OVERFLOW\n");
else
addq(&q1,n);
break;
case 2:
if(isempty(&q1))
printf("\nQueue is empty\n");
else
printf("\nThe deleted element is %d",removeq(&q1));
break;
}
}while(choice!=3);
}

Here MAXSIZE is 3 but i'm able to add only 2 elements .Can anyone help?

fsociety123 in your code for array implementation as queue there is a mistake.

When there is no element in the queue i.e. both front=rear=-1 then while deQueue() gives empty queue but the print function right after it prints the value 0.
Because you forgot to mention the same isEmpty() function in Print() as well.

Please add:-
if ( isEmpty() )
{
return;
}

it'll fix this minor bug. Rest it's perfect and very easy. Thanks for sharing.

#include
#include
#define mx 111
using namespace std;
class queu
{
private:
int a[mx],head,rear;
public:
queu()
{
head=-1;
rear=-1;
}
bool isempty()
{
if(head==-1 && rear==-1)
return true;
else false;
}
bool isfull()
{
if((rear+1)% mx==head)
return true;
else false;
}
void enqueue(int x)
{
if(isfull())
return;
else if(isempty())
{
rear=head=0;
}
else rear=(rear+1)% mx;
a[rear]=x;
}
void dequeue()
{
if(isempty())
return;
else if(rear==head)
rear=head=-1;
else head=(head+1)%mx;
}
int fron()
{
if(isempty())
return -1;
return a[head];
}
void print()
{
int n=((rear+mx-head)% mx)+1;
for(int i=0;i<n;i++)
{
int t=(head+i)% mx;
printf("%d ",a[t]);
}
}
};
int main()
{
queu q;
q.enqueue(1);
q.print();
q.enqueue(7);
q.enqueue(4);
q.enqueue(0);
q.enqueue(41);
q.enqueue(3);
q.print();
return 0;
}
please help.what is the problem.it gives gurbage value.

/* Queue - Circular Array implementation in C++*/

**#include

using namespace std;
#define MAX_SIZE 101 //maximum size of the array that will store Queue.**

// Creating a class named Queue.
class Queue
{
private:
int A[MAX_SIZE];
int front, rear;
public:
// Constructor - set front and rear as -1.
// We are assuming that for an empty Queue, both front and rear will be -1.
Queue()
{
front = -1;
rear = -1;
}

// To check wheter Queue is empty or not
bool IsEmpty()
{
	return (front == -1 && rear == -1); 
}

// To check whether Queue is full or not
bool IsFull()
{
	return (rear+1)%MAX_SIZE == front ? true : false;
}

// Inserts an element in queue at rear end
void Enqueue(int x)
{
	cout<<"Enqueuing "<<x<<" \n";
	if(IsFull())
	{
		cout<<"Error: Queue is Full\n";
		return;
	}
	if (IsEmpty())
	{ 
		front = rear = 0; 
	}
	else
	{
	    rear = (rear+1)%MAX_SIZE;
	}
	A[rear] = x;
}

// Removes an element in Queue from front end. 
void Dequeue()
{
	cout<<"Dequeuing \n";
	if(IsEmpty())
	{
		cout<<"Error: Queue is Empty\n";
		return;
	}
	else if(front == rear ) 
	{
		rear = front = -1;
	}
	else
	{
		front = (front+1)%MAX_SIZE;
	}
}
// Returns element at front of queue. 
int Front()
{
	if(front == -1)
	{
		cout<<"Error: cannot return front from empty queue\n";
		return -1; 
	}
	return A[front];
}
/* 
   Printing the elements in queue from front to rear. 
   This function is only to test the code. 
   This is not a standard function for Queue implementation. 
*/
void Print()
{
	// Finding number of elements in queue  
	int count = (rear+MAX_SIZE-front)%MAX_SIZE + 1;
	cout<<"Queue       : ";
	for(int i = 0; i <count; i++)
	{
		int index = (front+i) % MAX_SIZE; // Index of element while travesing circularly from front
		cout<<A[index]<<" ";
	}
	cout<<"\n\n";
}

};
int main()
{
/*Driver Code to test the implementation
Printing the elements in Queue after each Enqueue or Dequeue
*/
Queue Q; // creating an instance of Queue.
Q.Enqueue(2); Q.Print();
Q.Enqueue(4); Q.Print();
Q.Enqueue(6); Q.Print();
Q.Dequeue(); Q.Print();
Q.Enqueue(8); Q.Print();
}#

can anyone please explain the use of % in enqueue function.

@adist98 the % sign in enqueue is the Modulo operation which calculates the remainder.

I want to create a queue with growth capability.
Rather than using the constant array size, i want it to be determined at runtime,
Incase of enqueue, the array size doubles when the queue is full and it halves for dequeue if the number of remaining elements is less than half the original array size
Please help.

@Mgynius why don't you use a linkedList for such implementation?

@Mgynius : You can use ArrayList or increase the size of array dynamically.

class queue
{
private:
int rear;
int front;
static const int arrLength = 5;
int arr[arrLength];

bool isEmpty ; //tracker

public:
queue() : front{ 0 }, rear{ 0 }, isEmpty{ true } {};

void enqueue(int number)
{		
	if ((rear + 1) % arrLength == front) //queue is full
		return;	
	else if (!isEmpty) 
	{
		rear = (rear + 1) % arrLength;			
	}
	
	arr[rear] = number;	
	isEmpty = false;
}

void dequeue()
{
	if (isEmpty) //empty
		return;
	else if (front == rear) // set to empty
	{
		front = rear = 0;
		isEmpty = true;
		return;
	}
	else		
		front = (front + 1) % arrLength;		
}

int showFront()
{
	return arr[front];
}

};

#include
using namespace std;

class Queue {
int size;
int *arr;
int front;
int rear;

    public:
        Queue(int size) {
            this->size = size;
	arr = new int[size];
	front = -1;
	rear = -1;
}

bool isEmpty() {
	return (front == -1 && rear == -1) ? true : false;
}

bool isFull() {
	return (rear+1)%size == front ? true : false;
}

void qinsert(int data) {
	cout << "inserting: " << data;
	if(isFull()) 
		cout << " error : full";
	else if(isEmpty()) {
		front = rear = 0;
		arr[rear] = data;
	}
	else {
		rear = (rear+1)%size;
		arr[rear] = data;
	}
	cout << endl;
}

void qdelete() {
	cout << "deleting : " << peekfront();
	if(isEmpty())
		cout << " error : empty";
	else if(rear == front) {
		rear = front = -1;
	}
	else {
		
		front = (front+1)%size;
	}
	cout << endl;
}

void print() {
	cout << "printing : ";
	if(isEmpty()) 
		cout << " error : empty";
	else {
		for(int i = front; i != rear; i = (i+1)%size)
			cout << arr[i] << " ";
		cout << arr[rear];
	}
	cout << endl;
}

int peekfront() {
	if(!isEmpty())
		return arr[front];
}

int peekrear() {
	if(!isEmpty())
		return arr[rear];	
}

};

int main() {
Queue q(5);

q.qinsert(10);
q.qinsert(20);
q.qinsert(30);
q.qinsert(40);
q.qinsert(50);

q.print();

q.qdelete();		
q.qdelete();		
q.qdelete();				
q.qdelete();				
q.qdelete();				

q.print();	

q.qinsert(10);
q.qinsert(20);
q.qinsert(30);
q.qinsert(40);
q.qinsert(50);
q.qinsert(60);

return 0;

}

OUTPUT:
inserting: 10
inserting: 20
inserting: 30
inserting: 40
inserting: 50
printing : 10 20 30 40 50
deleting : 10
deleting : 20
deleting : 30
deleting : 40
deleting : 50
printing : error : empty
inserting: 10
inserting: 20
inserting: 30
inserting: 40
inserting: 50
inserting: 60 error : full

@adist98 '%' this is called module, and it will give the balance amount
for example 5%2
if we dive 5 by two it will give 1 as balance, so
that's what done by % operator

Full tempo

Queue implementation using circular array in C -

Click here for the souce code

can anyone please explain the use of % in enqueue function.

We are trying to make sure that indices are in fixed range .i.e less than the size of array ,where as in linear array array size can be increased dynamically(taking one more array twice the size and copying them...),but by the use of circular array, no need to increase array size dynamically, instead can be inserted in previously dequeued cells with in the index range in previously dequeued cells(saves space)

### C Code
#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 3

int arr[MAX_SIZE];
int tail = -1;
int front = -1;
void EnQueue(int x)
{
if((tail+1)%MAX_SIZE == front){
printf("Error: Overeflow");
return;
}
if(tail == -1 && front == -1)
{
front++;
}
tail = (tail + 1)%MAX_SIZE;
arr[tail] = x;
}

int DeQueue()
{
if(front == -1 && tail == -1)
{
printf("Queue is emptey!!");
}
if(front == tail)
{
printf("Deleted vale: %d",arr[front]);
front = -1;
tail = -1;
}
else
{
printf("Deleted vale: %d",arr[front]);
printf("\n");
front =(front+1)%MAX_SIZE;
}
}

void IsEmptey()
{
if(front == -1 && tail == -1)
{
printf("Queue is emptey..");
}
else
printf("Queue is not emptey");
}

void Print()
{
printf("Queue is: ");
int i,count = ((tail + MAX_SIZE - front) % MAX_SIZE) + 1;
for(i = 0; i < count; i++) {
int index = (front + i) % MAX_SIZE;
printf("%d ",arr[index]);
}
printf("\n");
}

int main(){
Print();
IsEmptey();
EnQueue(11);
Print();
EnQueue(99);
Print();
DeQueue();
Print();
EnQueue(10);
Print();
DeQueue();
Print();
IsEmptey();
EnQueue(80);
Print();
DeQueue();
Print();
EnQueue(90);
Print();
}

Thx everyone !
that was really helpful !

// C++ code by using class template!

#include<bits/stdc++.h>
using namespace std;

// One Limitation with array based queue is that max size of queueArr pehle se define karni padhegi and so result can overflow.
// To avoid this when overflow is done, tab ek new array bana do with twice the max size.

// We implement circular array for proper usage of memory allocated to us.
template
class Queue{
private:
T* queueArr;
int frontIndex;
int rearIndex;
int mxSize;
public:
// Constructor
Queue(int len);
// Destructor
~Queue();
// Member functions
void push(T val);
void pop();
T front();
void display();
bool empty();
};

template
Queue ::Queue(int len){
mxSize= len;
frontIndex=-1; rearIndex=-1;
queueArr= new T[mxSize];
}

template
Queue ::~Queue(){
delete[] queueArr;
}

template
void Queue::push(T val){
if(rearIndex+1==frontIndex) cout << "Overflow\n";
else{
if(frontIndex==-1 && rearIndex==-1){ frontIndex=0; rearIndex=0; }
else rearIndex=(rearIndex+1)%mxSize;
queueArr[rearIndex]=val;
}

}

template
void Queue::pop(){
if(frontIndex==-1 && rearIndex==-1) cout << "Queue is empty, nothing to pop.\n";
else if(frontIndex==rearIndex){ frontIndex=-1; rearIndex=-1; }
else frontIndex=(frontIndex+1)%mxSize;
}

template
T Queue::front(){
if(frontIndex==-1 && rearIndex==-1){ cout << "Queue is empty, nothing on top.\n"; return INT_MIN; }
else return queueArr[frontIndex];
}

template
void Queue::display(){
if(frontIndex==-1 && rearIndex==-1) cout << "Queue is empty, nothing to display.\n";
else{
int i=frontIndex;
while(i!=rearIndex){
cout << queueArr[i] << " ";
i=(i+1)%mxSize;
}
cout << queueArr[rearIndex] << "\n";
}
}

template
bool Queue::empty(){
if(frontIndex==-1 && rearIndex==-1) return true;
else return false;
}

int main(){
Queue q(10);
// for(int i=0;i<10;++i) q.push(i+1);
q.push(10);
q.display();
q.pop();
q.display();
q.push(11);
q.display();
q.pop();
if(q.front()!=INT_MIN) cout << q.front() << endl;
cout << q.empty() << endl;

return 0;

}

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

For a C program
#include <assert.h> // assert
#include <stdlib.h> // malloc, free
#include <stdbool.h>
#include <stdio.h>

typedef struct node
{
int data;
struct node *next;
} node_t;

typedef struct
{
node_t *rear;
int size;
} queue_t;

queue_t *alloc_queue(void)
{
queue_t *queue = malloc(sizeof(queue_t));
assert(queue != NULL);

queue->rear = NULL;
queue->size = 0;
return queue;

}

void enqueue(queue_t queue, int value)
{
assert(queue!=NULL);
node_t newnode;
node_t *front;
newnode = malloc(sizeof(node_t));
assert(newnode!=NULL);
newnode->data = value;
newnode->next = NULL;
if(queue->rear==NULL) // if the queue is empty
{
queue->rear = newnode;
queue->rear->next = queue->rear;
}
else
{
front = queue->rear->next;
queue->rear->next = newnode;
queue->rear = newnode;
queue->rear->next = front;
}
queue->size++;
}

_

int main()
{
queue_t *queue = alloc_queue();
enqueue(queue, 40);
enqueue(queue, 30);
enqueue(queue, 20);
int a;
front(queue, &a);
}

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。