In this paper we discuss the problem of computing structured complex stability radii of large and sparse matrices and pencils. For this purpose we consider certain structured pseudospectra. To compute the structured complex stability radius we have to find the pseudospectrum which touches the imaginary axis. Therefore, we set up an iteration over the real part of the rightmost pseudoeigenvalue. For that we use a new fast iterative scheme which is based on certain rank-1 perturbations of the matrix or pencil. Finally, we illustrate the performance of our algorithm by using real-world example data.