Dequeue DS Flashcards
Application of dequeue data structure
What is a dequeue in cpp STL ?
Deque or Doubly ended queues are sequence containers with the feature of expansion and contraction on both the ends.
How dequeue is different from stacks and queue ?
Unlike, Queues or Stacks, Deques allows us to perform insertion and deletion at both ends.
How dequeue in implemented in cpp STL and what extra features it provides ?
Deques are generally implemented using doubly-linked lists. But in C++ STL, Deques has some additional features:
It allows performing random access.
It allows performing arbitrary insertions in constant time.
What is the systax for deque ?
deque deque_name;
Write a simple program to create a dequeue
push_front(): This function is used to push elements into a deque from the front.
push_back(): This function is used to push elements into a deque from the back.
front() and back(): front() function is used to reference the first element of the deque container. back() function is used to reference the last element of the deque container.
Below program illustrate the creation of Deque and implementation of the above functions:
#include #include
using namespace std;
int main()
{
// Creates an empty Deque
deque dq;
// Push element at back
dq.push_back(10);
// Push element at front
dq.push_front(20);
// The Deque is: 20 10 // Access front and back elements // of the Deque cout << "dq.front() : " << dq.front(); cout << "\ndq.back() : " << dq.back(); return 0; }
Output:
dq. front() : 20
dq. back() : 10
Problem: Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.
Examples :
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6
Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90
Solution (A O(n) method: using Deque): We create a Deque, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in the current window and is greater than all other elements on the left side of it in the current window. We process all array elements one by one and maintain Qi to contain useful elements of the current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
#include #include
using namespace std;
// A Dequeue (Double ended queue) based method for
// printing maximum element of all subarrays of size k
void printKMax(int arr[], int n, int k)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
std::deque Qi(k);
/* Process first k (or first window) elements of array */
int i;
for (i = 0; i < k; ++i) {
// For every element, the previous smaller
// elements are useless so remove them from Qi
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements, i.e.,
// from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the
// largest element of previous window, so print it
cout << arr[Qi.front()] << " ";
// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front(); // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element of last window
cout << arr[Qi.front()];
}
// Driver Code
int main()
{
int arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k); return 0; }
Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of the array is added and removed at most once. So there are total 2*n operations.
Auxiliary Space: O(k)
Below image is a dry run of the above approach:
Given a Deque Deq containing N elements, the task is to traverse the Deq and print the elements of it.
Example 1:
Input:
5
1 2 3 4 5
Output:
1 2 3 4 5
Explanation:
Dqe will look like
{1, 2, 3, 4, 5}.
Example 2:
Input:
1
1
Output:
1
Explanation:
Dqe will look like {1}.
Your task: You don’t have to worry about the input. You just have to complete the function printDequeue() which takes a dequeue as an input parameter and prints all elements of it.
Note: For multiple test cases, the output needs to be printed on different lines.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
void printDeque(deque Deq)
{
// your code here
while(Deq.empty() == false) {
cout << Deq.front() << " ";
Deq.pop_front();
}
cout << endl;
}Given an array arr[] of size N containing non-negative integers. You need to insert all elements of the array to deque and return it.
Example 1:
Input:
5
1 2 3 4 5
Output:
1 2 3 4 5
Explanation:
After insert in the deque
it will look like {1, 2, 3, 4, 5}.
Example 2:
Input:
1
1
Output:
1
Explanation:
After insert in the deque
it will look like {1}.
Your Task:
You need to complete the function deque_Init() which takes array arr[] and it's size N as input parameters and should return deque that contains array elements. You don't have to worry about input.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
class Solution {
public:
// Function to insert all elements of the array in deque.
deque deque_Init(int arr[], int n) {
// add your code here
deque dq;
for (int i = 0; i < n; i++) {
dq.push_back(arr[i]);
}
return dq;
}
};Given a Deque dqe of size N containing non-negative integers.
Complete below functions depending type of query as mentioned and provided to you (indexing starts from 0):
1. eraseAt(X): this function should remove the element from specified position X in deque.
2. eraseInRange(start, end): this function should remove the elements in range start (inclusive), end (exclusive) specified in the argument of the function.
Note: If start is equal to end then simply return.
3. eraseAll(): remove all the elements from the deque.
Example 1:
Input:
5
1 2 4 5 6
1 2
Output:
1 2 5 6
Explanation: Here the query type is 1 and the position is 2. So we remove element at position 2. The element at position 2 is 1 2 4 5 6. So, we remove 4 and get 1 2 5 6. Example 2:
Input:
4
1 2 3 4
2 1 3
Output:
1 4
Explanation: Here the query type is 2 and the range is [1, 3). So we need to delete 1 2 3 4. Remember that end is exclusive. So the updated dequeue is 1 4. Example 3:
Input:
3
1 2 3
3
Output:
Empty
Explanation:
Here the query is of type 3
so we remove all the elements of dequeue.
Your Task:
Complete the functions eraseAt() which takes dequeue and a postion as input parameters, eraseInRange() which takes dequeue, start(inclusive) and end(exclusive) as input parameters and eraseAll() which takes a dequeue as input parameter.
Expected Time Complexity: O(N), for all operations
Expected Auxilliary Space: O(1)
void eraseAt(deque &deq, int X)
{
// your code here
deq.erase(deq.begin() + X);
}
//Function to erase the elements in range start (inclusive), end (exclusive).
void eraseInRange(deque &deq, int start, int end)
{
// your code here
deq.erase(deq.begin() + start, deq.begin() + end);
}
//Function to erase all the elements in the deque.
void eraseAll(deque &deq)
{
// your code here
deq.clear();
}
Given a Deque deq of size N containing non-negative integers and a positive integer K, the task is to rotate elements of the deque by K places in a circular fashion. There will be two rotations which you have to implement depending on the type rotating query. Below is the description of rotating type and value of K for which you have to rotate in circular way:
Type-1. right_Rotate_Deq_ByK(): this function should rotate deque by K places in a clockwise fashion.
Type-2. left_Rotate_Deq_ByK(): this function should rotate deque by K places in an anti-clockwise fashion.
Example 1:
Input:
6
1 2 3 4 5 6
1 2
Output:
5 6 1 2 3 4
Explanation: The dequeue is 1 2 3 4 5 6. The query type is 1 and k is 2. So, we need to right rotate dequeue by 2 times. In 1 right rotation we get 6 1 2 3 4 5. In another we get 5 6 1 2 3 4. Example 2:
Input:
6
1 2 3 4 5 6
2 2
Output:
3 4 5 6 1 2
Explanation: The dequeue is 1 2 3 4 5 6. The query type is 2 and k is 2. So, we need to left rotate dequeue by 2 times. In 1 left rotation we get 2 3 4 5 6 1. In another we get 3 4 5 6 1 2. Your Task: Since this is a functional problem you don't have to worry about the input. You just have to complete the functions right_Rotate_Deq_ByK() and left_Rotate_Deq_ByK() takes dequeue, size of dequeue, and a value K as input parameters and perform the operations. The functions are of a void type so don't return anything. The updated deque will be printed by the driver code.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
void left_Rotate_Deq_ByK(deque &deq, int n, int k)
{
// your code here
int a;
while(k>0) {
a = deq.front();
deq.pop_front();
deq.push_back(a);
k--; } }
//Function to rotate deque by k places in clockwise direction.
void right_Rotate_Deq_ByK(deque &deq, int n, int k)
{
// your code here
int a;
while(k > 0) {
a = deq.back();
deq.pop_back();
deq.push_front(a);
k--;
}
}
