We have to physically compress the gas. The reason behind this, along with answering your 2nd question, will be apparent if we analyze the Carnot cycle. It's convenient to consider the $PV$ and $TS$ diagrams when talking about processes:
Let's start at state 1 with $S_1$, $T_1$, $P_1$, etc.
1 $\rightarrow$ 2: Isentropic work input.
2nd law for this process gives:
$$ S_2 - S_1 = \int\frac{\delta Q_{12}}{T} + \Delta S_{gen}$$
Look at the TS diagram; clearly, $S_2 = S_1$. We also know $\Delta S_{gen} = 0$ since this is the Carnot cycle.
Therefore, $Q_{12} = 0$ and the 2nd law yields $S_1 = S_2$.
How else are we gonna increase the temperature to state 2? We have to add some sort non-heat energy to increase the temperature but keep $\Delta S = 0$. We therefore must add work.
2 $\rightarrow$ 3: Isothermal heat addition and work output.
The second law for this process gives:
$$ S_3 - S_2 = \frac{Q_{23}}{T_H}$$
where $T_H = T_2 = T_3$. Heat must therefore be added because we increase entropy. Note from the $PV$ diagram that we also have positive work output.
We've now made half a square on the $TS$ diagram. Next step is to isentropically decrease the temperature back to $T_1$.
3 $\rightarrow$ 4: Isentropic work output.
For the same reason as process 1 $\rightarrow$ 2, this process is adiabatic. The only way to decrease the entropy is to remove some sort of non-heat energy (i.e., the second law says we have to output work).
4 $\rightarrow$ 1: Isothermal heat rejection and work input.
The second law for this process gives:
$$ S_{1'} - S_4 = \frac{Q_{41'}}{T_C}$$
where $T_C = T_4 = T_1$. I'm using state $1'$ because we could reject heat $Q_{41'} = T_C(S_1' - S_4)$ that takes us to a different state. But, since this is a cycle, we reject just enough heat to bring us back to state $1$. We don't have to do that, we just choose to since this is a cycle. I think that answers your 2nd question.