Creating a stack template

[Sanshin77]

After finishing up my book on C++ I started creating some containers(templates) Ive done a simple Array, and a linkedlist so far and now I wanna make a stack. Ive been looking around and wikipedia mentions implementing a stack with either a linkedlist or an array. Both seem pretty simple and I think I'd go for a linkedlist. I'm just wondering if there are any other preferable solutions, as fast as possible, because the future uses would involve a lot of pushes and pop's per frame.

What's the best/most common/fastest way? What kind of solution does hardcore dudes like the people behind OpenGL use for glPush- and glPop- Matrix ?

Thanks in advance...

Edit: Seems noone wants to answer...

[fantastico]

You have to think about how you will use the stack and then choose the implementation to squeeze out the last bit of performance if you really need that, in terms of asymptotic complexity a vector and a doubly-linked list are equal.
However, a list will only hold the objects that are actually on the stack currently, while a vector usually won't shrink again if you pop items from the stack. On the other side, the overhead of pushing onto a vector is less than appending to a list, especially if you know in advance how many items there will be at most and initialize the vector with a large enough capacity so resizing operations will be rare.
So you have a tradeoff between wasted memory and slighty better performance in some cases, I suggest you implement both, test and tell us

[Sanshin77]

Im not good at testing tho, tried using instruments(mac app) to test for memory leaks with my linkedlist, didn't understand a shit :/
Ive started on the linkedlist implementation so we'll see how that goes.

[dandymcgee]

Im not good at testing tho, tried using instruments(mac app) to test for memory leaks with my linkedlist, didn't understand a shit :/
Ive started on the linkedlist implementation so we'll see how that goes.

http://www.codeproject.com/KB/cpp/Memor ... n_CPP.aspx

You might wanna check this out. Personally, I've not used any of these concepts in any of my projects but I found it to be an interesting read.