Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active May 25, 2024 10:46
Show Gist options
  • Save mycodeschool/7331785 to your computer and use it in GitHub Desktop.
Save mycodeschool/7331785 to your computer and use it in GitHub Desktop.
Queue - Array Implementation
/* 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();
}
@imrun-n
Copy link

imrun-n commented Nov 12, 2017

#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.

@Narayan003
Copy link

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

@adist98
Copy link

adist98 commented Jan 5, 2018

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

@R-INYURU
Copy link

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

@Mgynius
Copy link

Mgynius commented Apr 29, 2018

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.

@tejasparab1994
Copy link

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

Copy link

ghost commented Jul 14, 2018

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

@chaleelaleela
Copy link

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];
}

};

@dhirajgupta811
Copy link

dhirajgupta811 commented Oct 2, 2018

#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

@theepag
Copy link

theepag commented Dec 31, 2018

@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

@Rushu-geek
Copy link

Full tempo

@tridibsamanta
Copy link

Queue implementation using circular array in C -

Click here for the souce code

Copy link

ghost commented Mar 17, 2020

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)

@Rittik7
Copy link

Rittik7 commented Jun 21, 2021

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

@MiladZarour
Copy link

Thx everyone !
that was really helpful !

@aadishJ01
Copy link

// 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;

}

@Aatrox00
Copy link

Aatrox00 commented Jun 1, 2022 via email

@Olatomiwaola
Copy link

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

@Aatrox00
Copy link

Aatrox00 commented Nov 19, 2022 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment