Today I was reading a lot of articles complaining about Java Generics or C++ Templates. Now, my question is: How can someone implement a collection data structure like Stack without using them?
As the OP correctly stated in a comment, both of these language constructs were added to their respective langugae to enable developers to write type-independent code and still provide compile-time type-safety.
Before they were added, this was not possible in these languages. You could either flexible or (compile-time) typesafe code, but not both. Collection types typically valued code-reuse more than compile-time type-checking and could therefore contain anything, leaving it to their users to perform runtime checks (e.g. in the form of casts).
In languages that do not provide such a feature (e.g. C), this is still the case - just have a look at their libraries.