home
Naukri Code 360
expand-more
Problem Details
expand-more
Special Queue
Last Updated: 26 Sep, 2021

Special Queue

Moderate
Asked in companies
AmazonD.E.Shaw
Solve now

Problem statement

Your task is to design a special type of Queue having three positions front, middle, and back to push or pop the element. You have to define a class having the following functions:

1. SPECIAL_QUEUE() is a function that initializes your queue.

2. PUSH_FRONT(VAL) inserts the VAL in the front of the queue.

3. PUSH_BACK(VAL) inserts the VAL at the back of the queue.

4. PUSH_MIDDLE(VAL) inserts the VAL at the middle position of the queue.

5. POP_FRONT(VAL) removes the first element from the queue and returns the value of the removed element.

6. POP_BACK(VAL) removes the last element from the queue and returns the value of the removed element.

7. POP_MIDDLE(VAL) removes the middle element from the queue and returns the value of the removed element.

Note:

If the queue is empty and any type of ‘POP’ function is called, return -1.
If there are two middle positions available, operate on the position close to the front of the queue.
For Example
If the functions calls are as follows:
‘PUSH_FRONT’(10).
‘PUSH_FRONT’(20)’.
‘PUSH_MIDDLE’(30)
‘POP_BACK’().
 So after each operation queue will changes like [ ] -> [10] -> [20, 10] -> [20, 30, 10] ->[20,30].
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of function calls.

The second line contains a list of ‘N’ function names.

The third line of each test case contains ‘N’ integers denoting the parameters passed in each function call. (Parameter value corresponding to  any pop() function is -1.)
Output Format:
For each test case, output the value of the popped element for each pop() function call in a separate line.
For push() function ,do not print anything.  

Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10000.
0 <= ‘VAL’ <= 10^6 .  

Time limit: 1 sec
Solve now

Approaches

01 Approach

In this approach, we will implement this special queue using a  simple dynamic array.

In push functions, we will shift the elements of the array and insert the new element.

In pop functions, we will remove the element from the specified position and update the array.

In these functions, we will use additional space to change the array according to the function.  


 

Algorithm:

  • Defining SPECIAL_QUEUE():
    • Declare a dynamic array ‘ARR’.
  • Defining PUSH_BACK(‘VAL’):
    • Append ‘VAL’ to the end of the ‘ARR’.
  • Defining PUSH_FRONT(‘VAL’):
    • Declare an array ‘TEMP’.
    • Insert ‘VAL’ into the ‘TEMP’.
    • For each element ‘i’ in the array ‘ARR’, do the following:
      • Insert ‘i’ into ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’.
  • Defining PUSH_MIDDLE(‘VAL’):
    • Declare an array ‘TEMP’.
    • Set ‘i’ as 0.
    • Set ‘j’ as  0.
    • Set ‘IDX’ as (length of ‘ARR’) / 2 . (Index where ‘VAL’ should be inserted.)
    • While ‘j’ is less than (length of ‘ARR’ +1):
      • If ‘j’ is equal to ‘IDX’:
        • Insert ‘VAL’ into ‘TEMP’.
      • Else:
        • Insert ‘ARR’[i] into ‘TEMP’.
        • Set ‘i’ as ‘i+1’.
      • Set ‘j’ as j+1.
    • Set ‘ARR’  as ‘TEMP’.
  • Defining POP_BACK():
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘V’ as ‘ARR’[length of ‘ARR’ - 1].
    • Remove the last element from array ‘ARR’.
    • Return ‘V’.
  • Defining POP_FRONT()
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘V’ as ‘ARR’[0].
    • Declare an array ‘TEMP’.
    • For i in range(1,length of ‘ARR’ -1 ):
      • Insert ‘ARR’[i] into  ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’
    • Return ‘V’.
  • Defining POP_MIDDLE()
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘IDX’ as (length of ‘ARR’) / 2,if the length is odd. (Index from where the element should be removed).
    • Set ‘IDX’ as ( (length of ‘ARR’) / 2) -1,if the length is even.
    • Set ‘V’ as ‘ARR’[IDX].
    • Declare an array ‘TEMP’.
    • For i in range(0,length of ‘ARR’ -1 ):
      • If i is equal to ‘IDX’:
        • Continue.
      • Insert ‘ARR’[i] into  ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’
    • Return ‘V’.
Solve now

02 Approach

In this approach, we will implement this special queue using two deque.

Deque (Doubly Ended Queue) is an inbuilt queue in each insertion and deletion at both end can be done in O(1) time.

We will maintain the condition that the size of ‘FIRST’ deque is always equal to the size of ‘SECOND’ deque or( size of ‘SECOND’ deque -1 ). So in the ‘PUSH_MIDDLE’ function,we will always push the element in the ‘FIRST’ deque. We will also define two functions FIRST_TO_SECOND() to transfer the last element of ‘FIRST’ into ‘SECOND’, and SECOND_TO_FIRST() to transfer the first element of ‘SECOND’ into ‘FIRST’.


 

Algorithm:

  • Defining SPECIAL_QUEUE():
    • Declare two deques ‘FIRST’ and ‘SECOND’.
  • Defining FIRST_TO_SECOND():
    • If the size of ‘FIRST’ is greater than` ‘SECOND’:
      • Set ‘VAL’ as FIRST’s last element.
      • Remove the last element from ‘FIRST’.
      • Insert ‘VAL’ in the front of ‘SECOND’.
  • Defining SECOND_TO_FIRST():
    • If the size of ‘SECOND’ is greater than the size of ‘FIRST’ +1:
      • Set ‘VAL’ as the first element of ‘SECOND’.
      • Remove the first element of ‘SECOND’.
      • Insert ‘VAL’ to the end of ‘FIRST’.


 

  • Defining PUSH_BACK(‘VAL’):
    • Append ‘VAL’ to the end of the ‘SECOND’.
    • Call SECOND_TO_FIRST().


 

  • Defining PUSH_FRONT(‘VAL’):
    • Insert ‘VAL’ in the front of ‘FIRST’.
    • Call FIRST_TO_SECOND().


 

  • Defining PUSH_MIDDLE(‘VAL’):
    • Insert ‘VAL’ at the end of ‘FIRST’.
    • Call FIRST_TO_SECOND().
  • Defining POP_BACK():
    • If the size of ‘FIRST’ is equal to 0 and the size of ‘SECOND’ is equal to 0:
      • Return -1.
    • Set ‘ANS’ as the last element of ‘SECOND’.
    • Remove the last element from ‘SECOND’.
    • Call FIRST_TO_SECOND().
    • Return ‘ANS’.
  • Defining POP_FRONT()
    • If the size of ‘FIRST’ is equal to 0 and the size of ‘SECOND’ is equal to 0:
      • Return -1.
    • If the size of ‘FIRST’ is 0, do the following:
      • Set ‘ANS’ as the first element of ‘SECOND’.
      • Remove the first element of ‘SECOND’.
      • Return ‘ANS’.
    • Else:
      • Set ‘ANS’ as the first element of the ‘FIRST’.
      • Remove the first element of ‘FIRST’.
      • Call ‘SECOND_TO_FIRST’.
      • Return ‘ANS’.
  • Defining POP_MIDDLE()
    • If the size of ‘FIRST’ is equal to 0 and the size of ‘SECOND’ is equal to 0:
      • Return -1.
    • If the size of ‘FIRST’ is equal to the size of ‘SECOND’.
      • Set ‘ANS’ as the last element of ‘FIRST’.
      • Remove the last element of ‘FIRST’.
    • Else:
      • Set ‘ANS’ as the first element of ‘SECOND’.
      • Remove the first element of ‘SECOND’.
    • Return ‘ANS’.
Solve now

03 Approach

5In this approach, we will implement this special queue using a doubly-linked list.

We will define the Node structure which has one integer variable ‘VALUE’ to store the value and two pointers ‘NEXT’ and ‘PREV’ to point to the next and previous node.

We will declare three-pointers ‘HEAD’,’ TAIL’ and ‘MID’ to point to the respective positions.

We will also declare a variable ‘QUEUE_SIZE’ to store the number of elements currently have in the queue.  

In the functions, we will add or remove the respective node from the list and update the list accordingly.  


 

Algorithm:

  • Defining ‘NODE’ structure.
    • Declare an integer variable ‘VALUE’ to store the value.
    • Declare two pointers ‘NEXT’ and ‘PREV’ to store the addresses of the next and previous nodes.
  • Defining SPECIAL_QUEUE():
    • Declare a node pointer ‘HEAD’ and set it as an empty node.
    • Declare a node pointer ‘TAIL’ and set it as an empty node.
    • Declare a node pointer ‘MID’ and set it as an empty node.
    • Declare an integer ‘QUEUE_SIZE’ and set it as 0.
  • Defining PUSH_BACK(‘VAL’):
    • Set ‘NEW_NODE’ as NODE(‘VAL’).
    • If ‘HEAD’ is an empty node:
      • Set ‘HEAD’ as ‘NEW_NODE’.
      • Set ‘MID’ as ‘NEW_NODE’.
      • Set ‘TAIL’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
    • Else:
      • Set TAIL‘s NEXT as ‘NEW_NODE’.
      • Set ‘NEW_NODE’ ‘s ‘PREV’ as ‘TAIL’.
      • Set ‘TAIL’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
      • If ‘QUEUE_SIZE is odd:
        • Set ‘MID’ as ‘MID‘s ‘NEXT’.


 

  • Defining PUSH_FRONT(‘VAL’):
    • Set ‘NEW_NODE’ as NODE(‘VAL’).
    • If ‘HEAD’ is an empty node:
      • Set ‘HEAD’ as ‘NEW_NODE’.
      • Set ‘MID’ as ‘NEW_NODE’.
      • Set ‘TAIL’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
    • Else:
      • Set HEAD‘s PREV as ‘NEW_NODE’.
      • Set ‘NEW_NODE’ ‘s ‘NEXT’ as ‘HEAD’.
      • Set ‘HEAD’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
      • If ‘QUEUE_SIZE is even:
        • Set ‘MID’ as ‘MID’ ‘s PREV.
  • Defining PUSH_MIDDLE(‘VAL’):
    • Set ‘NEW_NODE’ as NODE(‘VAL’).
    • If ‘HEAD’ is an empty node:
      • Set ‘HEAD’ as ‘NEW_NODE’.
      • Set ‘MID’ as ‘NEW_NODE’.
      • Set ‘TAIL’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
    • Else:
      • If ‘QUEUE_SIZE’ is ‘ODD’, we will insert the new node before the ‘MID’:
        • Set ‘TEMP’ as MID’s ‘PREV’.
        • Set TEMP’s NEXT as NEW_NODE.
        • Set NEW_NODE ‘s NEXT as ‘MID’.
        • Set ‘MID’ as ‘NEW_NODE’.
      • Else (Insert node after ‘MID’):
        • Set ‘TEMP’ as MID’s ‘NEXT’.
        • Set TEMP’s PREV as NEW_NODE.
        • Set MID‘s NEXT as ‘NEW_NODE’.
        • Set ‘MID’ as ‘NEW_NODE’.
      • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ + 1.
  • Defining POP_BACK():
    • If ‘HEAD’ is an empty node:
      • Return -1.
    • Set ‘VAL’ as TAIL’s VALUE.
    • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ -1.
    • Set TAIL as TAIL‘s PREV.
    • If ‘TAIL’ is not empty:
      • Set TAIL’s ‘NEXT’ as an empty node.
    • If ‘QUEUE_SIZE’ is equal to 0, do the following:
      • Set ‘HEAD’ as an empty node.
      • Set ‘TAIL’ as an empty node.
      • Set ‘MID’ as an empty node.
    • Else:
      • If ‘QUEUE_SIZE’ is odd, Set ‘MID’ as MID’s ‘PREV’.
    • Return ‘VAL’.


 

  • Defining POP_FRONT():
    • If ‘HEAD’ is an empty node:
      • Return -1.
    • Set ‘VAL’ as HEAD’s ‘VALUE’.
    • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ -1.
    • Set ‘HEAD’ as HEAD’s NEXT.
    • If ‘HEAD’ is not empty:
      • Set HEAD’s PREV as an empty node.
    • If ‘QUEUE_SIZE’ is equal to 0, do the following:
      • Set ‘HEAD’ as an empty node.
      • Set ‘TAIL’ as an empty node.
      • Set ‘MID’ as an empty node.
    • Else:
      • If ‘QUEUE_SIZE’ is even, Set ‘MID’ as MID’s ‘PREV’.
    • Return ‘VAL’.


 

  • Defining POP_MIDDLE()
    • If ‘HEAD’ is an empty node:
      • Return -1.
    • Set ‘VAL’ as MID’s ‘VALUE’.
    • Set ‘QUEUE_SIZE’ as ‘QUEUE_SIZE’ -1.
    • If ‘QUEUE_SIZE’ is equal to 0, do the following:
      • Set ‘HEAD’ as an empty node.
      • Set ‘TAIL’ as an empty node.
      • Set ‘MID’ as an empty node.
      • Return ‘VAL’.
    • Set ‘TEMP’ as ‘MID’.
    • If ‘QUEUE_SIZE’ is even, do the following:
      • Set TEMP’s PREV’s NEXT as TEMP’s NEXT.
      • Set ‘MID as TEMP’s ‘PREV’.
      • If ‘TEMP’s next is not empty: Set TEMP’s NEXT’s PREV as ‘MID’.
      • Return ‘VAL’.
    • Else:
      • Set ‘MID’ as MID’s NEXT.
      • Set MID’s ‘PREV’ as TEMP’s PREV.
      • If TEMP’s PREV is not empty:
        • Set TEMP’s PREV’s NEXT as ‘MID’.
      • Else:
        • Set ‘HEAD’ as ‘MID’.
        • Set ‘TAIL’ as ‘MID’.
      • Return ‘VAL’.
Solve now
Similar problems

Minimized Maximum of Products Distributed to Any Store

Moderate
Posted: 22 Feb, 2026

Landline Infrastructure

Easy
Posted: 24 Feb, 2026

Unique Gift Packing

Moderate
Posted: 1 Mar, 2026

Optimal Line Arrangement

Moderate
Posted: 1 Mar, 2026

Maximum Element and Frequency

Easy
Posted: 7 Mar, 2026