StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Wednesday, June 1, 2011

C++ Deque

 June 01, 2011     Data Structures     No comments   

In this article, we will explore the concepts around Deque data structure. We will also write some simple implementation of Deque.

Deque Introduction

  1. Deque is an abbreviation for double-ended queue.
  2. It is a data structure in which the elements can only be added or removed from front and back of the queue.
  3. A typical deque implementation support the following operations. Insert at front an element, insert at back an element, remove from back an element, remove from front an element, list the front element and list the back element.
  4. Simple method of implementing a deque is using a doubly linked list.
  5. The time complexity of all the deque operations using a doubly linked list can be achieced O(1).
  6. A general purpose deque implementation can be used to mimic specialized behaviors like stacks and queues.
  7. For example to use deque as a stack. Insert at back an element (Push) and Remove at back an element (Pop) can behave as a stack.
  8. For example to use deque as a queue. Insert at back an element (Enqueue) and Remove at front an element (Dequeue) can behave as a queue.
  9. Deque is also supported in C++ Standard Template Library.

Deque Implementation

EXAMPLE:- Implement a deque using doubly linked lists.

#include <iostream>
using namespace std;

class DequeEmptyException
{
public:
    DequeEmptyException()
    {
        cout << "Deque empty" << endl;
    }
};

// Each node in a doubly linked list
class Node
{
public:
    int data;
    Node* next;
    Node* prev;
};

class Deque
{  
private:
    Node* front;
    Node* rear;
    int count;

public:
    Deque()
    {
        front = NULL;
        rear = NULL;
        count = 0;
    }      
  
    void InsertFront(int element)
    {
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Prepend to the list and fix links
            tmp->next = front;
            front->prev = tmp;
            front = tmp;
        }

        count++;
    }

    int RemoveFront()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the front node
        int ret = front->data;

        // Delete the front node and fix the links
        Node* tmp = front;
        if ( front->next != NULL )
        {
            front = front->next;
            front->prev = NULL;
        }
        else
        {
            front = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }

    void InsertBack(int element)
    {          
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Append to the list and fix links
            rear->next = tmp;
            tmp->prev = rear;
            rear = tmp;
        }

        count++;
    }

    int RemoveBack()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the rear node
        int ret = rear->data;

        // Delete the front node and fix the links
        Node* tmp = rear;
        if ( rear->prev != NULL )
        {
            rear = rear->prev;
            rear->next = NULL;
        }
        else
        {
            rear = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }
  
    int Front()
    {          
        if ( isEmpty() )
            throw new DequeEmptyException();

        return front->data;
    }

    int Back()
    {
        if ( isEmpty() )
            throw new DequeEmptyException();

        return rear->data;
    }
  
    int Size()
    {
        return count;
    }

    bool isEmpty()
    {
        return count == 0 ? true : false;
    }
};

int main()
{      
    // Stack behavior using a general dequeue
    Deque q;
    try {
        if ( q.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.InsertBack(100);
        q.InsertBack(200);
        q.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q.Size() << endl;

        // Pop elements
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a general dequeue
    Deque q1;
    try {
        if ( q1.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.InsertBack(100);
        q1.InsertBack(200);
        q1.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q1.Size() << endl;

        // Pop elements
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:
Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300

EXAMPLE:- Using the STL deque

#include <iostream>
#include <deque>
using namespace std;

int main()
{
    // Stack behavior using a STL deque
    deque<int> q;
    try {
        if ( q.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.push_back(100);
        q.push_back(200);
        q.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q.size() << endl;

        // Pop elements
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a STL deque
    deque<int> q1;
    try {
        if ( q1.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.push_back(100);
        q1.push_back(200);
        q1.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q1.size() << endl;

        // Pop elements
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}
OUTPUT:-
Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk