Last Updated on December 14, 2022 by Prepbytes
What is Deque?
Deque is a double ended queue, i.e. a special kind of queue in which insertion and deletion can be done at the both rear as well as front end of the queue.You can implement both stack and queue by using deque.
What is stack?
Stack follows the principle of LIFO (Last in First out) i.e. element which is inserted at last will be removed first. The operation for insertion of elements in stack is known as Push operation and the operation for deletion of element in stack is known as Pop operation.
What is Queue?
Queue follows the principle of FIFO (First in First out) i.e. element which is inserted first will be removed first. The operation for insertion of elements is known as enqueue operation and the operation for deletion of elements is known as dequeue operation.
Functions of deque that works same as the functions of stack and queue:
| Deque | Stack | Queue |
|---|---|---|
| size() | size() | size() |
| isEmpty() | isEmpty() | isEmpty() |
| Insert_First() | – | – |
| Insert_Last() | Push() | Enqueue() |
| Remove_First() | – | Dequeue() |
| Remove_Last() | Pop() | – |
Operations of Deque
- size(): This function returns the size of the deque.
- isEmpty(): This function returns true if the deque is empty else false.
- Insert_First(element): This function will insert an element in the deque at the front end.
- Insert_Last(element): This function will insert an element in the deque at the rear end.
- Remove_First(): This function will remove the element from the deque which is present at the front end.
- Remove_Last(): This function will remove the element from the deque which is present at the rear end.
#include <bits/stdc++.h>
using namespace std;
struct DQueNode {
int value;
DQueNode* next;
DQueNode* prev;
};
class Deque {
private:
DQueNode* head;
DQueNode* tail;
public:
Deque()
{
head = tail = NULL;
}
bool isEmpty()
{
if (head == NULL)
return true;
return false;
}
int size()
{
if (!isEmpty()) {
DQueNode* temp = head;
int len = 0;
while (temp != NULL) {
len++;
temp = temp->next;
}
return len;
}
return 0;
}
void insert_first(int element)
{
DQueNode* temp = new DQueNode[sizeof(DQueNode)];
temp->value = element;
if (head == NULL) {
head = tail = temp;
temp->next = temp->prev = NULL;
}
else {
head->prev = temp;
temp->next = head;
temp->prev = NULL;
head = temp;
}
}
void insert_last(int element)
{
DQueNode* temp = new DQueNode[sizeof(DQueNode)];
temp->value = element;
if (head == NULL) {
head = tail = temp;
temp->next = temp->prev = NULL;
}
else {
tail->next = temp;
temp->next = NULL;
temp->prev = tail;
tail = temp;
}
}
void remove_first()
{
if (!isEmpty()) {
DQueNode* temp = head;
head = head->next;
if(head) head->prev = NULL;
delete temp;
if(head == NULL) tail = NULL;
return;
}
cout << "List is Empty" << endl;
}
void remove_last()
{
if (!isEmpty()) {
DQueNode* temp = tail;
tail = tail->prev;
if(tail) tail->next = NULL;
delete temp;
if(tail == NULL) head = NULL;
return;
}
cout << "List is Empty" << endl;
}
void display()
{
if (!isEmpty()) {
DQueNode* temp = head;
while (temp != NULL) {
cout << temp->value << " ";
temp = temp->next;
}
cout << endl;
return;
}
cout << "List is Empty" << endl;
}
};
class Stack : public Deque {
public:
void push(int element)
{
insert_last(element);
}
void pop()
{
remove_last();
}
};
class Queue : public Deque {
public:
void enqueue(int element)
{
insert_last(element);
}
void dequeue()
{
remove_first();
}
};
int main()
{
Stack stk;
stk.push(5);
stk.push(10);
cout << "Stack: ";
stk.display();
stk.pop();
cout << "Stack: ";
stk.display();
Queue que;
que.enqueue(12);
que.enqueue(24);
cout << "Queue: ";
que.display();
que.dequeue();
cout << "Queue: ";
que.display();
cout << "Size of Stack is " << stk.size() << endl;
cout << "Size of Queue is " << que.size() << endl;
return 0;
}
class PrepBytes{
static class DQueNode
{
int value;
DQueNode next;
DQueNode prev;
}
static class deque
{
private DQueNode head;
private DQueNode tail;
public deque()
{
head = tail = null;
}
boolean isEmpty()
{
if (head == null)
return true;
return false;
}
int size()
{
if (!isEmpty())
{
DQueNode temp = head;
int len = 0;
while (temp != null)
{
len++;
temp = temp.next;
}
return len;
}
return 0;
}
void insert_first(int element)
{
DQueNode temp = new DQueNode();
temp.value = element;
if (head == null)
{
head = tail = temp;
temp.next = temp.prev = null;
}
else
{
head.prev = temp;
temp.next = head;
temp.prev = null;
head = temp;
}
}
void insert_last(int element)
{
DQueNode temp = new DQueNode();
temp.value = element;
if (head == null)
{
head = tail = temp;
temp.next = temp.prev = null;
}
else
{
tail.next = temp;
temp.next = null;
temp.prev = tail;
tail = temp;
}
}
void remove_first()
{
if (!isEmpty())
{
DQueNode temp = head;
head = head.next;
head.prev = null;
return;
}
System.out.print("List is Empty");
}
void remove_last()
{
if (!isEmpty())
{
DQueNode temp = tail;
tail = tail.prev;
tail.next = null;
return;
}
System.out.print("List is Empty");
}
void display()
{
if (!isEmpty())
{
DQueNode temp = head;
while (temp != null)
{
System.out.print(temp.value + " ");
temp = temp.next;
}
return;
}
System.out.print("List is Empty");
}
}
static class Stack
{
deque d = new deque();
public void push(int element)
{
d.insert_last(element);
}
public int size()
{
return d.size();
}
public void pop()
{
d.remove_last();
}
public void display()
{
d.display();
}
}
static class Queue
{
deque d = new deque();
public void enqueue(int element)
{
d.insert_last(element);
}
public void dequeue()
{
d.remove_first();
}
public void display()
{
d.display();
}
public int size()
{
return d.size();
}
}
public static void main(String[] args)
{
Stack stk = new Stack();
stk.push(7);
stk.push(14);
System.out.print("Stack: ");
stk.display();
System.out.println();
stk.pop();
System.out.print("Stack: ");
stk.display();
System.out.println();
Queue que = new Queue();
que.enqueue(12);
que.enqueue(24);
System.out.print("Queue: ");
que.display();
System.out.println();
que.dequeue();
System.out.print("Queue: ");
que.display();
System.out.println();
System.out.println("Size of stack is " +
stk.size());
System.out.println("Size of queue is " +
que.size());
}
}
So, in this blog, we have tried to explain how to Implement Stack Queue using Deque. If you want to strengthen your basic data structures knowledge feel free to check Foundation Courses at Prepbytes.