Implement Stack and Queue using Deque

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,

Implement Stack and Queue using 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.

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;
import java.util.LinkedList;
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
        deque.addFirst(x);
    }

    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) {
        deque = new LinkedList<>();

        // 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 top;
    }
    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.

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;
import java.util.LinkedList;
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
        deque.addFirst(x);
    }

    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) {
        deque = new LinkedList<>();

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