Skip to content

Instantly share code, notes, and snippets.

@m-primo
Created April 25, 2020 14:02
Show Gist options
  • Save m-primo/676c0279c3d8e7872001ea33c8b07a16 to your computer and use it in GitHub Desktop.
Save m-primo/676c0279c3d8e7872001ea33c8b07a16 to your computer and use it in GitHub Desktop.
Simple Queue Implementation in c++
#include <iostream>
using namespace std;
#define null 0
class QueueArray {
private:
int front;
int rear;
int numOfEl;
int size;
int *queueArr;
void resize() {
int tempSize = size * 2;
int *tempArr = new int[tempSize];
for(int i = 0; i < size; i++) tempArr[i] = queueArr[(front + i) % size];
delete[] queueArr;
queueArr = tempArr;
front = 0;
rear = size - 1;
size = tempSize;
}
public:
QueueArray(int size) {
front = rear = -1;
this->size = size;
queueArr = new int[size];
numOfEl = 0;
}
void Enqueue(int data) {
if(numOfEl == size) resize();
if(front == -1 && rear == -1) front = rear = 0;
else rear = (rear + 1) % size;
queueArr[rear] = data;
numOfEl++;
}
void Dequeue() {
if(numOfEl != 0) {
if(front == rear) rear = front = -1;
else front = (front + 1) % size;
numOfEl--;
}
}
void print() {
int count = (rear + size - front) % size + 1;
for(int i = 0; i < count; i++) {
cout << queueArr[(front + i) % size] << endl;
}
cout << endl;
}
void test() {
Enqueue(4);
Enqueue(2);
Enqueue(7);
Enqueue(8);
print();
Dequeue();
Dequeue();
print();
}
~QueueArray() {
delete[] queueArr;
}
};
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
next = null;
}
};
class QueueLinkedList {
private:
Node *front;
Node *rear;
public:
QueueLinkedList() {
front = rear = null;
}
void Enqueue(int data) {
Node *n = new Node(data);
if(rear == null) rear = front = n;
else {
rear->next = n;
rear = n;
}
}
void Dequeue() {
if(front != null) {
Node *temp = front;
if(front == rear) front = rear = null;
else front = front->next;
delete(temp);
}
}
void print() {
Node *temp = front;
while(temp != null) {
cout << temp->data << endl;
temp = temp->next;
}
cout << endl;
}
void test() {
Enqueue(666);
Enqueue(7);
Enqueue(21);
print();
Dequeue();
Dequeue();
print();
}
~QueueLinkedList() {
Node *next;
while(front != null) {
next = front->next;
delete front;
front = next;
}
front = null;
rear = null;
}
};
int main() {
cout << endl << "Array:" << endl;
QueueArray qa(4);
qa.test();
cout << endl << "Linked List:" << endl;
QueueLinkedList qll;
qll.test();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment