PUERTA | PUERTA-CS-2006 | Pregunta 49

A continuación se muestra una implementación de una cola Q, utilizando dos pilas S1 y S2:

void insert(Q, x) {
   push (S1, x);
}
   
void delete(Q){
   if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print(“Q is empty”);
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
   x=pop(S2);
}

Sean realizadas n operaciones de inserción y m (<=n) de eliminación en un orden arbitrario en una cola vacía Q. Sean x e y el número de operaciones push y pop realizadas respectivamente en el proceso. ¿Cuál de los siguientes es cierto para todo m y n?
(A) n+m <= x < 2n y 2m <= y <= n+m
(B) n+m <= x < 2n y 2m<= y <= 2n
(C) 2m <= x < 2n y 2m <= y <= n+m
(D) 2m <= x <2n y 2m <= y <= 2n

Respuesta: (A)
Explicación: Igual que https://www.geeksforgeeks.org/data-structures-queue -pregunta-10/
Cuestionario de esta pregunta