Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Medium

Design Front Middle Back Queue using STL

Author Rhythm Jain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Queue

Introduction

Design and Implementation based questions are increasingly becoming common in technical interviews. So here we are back again with a question based on the design of a unique type of data structure called Front, Middle, and Back Queue.

Let's proceed without any delay.

Problem Statement

Create a data structure that efficiently supports the following queue operations.

  • push_front_queue(x): Insert the element “x” at the front of the queue.
  • push_middle_queue(x): Insert the element “x” at the middle of the queue.
  • push_back_queue(x): Insert the element “x” at the back of the queue.
  • pop_front_queue(): If the queue is not empty, return the element at the front of the queue else return -1.
  • pop_middle_queue(): If the queue is not empty, return the element at the middle of the queue else return -1.
  • pop_back_queue(): If the queue is not empty, return the element at the back of the queue else return -1.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1: List

The above problem can be easily solved by using a single List in STL. The list is based on the Singly Linked List. We can implement the functions in the following way-

  • push_front_queue(x): Insert the element "x" at the front of the list using push_front() function of the list.
  • push_middle_queue(x): Using the advance() function of the list iterate over the list and then insert the element at the middle position of the list using the insert() function.
  • push_back_queue(x): Insert an element "x" at the rear of the list using push_back() function.
  • pop_front_queue(): If the size of the list is greater than zero then delete the front element of the list using pop_front() function else return -1.
  • pop_middle_queue(): If the size of the list is greater than zero then iterate to the middle element using advance() and delete the middle element using erase() function else return -1.
  • pop_back_queue(): If the size of the list is greater than zero then delete the last element of the list using pop_back() function else return -1.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

class Queue
{
    list<int> l;

public:
    //push element at front of the queue
    void push_front_queue(int val)
    {
        l.push_front(val);
    }

    // push element at middle of the queue
    void push_middle_queue(int val)
    {
        auto itr = l.begin();

        // Traverse the list
        advance(itr, l.size() / 2);

        // Insert element into middle of the list
        l.insert(itr, val);
    }

    // Insert an element at back of the queue
    void push_back_queue(int val)
    {
        l.push_back(val);
    }

    //pop element from front of the queue
    int pop_front_queue()
    {
        // Stores front element of queue
        int val = - 1;
        if (l.size())
        {
            val = l.front();
            l.pop_front();
        }
        return val;
    }

    //pop middle element of the queue
    int pop_middle_queue()
    {
        int val = - 1;
        if (l.size())
        {
            auto itr = l.begin();

            // Traverse the list
            advance(itr, (l.size() - 1) / 2);
            val = *itr;

            // Remove mid element from queue
            l.erase(itr);
        }
        return val;
    }

    //pop end element of the queue
    int pop_back_queue()
    {
        // Stores back element of the queue
        int val = - 1;
        if (l.size())
        {
            val = l.back();
            l.pop_back();
        }
        return val;
    }
};

// Drivers code

int main()
{
    Queue q;
    q.push_front_queue(1);
    q.push_back_queue(2);
    q.push_middle_queue(3);
    cout << q.pop_middle_queue() << " ";
    cout << q.pop_back_queue() << " ";
    cout << q.pop_front_queue() << " ";
    return 0;
}


Output:

3 2 1

Time Complexity Analysis

push_front_queue() : O(1)

push_middle_queue() : O(N)

push_back_queue(): O(1)

pop_front_queue(): O(1)

pop_middle_queue(): O(N)

pop_back_queue(): O(1)

Read More - Time Complexity of Sorting Algorithms

Approach 2: Deque

We can solve the problem using two Deque.

Double Ended or Deque Queue is an extended version of the Queue data structure that supports insert and delete operations at both ends.

We will use the following rules in order to maintain the efficiency of our queue.

  • Let the first and second deque be d1 and d2 respectively.
  • The operation in the rear of the queue should be performed at the end of the d2, and the operation in the center should be performed at the end of the d1.
  • If the size of d1 is greater than the size of d2, the element at end of d1 should be removed and added to the front of the d2.
  • If the size of d2 is greater than the size of d1, the element at front of d2 should be removed and added to the rear of the d1 only if the size of d2 exceeds the size of d1 by 

We can implement the functions in the following way-

  • push_front_queue(x): Insert the element "x" at the front of d1 using push_front() function.
  • push_middle_queue(x): Insert the element "x" at the end of the d1 using push_back() function.
  • push_back_queue(x): Insert an element x at the end of the d2 using push_back() function.
  • pop_front_queue(): Remove the front element of d1 if the size of d1 is greater than 0 otherwise if size of d2 is greater than 0 remove front element of d2 using pop_front(). Else if both d1 and d2 are empty then return -1.
  • pop_middle_queue(): If both d1 and d2 are empty then return -1. Else remove the end element of d1 if the size of d1 equals the size of d2 using pop_back() otherwise remove first element of d2 using pop_front().
  • pop_back_queue(): If both d1 and d2 are empty then return -1. Else remove the end element of d2 if the size of d2 is greater than 0 using pop_back().

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Create class Queue.
class Queue
{
    // Initialize two deques d1 and d2
    deque<int> d1, d2;
    //balance the size of d1 and d2 
    void equalizeSizedeque1deque2()
    {
        if (d1.size() <= d2.size())
            return;
        // Insert the last element of d1 into d2.
        d2.push_front(d1.back());
        // Pop the front element of the d1
        d1.pop_back();
    }
    // Function to balance the size of d2 and d1 
    void equalizeSizedeque2deque1()
    {
        // if size of d2 deceed the d1 by 1
        if (d2.size() <= d1.size() + 1)
            return;
        // Insert front element of d2 into the d1
        d1.push_back(d2.front());
        // Remove front element of d2
        d2.pop_front();
    }

public:
    //insert element at front of queue
    void push_front_queue(int val)
    {
        // Insert val into d1 
        d1.push_front(val);
        // Balancing the size of d2
        equalizeSizedeque1deque2();
    }
    //insert val into the middle of queue
    void push_middle_queue(int val)
    {
        // Insert val into d1 
        d1.push_back(val);
        // Balancing the size of d2
        equalizeSizedeque1deque2();
    }
    //insert val into back of queue
    void push_back_queue(int val)
    {
        // Insert val into d2 
        d2.push_back(val);
        // Balancing the size of d2
        equalizeSizedeque2deque1();
    }
    //pop front element from queue
    int pop_front_queue()
    {
        // If d1 and d2 is empty
        if (d1.empty() && d2.empty())
            return - 1;
        int ans;
        // If the d1 is empty
        if (d1.empty())
        {
            // Stores front element of d2
            ans = d2.front();
            // Pop front element of d2
            d2.pop_front();
        }
        else
        {
            // Stores front element of d1
            ans = d1.front();
            // Pop front element of d1
            d1.pop_front();
            // Balancing the size of d1
            equalizeSizedeque2deque1();
        }
        return ans;
    }
    //pop middle element of queue
    int pop_middle_queue()
    {
        // If both deques are empty
        if (d1.empty() && d2.empty())
            return - 1;
        // Stores mid element of queue
        int ans;
        // If size of both deque is equal
        if (d1.size() == d2.size())
        {
            // Stores back element of d1
            ans = d1.back();
            // Pop back element of d1
            d1.pop_back();
        }
        else
        {
            // Stores front element of d2
            ans = d2.front();
            // Pop front element from d2
            d2.pop_front();
        }
        return ans;
    }
    //pop back element from queue
    int pop_back_queue()
    {
        // If both the deque are empty
        if (d1.empty() && d2.empty())
            return - 1;
        // Stores back element from d2
        int ans = d2.back();
        // Pop back element from d2
        d2.pop_back();
        // Balancing the size of d2
        equalizeSizedeque1deque2();
        return ans;the 
    }
};
// Driver code

int main()
{
    Queue q;
    q.push_front_queue(1);
    q.push_back_queue(2);
    q.push_middle_queue(3);
    cout << q.pop_middle_queue() << " ";
    cout << q.pop_back_queue() << " ";
    cout << q.pop_front_queue() << " ";
    return 0;
}


Output:

3 2 1

Time Complexity Analysis

push_front_queue() : O(1)

push_middle_queue() : O(1)

push_back_queue(): O(1)

pop_front_queue(): O(1)

pop_middle_queue(): O(1)

pop_back_queue(): O(1)

 

Read about Application of Queue in Data Structure here.

Frequently Asked Questions

How can we implement a Deque?

Deque can be implemented either by a doubly linked list or by the dynamic array. Each has different time complexities and implementation.

What is the time complexity of operations in Deque implemented using Doubly Linked List?

The time complexity of all deque operations in a Doubly-linked list implementation of Deque is O(1). Furthermore, given an iterator, the time complexity of insertion or deletion in the middle is O(1). Random access by index, on the other hand, has an O(N) time complexity.

How a List can be implemented?

The List used here can be implemented as a Doubly Linked List since the forward and reverse iterators are used to traverse the list in both directions.

Conclusion

Design and application of various data structures are the most critical technical and coding interview concepts.

STL includes a number of data structures that are useful in a variety of situations. Many data structures are inspired by real-world applications. It's a container library with algorithms, iterators, and container classes. It is a parameterized library since it is a generic library.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Implement Dynamic Deque using Templates Class and a Circular Array
Next article
Implementation of Deque Using Doubly Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass