This work is devoted to the numerical computation of complex band structure $\k=\k(\omega)\in\mathbb C^3$ for positive $\omega$ of three dimensional isotropic dispersive or non-dispersive photonic crystals from the perspective of structured quadratic eigenvalue problems (QEPs). Our basic strategy is to fix two degrees of freedom in $\k\in\mathbb C^3$ and to view the remaining one as the eigenvalue of a quadratic operator pencil derived from Maxwell's equations. Then Yee's scheme is employed to discretize $\nabla\times$ and $\k\times$ operators in this quadratic operator pencil. Distinct from the others' works which either ignore or directly exploit the Hamiltonian structure of the spectrum of the resulting QEP, we reformulate this QEP into an equivalent $\top$-palindromic QEP to facilitate the use of superior structure-preserving algorithms. Ultimately we rely on the structured Arnoldi algorithm, namely the G$\top$SHIRA algorithm, to compute eigenvalues of a $\top$-skew-Hamiltonian pair which are near or in $[-2,2]$, a much narrower region than the whole positive real axis in the origin problem. Moreover, to accelerate the inner iterations of the G$\top$SHIRA algorithm, we propose the preconditioning technique, making most of the eigenmatrix, which can essentially be seen as the Kronecker product of three discrete Fourier transformation matrices, of the commutative discretized $\partial_x,\partial_y,\partial_z$ operators. The advantage of our method is discussed in detail and corroborated by several numerical results.