Estructuras de datos | Cola | Pregunta 11 – Part 2

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: Aquí importa el orden en que se realizan las operaciones de inserción y eliminación.
El mejor de los casos: las operaciones de inserción y eliminación se realizan alternativamente. En cada operación de eliminación, se realizan 2 operaciones pop y 1 push. Por lo tanto, se realizan operaciones totales m + n push (n push para insertar() y m push para eliminar()) y 2 millones de operaciones emergentes.

El peor de los casos: primero se insertan n elementos y luego se eliminan m elementos. En la primera operación de eliminación, se realizan n + 1 operaciones pop yn operaciones push. Aparte de primero, en todas las operaciones de eliminación, se realiza 1 operación emergente. Por lo tanto, se realizan un total de m + n operaciones pop y 2n operaciones push (n push para insertar() y n push para eliminar())
Cuestionario de esta pregunta