For a finite involutive non-degenerate solution $(X,r)$ of the Yang--Baxter equation it is known that the structure monoid $M(X,r)$ is a monoid of I-type, and the structure algebra $K[M(X,r)]$ over a field $K$ share many properties with commutative polynomial algebras, in particular, it is a Noetherian PI-domain that has finite Gelfand--Kirillov dimension. In this paper we deal with arbitrary finite (left) non-degenerate solutions. Although the structure of both the monoid $M(X,r)$ and the algebra $K[M(X,r)]$ is much more complicated than in the involutive case, we provide some deep insights. In this general context, using a realization of Lebed and Vendramin of $M(X,r)$ as a regular submonoid in the semidirect product $A(X,r)\rtimes\mathrm{Sym}(X)$, where $A(X,r)$ is the structure monoid of the rack solution associated to $(X,r)$, we prove that $K[M(X,r)]$ is a module finite normal extension of a commutative affine subalgebra. In particular, $K[M(X,r)]$ is a Noetherian PI-algebra of finite Gelfand--Kirillov dimension bounded by $|X|$. We also characterize, in ring-theoretical terms of $K[M(X,r)]$, when $(X,r)$ is an involutive solution. This characterization provides, in particular, a positive answer to the Gateva-Ivanova conjecture concerning cancellativity of $M(X,r)$. These results allow us to control the prime spectrum of the algebra $K[M(X,r)]$ and to describe the Jacobson radical and prime radical of $K[M(X,r)]$. Finally, we give a matrix-type representation of the algebra $K[M(X,r)]/P$ for each prime ideal $P$ of $K[M(X,r)]$. As a consequence, we show that if $K[M(X,r)]$ is semiprime then there exist finitely many finitely generated abelian-by-finite groups, $G_1,\dotsc,G_m$, each being the group of quotients of a cancellative subsemigroup of $M(X,r)$ such that the algebra $K[M(X,r)]$ embeds into $\mathrm{M}_{v_1}(K[G_1])\times\dotsb\times \mathrm{M}_{v_m}(K[G_m])$., Comment: A subtle mistake in the proof of Theorem 4.4 has been corrected (will appear in a corrigendum et addendum, TAMS). In the latter paper we also strengthen some of the results by removing the "square free'' condition in Section 5 and in this paper we also prove new homological equivalences in Theorem 4.4