# Implement Stack and Queue using Deque  Difficulty Level Easy
Frequently asked in Fanatics GE Healthcare MAQ Myntra Qualcomm
Dequeue Queue Stack

## Problem Statement  The problem “Implement Stack and Queue using Deque” states to write an algorithm to implement Stack and Queue using a Deque(Doubly Ended Queue).

## Example (Stack)  ```Push(1)
Push(2)
Push(3)
Pop()
isEmpty()
Pop()
Size()```
```3
false
2
1```

## Example (Queue)  ```Enqueue(1)
Enqueue(2)
Enqueue(3)
Dequeue
isEmpty()
Size()
Dequeue()```
```1
false
2
2```

## Algorithm  A deque(Doubly Ended Queue) is a special type of queue in which insertion and deletion can be performed on both the ends. This interesting property of Deque can be used to implement either a stack or a queue from it.
The image below shows a Deque, ### Stack

Stack is a Last In First Out(LIFO) data structure, that is, the elements are popped out from the same side where they are pushed. Let us use the front of Deque to perform push and pop operation for stack.

#### Push(x)

To push an element x to the stack, simply add the element x at the front of Deque.

Time Complexity = O(1)

#### Pop()

Pop operation happen on the same side as of Push, that is, to pop an element from stack delete the element present on the front of deque and return it.

Sorting a Queue without Extra Space

Time Complexity = O(1)

#### isEmpty()

If the Deque is empty the stack is empty else it is not. So return the isEmpty of Deque.

Time Complexity = O(1)

#### size()

The size of stack is same as the size of Deque, so return the size of deque.

Time Complexity = O(1)

#### Code

##### JAVA Code to implement stack using deque
```import java.util.Deque;
class StackUsingDeque {
// deque used to implement stack
private static Deque<Integer> deque;

private static void push(int x) {
// Add the element x to the front of Deque
}

private static int pop() {
// if deque is not empty remove an element from the front of deque
if (!deque.isEmpty()) {
return deque.removeFirst();
}
return -1;
}

private static boolean isEmpty() {
// stack is empty if deque is empty
return deque.isEmpty();
}

private static int size() {
// size of stack is same as size of Deque
return deque.size();
}

public static void main(String[] args) {

// Example
push(1);
push(2);
push(3);
System.out.println(pop());
System.out.println(isEmpty());
System.out.println(pop());
System.out.println(size());
}
}```
```3
false
2
1```
##### C++ Code to implement stack using deque
```#include <bits/stdc++.h>
using namespace std;

// deque used to implement stack
deque<int> dq;

void push(int x) {
// Add the element x to the front of Deque
dq.push_front(x);
}

int pop() {
// if deque is not empty remove an element from the front of deque
if (!dq.empty()) {
int top = dq.front();
dq.pop_front();
}
return -1;
}

int size() {
// size of stack is same as size of Deque
return dq.size();
}

bool isEmpty() {
// stack is empty if deque is empty
return dq.empty();
}

int main() {
// Example
push(1);
push(2);
push(3);
cout<<pop()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
cout<<pop()<<endl;
cout<<size()<<endl;

return 0;
}```
```3
false
2
1```

### Queue

Queue is First In First Out(FIFO) data structure, that enqueue and dequeue operations are performed on opposite sides. Let us use the front of Deque for enqueue operation and rear of Deque for dequeue operation.

Minimum swaps required to bring all elements less than or equal to k together

#### Enqueue(x)

To enqueue an element x in the queue, simply add the element at the front of Deque.

Time Complexity = O(1)

#### Dequeue()

To dequeue an element from queue, remove the element at rear of Deque and return it.

Time Complexity = O(1)

#### isEmpty()

The queue is empty if the Deque is empty, else it is not. So return the isEmpty of Deque.

Time Complexity = O(1)

#### size()

The size of queue is same as the size of Deque, so return the size of deque.

Time Complexity = O(1)

#### Code

##### JAVA Code to implement queue using deque
```import java.util.Deque;
class QueueUsingDeque {
// deque used to implement queue
private static Deque<Integer> deque;

private static void enqueue(int x) {
// add the element x at the front of deque
}

private static int dequeue() {
// if deque is not empty remove and return the rear of deque
if (!deque.isEmpty()) {
return deque.removeLast();
}
return -1;
}

private static boolean isEmpty() {
// queue is empty if deque is empty
return deque.isEmpty();
}

private static int size() {
// size of queue is same as size of deque
return deque.size();
}

public static void main(String[] args) {

// Example
enqueue(1);
enqueue(2);
enqueue(3);
System.out.println(dequeue());
System.out.println(isEmpty());
System.out.println(size());
System.out.println(dequeue());
}
}```
```1
false
2
2```
##### C++ Code to implement queue using deque
```#include <bits/stdc++.h>
using namespace std;

// deque used to implement queue
deque<int> dq;

void enqueue(int x) {
// add the element x at the front of deque
dq.push_front(x);
}

int dequeue() {
// if deque is not empty remove and return the rear of deque
if (!dq.empty()) {
int front = dq.back();
dq.pop_back();
return front;
}
return -1;
}

int size() {
// size of queue is same as size of deque
return dq.size();
}

bool isEmpty() {
// queue is empty if deque is empty
return dq.empty();
}

int main() {
// Example
enqueue(1);
enqueue(2);
enqueue(3);
cout<<dequeue()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
cout<<size()<<endl;
cout<<dequeue()<<endl;

return 0;
}```
```1
false
2
2```