Hot Topics
Data Structure
Dequeue using Array
Algorithm
Take an array and two pointers called front and rear,initiate both of them at -1 as at first the dequeue will be empty
pushFront() – To push elements at the front of dequeue we can have 4 cases.
Check for if the dequeue is full
Check if the dequeue is empty then reassign front and rear at 0
If the front is pointing at the 0th index but the rear is not pointing to the last index of dequeue then we reassign front pointer to the last index
In normal case we insert at front and decrease front by 1
pushRear() – To push elements from the rear of dequeue we have 4 cases
If the dequeue is full we can’t push elements
If the dequeue is empty then reassign the front and rear to 0 index
The rear is pointing to the last index of dequeue and the front is not pointing at the 0th index then reassign the rear to the 0th index
In normal case we increase rear and insert element in that position
popFront() – To pop elements from front we have 4 cases
The dequeue is empty then we can’t do anything to it
When a single element is present remove it and reassign front and rear to -1 which tells the dequeue is empty
If the front has reached the last index then reassign the front as 0 to maintain the cyclic nature
In normal flow remove the element from front and increase the front index by 1.
popRear() – To pop elements from rear we have 4 cases
If the dequeue is empty we can’t do anything
When a single element is present in the dequeue we reassign front and rear to -1 as the dequeue becomes empty
If the rear is pointing to 0 then to maintain the cyclic nature make rear to point to the last index of the dequeue
In the normal flow remove element from rear and decrease rear by 1
getFront() – Get the element from the index pointed by front variable
getRear() – Get the element from the index pointed by rear variable
#include
using namespace std;
class Deque
{
int *arr;
int front;
int rear;
int size;
public:
// Initializing the data structure.
Deque(int n)
{
size = n;
arr = new int[size];
front = -1;
rear = -1;
}
// Pushes 'X' in the front of the deque
void pushFront(int x)
{
// check full or not
if (isFull())
{
cout << "The dequeue is full" << endl;
}
// check if it is empty or not
else if (isEmpty())
{
front = rear = 0;
}
// creating cyclic nature
else if (front == 0 && rear != size - 1)
{
front = size - 1;
}
// normal flow
else
{
front--;
}
arr[front] = x;
cout << "The element inserted at front is:" << x << endl;
}
// Pushes 'X' in the back of the deque.
void pushRear(int x)
{
// check full or not
if (isFull())
{
cout << "The dequeue is full" << endl;
}
// check if empty or not
else if (isEmpty())
{
front = rear = 0;
}
// creating cyclic nature
else if (rear == size - 1 && front != 0)
{
rear = 0;
}
// when in normal flow
else
{
rear++;
}
arr[rear] = x;
cout << "The element inserted at rear is:" << x << endl;
}
// Pops an element from the front of the deque
void popFront()
{
// to check queue is empty
if (isEmpty())
{
cout << "Queue is Empty " << endl;
}
// storing the element denoted by front in a variable
int ans = arr[front];
// storing -1 in that place as we need to empty the place
arr[front] = -1;
// //single element is present
if (front == rear)
{
front = rear = -1;
}
// to maintain cyclic nature
else if (front == size - 1)
{
front = 0;
}
// normal flow
else
{
front++;
}
cout << "The element popped out from rear is:" << ans << endl;
}
// Pops an element from the back of the deque.
void popRear()
{
// to check queue is empty
if (isEmpty())
{
cout << "Queue is Empty " << endl;
}
// storing the element denoted by front in a variable
int ans = arr[rear];
// storing -1 in that place as we need to empty the place
arr[rear] = -1;
// single element is present
if (front == rear)
{
front = rear = -1;
}
// to maintain cyclic nature
else if (rear == 0)
{
rear = size - 1;
}
// normal flow
else
{
rear--;
}
cout << "The element popped out from rear is:" << ans << endl;
}
void display()
{
if (front == -1)
cout << "Dequeue is empty" << endl;
else
{
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
}
cout << endl;
}
// Returns the first element of the deque. If the deque is empty, it returns -1.
int getFront()
{
if (isEmpty())
{
cout <<”Queue is empty” << endl;
return -1;
}
cout << "The element at the front of dequeue is:" << arr[front] << endl;
return arr[front];
}
// Returns the last element of the deque. If the deque is empty, it returns -1.
int getRear()
{
if (isEmpty())
{
cout <<”Queue is empty” << endl;
return -1;
}
cout << "The element at the rear of dequeue is:" << arr[rear] << endl;
return arr[rear];
}
// Returns true if the deque is empty. Otherwise returns false.
bool isEmpty()
{
if (front == -1)
return true;
else
return false;
}
// Returns true if the deque is full. Otherwise returns false.
bool isFull()
{
if ((front == 0 && rear == size - 1) || (front != 0 && rear == (front - 1) % (size - 1)))
{
return true;
}
else
{
return false;
}
}
};
int main()
{
Deque dq(5);
// Function calls
dq.pushRear(5);
dq.pushRear(10);
dq.display();
dq.getRear();
dq.pushFront(15);
dq.getFront();
dq.popFront();
dq.getFront();
return 0;
}
Output
The element inserted at rear is:5
The element inserted at rear is:10
5 10
The element at the rear of dequeue is10
The element inserted at front is:15
The element at the front of dequeue is:15
The element popped out from rear is:15
The element at the front of dequeue is:5
Automata Fixing