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();
}

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邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。