Open In App

Implement Stack and Queue using Deque

Last Updated : 17 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Deque also known as double ended queue, as name suggests is a special kind of queue in which insertions and deletions can be done at the last as well as at the beginning.

A link-list representation of deque is such that each node points to the next node as well as the previous node. So that insertion and deletions take constant time at both the beginning and the last.

Now, deque can be used to implement a stack and queue. One simply needs to understand how deque can made to work as a stack or a queue.

The functions of deque to tweak them to work as stack and queue are list below.

Examples: Stack 

Input : Stack : 1 2 3
Push(4)
Output : Stack : 1 2 3 4

Input : Stack : 1 2 3
Pop()
Output : Stack : 1 2


Examples: Queue 

Input: Queue : 1 2 3
Enqueue(4)
Output: Queue : 1 2 3 4

Input: Queue : 1 2 3
Dequeue()
Output: Queue : 2 3

Implementation:

Java
// Java program to implement stack and
// queue using Deque
import java.lang.*;

class GFG {

    // Class for a node of deque
    static class DQueNode {
        int value;
        DQueNode next;
        DQueNode prev;
    }

    // Implementation of deque class
    static class deque {

        // Pointers to head and tail of deque
        private DQueNode head;
        private DQueNode tail;

        // Constructor
        public deque() { head = tail = null; }

        // If list is empty
        boolean isEmpty()
        {
            if (head == null)
                return true;

            return false;
        }

        // count the number of nodes in list
        int size()
        {

            // If list is not empty
            if (!isEmpty()) {
                DQueNode temp = head;
                int len = 0;

                while (temp != null) {
                    len++;
                    temp = temp.next;
                }
                return len;
            }
            return 0;
        }

        // Insert at the first position
        void insert_first(int element)
        {

            // Allocating node of DQueNode type
            DQueNode temp = new DQueNode();
            temp.value = element;

            // If the element is first element
            if (head == null) {
                head = tail = temp;
                temp.next = temp.prev = null;
            }
            else {
                head.prev = temp;
                temp.next = head;
                temp.prev = null;
                head = temp;
            }
        }

        // Insert at last position of deque
        void insert_last(int element)
        {

            // Allocating node of DQueNode type
            DQueNode temp = new DQueNode();
            temp.value = element;

            // If element is the first element
            if (head == null) {
                head = tail = temp;
                temp.next = temp.prev = null;
            }
            else {
                tail.next = temp;
                temp.next = null;
                temp.prev = tail;
                tail = temp;
            }
        }

        // Remove element at the first position
    public void remove_first()
    {
    // If list is not empty
    if (!isEmpty()) {
        // If there is only one node
        if (head == tail) {
            head = tail = null;
            return;
        } else {
            head = head.next;
            head.prev = null;
        }
    } else {
        System.out.println("List is Empty");
        }
    }


        // Remove element at the last position
        void remove_last()
        {

            // If list is not empty
            if (!isEmpty()) {
                DQueNode temp = tail;
                tail = tail.prev;
                if (tail != null) {
                    tail.next = null;
                }
                return;
            }
            System.out.print("List is Empty");
        }

        // Displays the elements in deque
        void display()
        {

            // If list is not empty
            if (!isEmpty()) {
                DQueNode temp = head;

                while (temp != null) {
                    System.out.print(temp.value + " ");
                    temp = temp.next;
                }

                return;
            }
            System.out.print("List is Empty");
        }
    }

    // Class to implement stack using Deque
    static class Stack {
        deque d = new deque();

        // push to push element at top of stack
        // using insert at last function of deque
        public void push(int element)
        {
            d.insert_last(element);
        }

        // Returns size
        public int size() { return d.size(); }

        // pop to remove element at top of stack
        // using remove at last function of deque
        public void pop() { d.remove_last(); }

        // Display
        public void display() { d.display(); }
    }

    // Class to implement queue using deque
    static class Queue {
        deque d = new deque();

        // enqueue to insert element at last
        // using insert at last function of deque
        public void enqueue(int element)
        {
            d.insert_last(element);
        }

        // dequeue to remove element from first
        // using remove at first function of deque
        public void dequeue() { d.remove_first(); }

        // display
        public void display() { d.display(); }

        // size
        public int size() { return d.size(); }
    }

    // Driver Code
    public static void main(String[] args)
    {

        // Object of Stack
        Stack stk = new Stack();

        // push 7 and 8 at top of stack
        stk.push(7);
        stk.push(8);
        System.out.print("Stack: ");
        stk.display();

        // For new line
        System.out.println();

        // pop an element
        stk.pop();
        System.out.print("Stack: ");
        stk.display();

        // For new line
        System.out.println();

        // Object of Queue
        Queue que = new Queue();

        // Insert 12 and 13 in queue
        que.enqueue(12);
        que.enqueue(13);
        System.out.print("Queue: ");
        que.display();

        // New line
        System.out.println();

        // Delete an element from queue
        que.dequeue();
        System.out.print("Queue: ");
        que.display();

        // New line
        System.out.println();
        System.out.println("Size of stack is "
                           + stk.size());
        System.out.println("Size of queue is "
                           + que.size());
    }
}

// This code is contributed by sujitmeshram
// This code is modified by Susobhan Akhuli
// This code is modified by K.Harichandana
Python3
class node:
    def __init__(self,val):
        self.val = val
        self.prev = None
        self.next = None
    
class Deque:
    def __init__(self):
        self.head = self.tail = None
    
    def isEmpty(self):
        if (self.head == None): return True
        return False
    
    def insert_first(self,element):
        newP = node(element)
        if self.head == None: 
            self.head = self.tail = newP
            return
        newP.next = self.head
        self.head.prev = newP
        self.head = newP
    
    def insert_last(self,element):
        newP = node(element)
        if self.head == None: 
            self.head = self.tail = newP
            return
        newP.prev = self.tail
        self.tail.next = newP
        self.tail = newP
        
    def size(self):
        curr = self.head
        len = 0
        while curr != None:
            len += 1
            curr = curr.next
        return len
        
    def remove_first(self):
        if self.isEmpty(): 
            print('List is Empty')
            return
        self.head = self.head.next
        if self.head != None: self.head.prev = None
        
    def remove_last(self):
        if self.isEmpty():
            print('List is Empty')
            return
        self.tail =  self.tail.prev
        if self.tail != None: self.tail.next = None
        
    def display(self):
        if self.isEmpty():
            print('List is Empty')
            return
        curr = self.head
        while curr != None:
            print(curr.val,end = ' ')
            curr = curr.next
        print()
            
class Stack:
    def __init__(self):
        self.stack = Deque()
    
    def push(self,element):
        self.stack.insert_last(element)
    
    def pop(self):
        self.stack.remove_last()
        
    def size(self):
        return self.stack.size()
    
    def display(self):
        self.stack.display()
        
class Queue:
    def __init__(self):
        self.que = Deque()
    
    def enqueue(self,element):
        self.que.insert_last(element)
    
    def dequeue(self):
        self.que.remove_first()
        
    def size(self):
        return self.que.size()
        
    def display(self):
        self.que.display()
            
            
stk = Stack() 

 # push 7 and 8 at top of stack
stk.push(7) 
stk.push(8) 
print("Stack: ") 
stk.display() 

 # pop an element
stk.pop() 
print("Stack: ") 
stk.display() 

 # Object of Queue
que = Queue() 

 # Insert 12 and 13 in queue
que.enqueue(12) 
que.enqueue(13) 
print("Queue: ") 
que.display() 

 # Delete an element from queue
que.dequeue() 
print("Queue: ") 
que.display() 

print("Size of stack is ",stk.size()) 
print("Size of queue is ", que.size()) 
C#
// C# program to implement stack and
// queue using Deque
using System;
class GFG
{

    // Class for a node of deque
    public

        class DQueNode {
        public

            int value;
        public
            DQueNode next;
        public
            DQueNode prev;
    }

    // Implementation of deque class
    public class deque {

        // Pointers to head and tail of deque
        private DQueNode head;
        private DQueNode tail;

        // Constructor
        public deque() { head = tail = null; }

        // If list is empty
        public

            bool
            isEmpty()
        {
            if (head == null)
                return true;

            return false;
        }

        // count the number of nodes in list
        public

            int
            size()
        {

            // If list is not empty
            if (!isEmpty()) {
                DQueNode temp = head;
                int len = 0;

                while (temp != null) {
                    len++;
                    temp = temp.next;
                }
                return len;
            }
            return 0;
        }

        // Insert at the first position
        public

            void
            insert_first(int element)
        {

            // Allocating node of DQueNode type
            DQueNode temp = new DQueNode();
            temp.value = element;

            // If the element is first element
            if (head == null) {
                head = tail = temp;
                temp.next = temp.prev = null;
            }
            else {
                head.prev = temp;
                temp.next = head;
                temp.prev = null;
                head = temp;
            }
        }

        // Insert at last position of deque
        public

            void
            insert_last(int element)
        {

            // Allocating node of DQueNode type
            DQueNode temp = new DQueNode();
            temp.value = element;

            // If element is the first element
            if (head == null) {
                head = tail = temp;
                temp.next = temp.prev = null;
            }
            else {
                tail.next = temp;
                temp.next = null;
                temp.prev = tail;
                tail = temp;
            }
        }

        // Remove element at the first position
        public

            void
            remove_first()
        {

            // If list is not empty
            if (!isEmpty()) {
                head = head.next;
                head.prev = null;

                return;
            }
            Console.Write("List is Empty");
        }

        // Remove element at the last position
        public

            void
            remove_last()
        {

            // If list is not empty
            if (!isEmpty()) {
                tail = tail.prev;
                tail.next = null;

                return;
            }
            Console.Write("List is Empty");
        }

        // Displays the elements in deque
        public

            void
            display()
        {

            // If list is not empty
            if (!isEmpty()) {
                DQueNode temp = head;

                while (temp != null) {
                    Console.Write(temp.value + " ");
                    temp = temp.next;
                }

                return;
            }
            Console.Write("List is Empty");
        }
    }

    // Class to implement stack using Deque
    public class Stack {
        deque d = new deque();

        // push to push element at top of stack
        // using insert at last function of deque
        public void push(int element)
        {
            d.insert_last(element);
        }

        // Returns size
        public int size() { return d.size(); }

        // pop to remove element at top of stack
        // using remove at last function of deque
        public void pop() { d.remove_last(); }

        // Display
        public void display() { d.display(); }
    }

    // Class to implement queue using deque
    class Queue {
        deque d = new deque();

        // enqueue to insert element at last
        // using insert at last function of deque
        public void enqueue(int element)
        {
            d.insert_last(element);
        }

        // dequeue to remove element from first
        // using remove at first function of deque
        public void dequeue() { d.remove_first(); }

        // display
        public void display() { d.display(); }

        // size
        public int size() { return d.size(); }
    }

    // Driver Code
    public static void Main(String[] args)
    {

        // Object of Stack
        Stack stk = new Stack();

        // push 7 and 8 at top of stack
        stk.push(7);
        stk.push(8);
        Console.Write("Stack: ");
        stk.display();

        // For new line
        Console.WriteLine();

        // pop an element
        stk.pop();
        Console.Write("Stack: ");
        stk.display();

        // For new line
        Console.WriteLine();

        // Object of Queue
        Queue que = new Queue();

        // Insert 12 and 13 in queue
        que.enqueue(12);
        que.enqueue(13);
        Console.Write("Queue: ");
        que.display();

        // New line
        Console.WriteLine();

        // Delete an element from queue
        que.dequeue();
        Console.Write("Queue: ");
        que.display();

        // New line
        Console.WriteLine();
        Console.WriteLine("Size of stack is " + stk.size());
        Console.WriteLine("Size of queue is " + que.size());
    }
}

// This code contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement stack and
// queue using Deque

// Class for a node of deque
class DQueNode
{
    constructor()
    {
        this.value = 0;
         this.next = null;
        this.prev = null;
    }
}

// Implementation of deque class
class deque
{
     // Constructor
    constructor()
    {
        this.head = this.tail=null;
    }
    
    // If list is empty
    isEmpty()
    {
        if (this.head == null)
            return true;
             
        return false;
    }
    
    // count the number of nodes in list
    size()
    {
        // If list is not empty
        if (!this.isEmpty())
        {
            let temp = this.head;
            let len = 0;
             
            while (temp != null)
            {
                len++;
                temp = temp.next;
            }
            return len;
        }
        return 0;
    }
    
    // Insert at the first position
    insert_first(element)
    {
    
        // Allocating node of DQueNode type
        let temp = new DQueNode();
        temp.value = element;
 
        // If the element is first element
        if (this.head == null)
        {
            this.head = this.tail = temp;
            temp.next = temp.prev = null;
        }
        else
        {
            this.head.prev = temp;
            temp.next = this.head;
            temp.prev = null;
            this.head = temp;
        }
    }
    
    // Insert at last position of deque
    insert_last(element)
    {
        // Allocating node of DQueNode type
        let temp = new DQueNode();
        temp.value = element;
 
        // If element is the first element
        if (this.head == null)
        {
            this.head = this.tail = temp;
            temp.next = temp.prev = null;
        }
        else
        {
            this.tail.next = temp;
            temp.next = null;
            temp.prev = this.tail;
            this.tail = temp;
        }
    }
    
    // Remove element at the first position
    remove_first()
    {
    
        // If list is not empty
        if (!this.isEmpty())
        {
            let temp = this.head;
            this.head = this.head.next;
            this.head.prev = null;
 
            return;
        }
        document.write("List is Empty");
    }
    
    // Remove element at the last position
    remove_last()
    {
        // If list is not empty
        if (!this.isEmpty())
        {
            let temp = this.tail;
            this.tail = this.tail.prev;
            this.tail.next = null;
 
            return;
        }
        document.write("List is Empty");
    }
    
    // Displays the elements in deque
    display()
    {
        // If list is not empty
        if (!this.isEmpty())
        {
            let temp = this.head;
             
            while (temp != null)
            {
                document.write(temp.value + " ");
                temp = temp.next;
            }
 
            return;
        }
        document.write("List is Empty");
    }
}

// Class to implement stack using Deque
class Stack
{
    constructor()
    {
        this.d= new deque();    
    }
    
    
    // push to push element at top of stack
    // using insert at last function of deque
    push(element)
    {
        this.d.insert_last(element);
    }
    
    // Returns size
    size()
    {
        return this.d.size();
    }
    
    // pop to remove element at top of stack
    // using remove at last function of deque
    pop()
    {
        this.d.remove_last();
    }
    
    // Display
    display()
    {
        this.d.display();
    }
}

// Class to implement queue using deque
class Queue
{
    constructor()
    {
        this.d = new deque();
    }
    // enqueue to insert element at last
    // using insert at last function of deque
    enqueue(element)
    {
        this.d.insert_last(element);
    }
    
    // dequeue to remove element from first
    // using remove at first function of deque
    dequeue()
    {
        this.d.remove_first();
    }
    
    // display
    display()
    {
        this.d.display();
    }
    
    // size
    size()
    {
        return this.d.size();
    }
}

// Driver Code
// Object of Stack
let stk = new Stack();

// push 7 and 8 at top of stack
stk.push(7);
stk.push(8);
document.write("Stack: ");
stk.display();

// For new line
document.write("<br>");

// pop an element
stk.pop();
document.write("Stack: ");
stk.display();

// For new line
document.write("<br>");

// Object of Queue
let que = new Queue();

// Insert 12 and 13 in queue
que.enqueue(12);
que.enqueue(13);
document.write("Queue: ");
que.display();

// New line
document.write("<br>");

// Delete an element from queue
que.dequeue();
document.write("Queue: ");
que.display();

// New line
document.write("<br>");
document.write("Size of stack is " +
                   stk.size()+"<br>");
document.write("Size of queue is " +
                   que.size()+"<br>");

// This code is contributed by patel2127
</script>
C++14
// C++ Program to implement stack and queue using Deque
#include <bits/stdc++.h>
using namespace std;

// structure for a node of deque
struct DQueNode {
    int value;
    DQueNode* next;
    DQueNode* prev;
};

// Implementation of deque class
class Deque {
private:

    // pointers to head and tail of deque
    DQueNode* head;
    DQueNode* tail;

public:
    // constructor
    Deque()
    {
        head = tail = NULL;
    }

    // if list is empty
    bool isEmpty()
    {
        if (head == NULL)
            return true;
        return false;
    }

    // count the number of nodes in list
    int size()
    {
        // if list is not empty
        if (!isEmpty()) {
            DQueNode* temp = head;
            int len = 0;
            while (temp != NULL) {
                len++;
                temp = temp->next;
            }
            return len;
        }
        return 0;
    }

    // insert at the first position
    void insert_first(int element)
    {
        // allocating node of DQueNode type
        DQueNode* temp = new DQueNode[sizeof(DQueNode)];
        temp->value = element;

        // if the element is first element
        if (head == NULL) {
            head = tail = temp;
            temp->next = temp->prev = NULL;
        }
        else {
            head->prev = temp;
            temp->next = head;
            temp->prev = NULL;
            head = temp;
        }
    }

    // insert at last position of deque
    void insert_last(int element)
    {
        // allocating node of DQueNode type
        DQueNode* temp = new DQueNode[sizeof(DQueNode)];
        temp->value = element;

        // if element is the first element
        if (head == NULL) {
            head = tail = temp;
            temp->next = temp->prev = NULL;
        }
        else {
            tail->next = temp;
            temp->next = NULL;
            temp->prev = tail;
            tail = temp;
        }
    }

    // remove element at the first position
    void remove_first()
    {
        // if list is not empty
        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;
    }

    // remove element at the last position
    void remove_last()
    {
        // if list is not empty
        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;
    }

    // displays the elements in deque
    void display()
    {
        // if list is not empty
        if (!isEmpty()) {
            DQueNode* temp = head;
            while (temp != NULL) {
                cout << temp->value << " ";
                temp = temp->next;
            }
            cout << endl;
            return;
        }
        cout << "List is Empty" << endl;
    }
};

// Class to implement stack using Deque
class Stack : public Deque {
public:
    // push to push element at top of stack
    // using insert at last function of deque
    void push(int element)
    {
        insert_last(element);
    }

    // pop to remove element at top of stack
    // using remove at last function of deque
    void pop()
    {
        remove_last();
    }
};

// class to implement queue using deque
class Queue : public Deque {
public:
    // enqueue to insert element at last
    // using insert at last function of deque
    void enqueue(int element)
    {
        insert_last(element);
    }

    // dequeue to remove element from first
    // using remove at first function of deque
    void dequeue()
    {
        remove_first();
    }
};

// Driver Code
int main()
{
    // object of Stack
    Stack stk;

    // push 7 and 8 at top of stack
    stk.push(7);
    stk.push(8);
    cout << "Stack: ";
    stk.display();

    // pop an element
    stk.pop();
    cout << "Stack: ";
    stk.display();

    // object of Queue
    Queue que;

    // insert 12 and 13 in queue
    que.enqueue(12);
    que.enqueue(13);
    cout << "Queue: ";
    que.display();

    // delete an element from queue
    que.dequeue();
    cout << "Queue: ";
    que.display();

    cout << "Size of Stack is " << stk.size() << endl;
    cout << "Size of Queue is " << que.size() << endl;
    return 0;
}

Output
Stack: 7 8 
Stack: 7 
Queue: 12 13 
Queue: 13 
Size of Stack is 1
Size of Queue is 1

Time Complexity: O(n)
Auxiliary Space: O(n)



Previous Article
Next Article

Similar Reads

Difference between Queue and Deque (Queue vs. Deque)
Queue: The queue is an abstract data type or linear data structure from which elements can be inserted at the rear(back) of the queue and elements can be deleted from the front(head) of the queue. The operations allowed in the queue are:insert an element at the reardelete element from the frontget the last elementget the first elementcheck the size
3 min read
Should we declare as Queue or Priority Queue while using Priority Queue in Java?
Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are
3 min read
Stack and Queue in Python using queue Module
A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.
3 min read
deque::at() and deque::swap() in C++ STL
Deque or Double ended queues are sequence containers with the feature of expansion and contraction on both the ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also the beginning. Unlike vectors, contiguous storage allocation may not be guaranteed. deque::at()at() function is us
4 min read
deque::clear() and deque::erase() in C++ STL
Deque or Double-ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors, but are more efficient in the case of insertion and deletion of elements at the end, and also at the beginning. Unlike vectors, contiguous storage allocation may not be guaranteed. deque::clear() The clear()
5 min read
deque::operator= and deque::operator[] in C++ STL
Deque or Double ended queues are sequence containers with the feature of expansion and contraction on both the ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also the beginning. Unlike vectors, contiguous storage allocation may not be guaranteed. deque::operator= This operator
4 min read
Deque::front() and deque::back() in C++ STL
Deque or Double Ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements at the end, and also at the beginning. Unlike vectors, contiguous storage allocation may not be guaranteed in the deque. deque::front()fron
4 min read
Check if a queue can be sorted into another queue using a stack
Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp
9 min read
How to implement Stack and Queue using ArrayDeque in Java
ArrayDeque in Java The ArrayDeque in Java provides a way to apply resizable-array in addition to the implementation of the Deque interface. It is also known as Array Double Ended Queue or Array Deck. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue. ArrayDeque class implements Queu
6 min read
Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm?
What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca
2 min read
Article Tags :
Practice Tags :