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;
}
You can also try this code with Online C++ Compiler
Output:
3 2 1
You can also try this code with Online C++ Compiler
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)
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;
}
You can also try this code with Online C++ Compiler
Output:
3 2 1
You can also try this code with Online C++ Compiler
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!
85+ registered