Design Front Middle Back Queue using STL

Rhythm Jain
Last Updated: May 13, 2022

Introduction

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

Lets 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 queue is not empty, returns the element at the front of the queue else return -1.
  • pop_middle_queue(): If queue is not empty, returns the element at the middle of the queue else return -1.
  • pop_back_queue(): If queue is not empty, returns the element at the back of the queue else return -1.

Approach 1: List

The above problem can be easily solved by using singly List in STL. 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): Ssing advance() function of the list iterate over the list and then insert the element at middle position of the list using 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)

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 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 centre 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 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 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 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;
    }
};
// 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)

Frequently Asked Questions

  1. How can we implement a Deque?
    Deque can be implimented either by a doubly linked list or by dynamic array.Each having different time complexities and implementation.
     
  2. What is time complexity of operations in Deque implimented 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.
     
  3. 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.

Key Takeaways

Design and application of various data structures are the most critical technical and coding interviews 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.

Was this article helpful ?
0 upvotes