How is Stack implemented in STL?

Question

I came across this:

Standard C++ Containers

It triggered me the question, how are stacks implemented in STL?

I am looking for a description similar to:

How is C++ std::vector implemented?

What really is a deque in STL?

What in the description of the `stack` adapter at the link you provided is causing confusion? An alternative documentation on that adapter [can be found **here**](http://en.cppreference.com/w/cpp/container/stack), and I highly recc you bookmark that site. It is outstanding as a C++ reference, one of the very best imho. — WhozCraig, Mar 11 '16 at 01:02

score 13 · Accepted Answer · answered Mar 11 '16 at 01:30

stack is an adapter which uses another container for the underlying storage, and links the functions push, pop, emplace etc. to the relevant functions in the underlying container.

By default, std::stack uses std::deque as underlying container. But you can specify your own, e.g. std::stack<T, std::vector<T>> s;.

For more details about this, see cppreference.

score 5 · Answer 2 · answered Mar 11 '16 at 01:28

std::stack has a template parameter Container, which is required to be a container that can store elements of type T (that is to say, the type of the elements of the stack). This container is required to have back(), push_back() and pop_back() functions, and the standard containers vector, deque and list all satisfy the requirements.

So, whichever container type the user specifies, the resulting instantiation of std::stack is a class which:

has a data member of type Container<T> (or something very similar if not literally a data member. I suppose it could probably be a private base class).
calls push_back() on the container whenever you call push() on the stack.
calls pop_back() on the container whenever you call pop() on the stack.
and so on.

Loosely speaking, std::stack<T> is an object that wraps up an instance of std::deque<T>, and hides most of deque's functionality in order to present a simpler interface solely for use as a last-in-first-out (LIFO) queue. Similarly std::queue presents a FIFO queue.

How is Stack implemented in STL?

2 Answers2