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);
}
See PUSH and POP operation in code.
Given : n=insert
m=delete
x=push
y=pop
Trywith some example.
Now, in given code
Say S_2 already contains 1,2,3 // No PUSH operation here, no need to consider it
$S_{1}$ has to push 4,5 // So, 2 PUSH operation here.
Now, POP S_2 //3 POP operation Not considering here
Now, POP $S_1$// 2 POP operation
PUSH them in $S_2$//2 PUSH operation
Again POP $S_2$// 2 POP operation
-------------------------------------------------------------------------------------------------------------------------------
In PUSH 4,5 push to insert $S_1$ (Say, n push)
Now, we only POP 5 from stack (Say m) and PUSH in $S_2$.
So, Total PUSH n+m.
and maximum we can push 2n (when we POP 4,5 both from stack (Say n) and PUSH in $S_2$. )
So, for PUSH operation $n+m< x\leq 2n$
--------------------------------------------------------------------------------------------------------------------------------------------------------------
In POP operation say 5 POP from $S_1$.(say m)
Now, 5 PUSH in $S_2$.(Say m)
Now, we have to POP only 5 from $S_2$.
Otherwise in worst case
In POP operation say 4,5 POP from $S_1$.(say n)
Now, only 5 PUSH in $S_2$.(Say m)
Now, we have to POP only 5 from $S_2$.
n+m POP operation
So, total POP operation $2m< x\leq m+n$