Reorganizar y actualizar los elementos de la array según lo especificado por las consultas dadas

Dada una array arr[] de tamaño N y consultas Q[][] , la tarea es realizar los siguientes tipos de consultas en la array dada. 0: desplaza la array una posición a la izquierda.

• 1: desplaza la array una posición a la derecha.
• 2 XY: actualice el valor de arr[X] = Y .
• 3 X: Imprimir arr[X] .

Ejemplo:

Entrada: array[]={1, 2, 3, 4, 5}, Q[][]={{0}, {1}, {3, 1}, {2, 2, 54}, {3, 2}}.
Salida: 4 54
Explicación: 
Consulta1: La array arr[] se modifica a {2, 3, 4, 5, 1} 
Consulta2: La array arr[] se modifica a {1, 2, 3, 4, 5} 
Consulta3: Imprime el valor de arr[1], es decir, 2 
Consulta4: la array arr[] se modifica a {1, 54, 3, 4, 5} 
Consulta5: imprime el valor de arr[2], es decir, 54.

Entrada: arr[]={1}, Q[][]={{0}, {1}, {2, 0, 54}, {3, 0}}
Salida: 54

Enfoque: el problema se puede resolver utilizando Deque (cola de doble extremo) para realizar la operación de inserción y eliminación en la parte delantera y trasera de la cola en O (1). Siga los pasos a continuación para resolver el problema.

1. Cree una cola de dos extremos , dq .
2. Empuje todos los elementos de la array arr[] a dq .
3. Para la consulta de tipo 0 (desplazamiento a la izquierda), extraiga un elemento del frente de dq y empújelo hacia la parte posterior de dq .
4. Para la consulta de tipo 1 ( Desplazamiento a la derecha), extraiga un elemento de la parte posterior de dq y empújelo hacia el frente de dq .
5. Para la consulta de tipo 2 , actualice dq[X] = Y.
6. Para la consulta de tipo 3 , imprima dq[X] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform the
// given operations
void Queries(int arr[], int N,
             vector<vector<int> >& Q)
{
 
    // Dequeue to store the
    // array elements
    deque<int> dq;
 
    // Insert all element of
    // the array into the dequeue
    for (int i = 0; i < N; i++) {
        dq.push_back(arr[i]);
    }
 
    // Stores the size of the queue
    int sz = Q.size();
 
    // Traverse each query
    for (int i = 0; i < sz; i++) {
 
        // Query for left shift.
        if (Q[i][0] == 0) {
 
            // Extract the element at
            // the front of the queue
            int front = dq[0];
 
            // Pop the element at
            // the front of the queue
            dq.pop_front();
 
            // Push the element at
            // the back of the queue
            dq.push_back(front);
        }
 
        // Query for right shift
        else if (Q[i][0] == 1) {
 
            // Extract the element at
            // the back of the queue
            int back = dq[N - 1];
 
            // Pop the element at
            // the back of the queue
            dq.pop_back();
 
            // Push the element at
            // the front of the queue
            dq.push_front(back);
        }
 
        // Query for update
        else if (Q[i][0] == 2) {
 
            dq[Q[i][1]] = Q[i][2];
        }
 
        // Query to get the value
        else {
            cout << dq[Q[i][1]] << " ";
        }
    }
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    vector<vector<int> > Q;
 
    // All possible Queries
    Q = { { 0 }, { 1 }, { 3, 1 },
          { 2, 2, 54 }, { 3, 2 } };
 
    Queries(arr, N, Q);
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to perform the
// given operations
static void Queries(int arr[], int N,
                    int [][]Q)
{
  // Dequeue to store the
  // array elements
  Vector<Integer> dq = new Vector<>();
 
  // Insert all element of
  // the array into the dequeue
  for (int i = 0; i < N; i++)
  {
    dq.add(arr[i]);
  }
 
  // Stores the size of the queue
  int sz = Q.length;
 
  // Traverse each query
  for (int i = 0; i < sz; i++)
  {
    // Query for left shift.
    if (Q[i][0] == 0)
    {
      // Extract the element at
      // the front of the queue
      int front = dq.get(0);
 
      // Pop the element at
      // the front of the queue
      dq.remove(0);
 
      // Push the element at
      // the back of the queue
      dq.add(front);
    }
 
    // Query for right shift
    else if (Q[i][0] == 1)
    {
      // Extract the element at
      // the back of the queue
      int back = dq.elementAt(dq.size() - 1);
 
      // Pop the element at
      // the back of the queue
      dq.remove(dq.size() - 1);
 
      // Push the element at
      // the front of the queue
      dq.add(0, back);
    }
 
    // Query for update
    else if (Q[i][0] == 2)
    {
      dq.set(Q[i][1], Q[i][2]);
    }
 
    // Query to get the value
    else
    {
      System.out.print(dq.get(Q[i][1]) + " ");
    }
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {1, 2, 3, 4, 5};
  int N = arr.length;
   
  // Vector<Vector<Integer>
  // > Q = new Vector<>();
 
  // All possible Queries
  int [][]Q = {{0}, {1}, {3, 1},
               {2, 2, 54}, {3, 2}};
  Queries(arr, N, Q);
}
}
 
// This code is contributed by Princi Singh

# Python3 program to implement
# the above approach
from collections import deque
 
# Function to perform the
# given operations
def Queries(arr, N, Q):
 
    # Dequeue to store the
    # array elements
    dq = deque()
 
    # Insert all element of
    # the array into the dequeue
    for i in range(N):
        dq.append(arr[i])
 
    # Stores the size of the queue
    sz = len(Q)
 
    # Traverse each query
    for i in range(sz):
 
        # Query for left shift.
        if (Q[i][0] == 0):
 
            # Extract the element at
            # the front of the queue
            front = dq[0]
 
            # Pop the element at
            # the front of the queue
            dq.popleft()
 
            # Push the element at
            # the back of the queue
            dq.appendleft(front)
 
        # Query for right shift
        elif (Q[i][0] == 1):
 
            # Extract the element at
            # the back of the queue
            back = dq[N - 1]
 
            # Pop the element at
            # the back of the queue
            dq.popleft()
 
            # Push the element at
            # the front of the queue
            dq.appendleft(back)
 
        # Query for update
        elif (Q[i][0] == 2):
            dq[Q[i][1]] = Q[i][2]
 
        # Query to get the value
        else:
            print(dq[Q[i][1]], end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 1, 2, 3, 4, 5 ]
    N = len(arr)
 
    # All possible Queries
    Q = [ [ 0 ], [ 1 ], [ 3, 1 ],
          [ 2, 2, 54 ], [ 3, 2 ] ]
 
    Queries(arr, N, Q)
 
# This code is contributed by mohit kumar 29

<script>
// Javascript program to implement
// the above approach
 
// Function to perform the
// given operations
function Queries(arr,N,Q)
{
  // Dequeue to store the
  // array elements
  let dq = [];
  
  // Insert all element of
  // the array into the dequeue
  for (let i = 0; i < N; i++)
  {
    dq.push(arr[i]);
  }
  
  // Stores the size of the queue
  let sz = Q.length;
  
  // Traverse each query
  for (let i = 0; i < sz; i++)
  {
    // Query for left shift.
    if (Q[i][0] == 0)
    {
      // Extract the element at
      // the front of the queue
      let front = dq[0];
  
      // Pop the element at
      // the front of the queue
      dq.shift();
  
      // Push the element at
      // the back of the queue
      dq.push(front);
    }
  
    // Query for right shift
    else if (Q[i][0] == 1)
    {
      // Extract the element at
      // the back of the queue
      let back = dq[dq.length - 1];
  
      // Pop the element at
      // the back of the queue
      dq.pop();
  
      // Push the element at
      // the front of the queue
      dq.unshift( back);
    }
  
    // Query for update
    else if (Q[i][0] == 2)
    {
      dq[Q[i][1]] = Q[i][2];
    }
  
    // Query to get the value
    else
    {
      document.write(dq[Q[i][1]] + " ");
    }
  }
}
 
// Driver Code
let arr=[1, 2, 3, 4, 5];
let N = arr.length;
    
// Vector<Vector<Integer>
// > Q = new Vector<>();
 
// All possible Queries
let Q = [[0], [1], [3, 1],
[2, 2, 54], [3, 2]];
Queries(arr, N, Q);
 
 
// This code is contributed by unknown2108
</script>

2 54

Complejidad temporal : O(N+|Q|)
Espacio auxiliar: O(N)