Sign in to follow this  
johnnyBravo

What is a 'stack' in c++?

Recommended Posts

Hi, I'm implementing an undo feature into a program to store prior changes to an image, although I have my own ideas on how to do this, I heard that I should use a 'stack', so i'm wondering what exactly is a stack in c++? Thanks

Share this post


Link to post
Share on other sites
A stack is not a C++-specific data structure.

Stacks support two operations, push and pop, such that the last element pushed (inserted) into the stack is the first to be popped (removed), like a stack of books, plates ...

Because of this behavior, they are also known as LIFO (Last In, First Out), by contrast with queues, which are FIFO (First In, First Out).

C++ has a std::stack container adapter. You can also use the push_back and pop_back member functions on sequence containers (vector, deque, list).

Share this post


Link to post
Share on other sites
The stack data type is a First-In-Last-Out (FILO) data structure. In other words, the first thing you put in is the last one you take out. So, it's perfect for storing actions for undoing, as you want to undo things in order reverse to that in which they were done.

Wikipedia Stack Article

In C++, there is a standard Stack template, which supports the function push to put stuff in, and pop to take stuff out of the stack.

MSDN stack class reference

EDIT: I type too slow. :)

Share this post


Link to post
Share on other sites
Not that I know. I use the std::vector as stacks in my programs, and I never had any problem with it.

Share this post


Link to post
Share on other sites
You can implement a stack using a vector. It has the usual benefits/drawbacks of using a vector (a push_back() might cause every object in the vector to be copied).

By default, std::stack uses a deque, not a vector, and it's best to leave it that way unless you have a thorough understanding of the considerations to using vector vs deque.

Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyBravo
Is there much of a difference between using c++'s stack and vector?


The main difference is the interface - and the fact that you get to choose which container implements the behavior.

Equivilants:
std::vector std::stack

push_back() push()
pop_back() pop()
back() top()
size()/empty() size()/empty()
everything else n/a


Documentation

Share this post


Link to post
Share on other sites
not sure, but a stack should be better performant than a vector.
Its smaller API enables more highly optimised implementation.

Whether this is true for the actual implementation you're using is of course implementation dependent!

Share this post


Link to post
Share on other sites
Quote:
Original post by jwenting
not sure, but a stack should be better performant than a vector.
Its smaller API enables more highly optimised implementation.

Whether this is true for the actual implementation you're using is of course implementation dependent!


A std::stack in C++ is a wrapper around another container (deque by default). That isn't implementation dependent.

Share this post


Link to post
Share on other sites
Quote:
Original post by jwenting
not sure, but a stack should be better performant than a vector.


All std::stack does is adapt another container (as provided via second template argument, defaulting to std::deque). std::stack< int , std::vector< int > > will obviously not outperform std::vector< int >, as the former is implemented using the later. Cases where std::stack< int > (std::deque implementation) outperform std::vector will be due to std::deque outperforming std::vector in that situation, and have nothing to do with std::vector itself.

Quote:
Its smaller API enables more highly optimised implementation.


Smaller API has no direct correlation to speed. If an API requires certain restrictions which prevent certain optimization techinques from being utilized, which would indeed be used, then that argument holds merit. Since all the restrictions of the implementing container still hold, and there are very few optimizations one could layer atop*, using std::stack<T,C<T> > will be very very very very unlikely to cause a performance gain over directly using C<T> (where C is a templatized container class).

* "very very very very few" as in only 1 that I can think of, atop std::list (why the heck would you using a list for a stack?). If the implementaiton of std::list::size is O(N), allowing for std::list::splice(begin, end) to be O(1), the elimination of the later method from the visible interface would allow a std::stack to store the size of the list, causing std::stack::size to be O(1) instead of O(N) in that circumstance.

The main purpouse of std::stack is to clarify intent and how you plan to use the container, not optimization.

Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyBravo
Ah ok, yeah I love vectors :)

Is there much of a difference between using c++'s stack and vector?

Yes. Stacks and vectors are very different. Primarily, the difference is that in the case of a stack, you add and remove elements only at one end, and you can only access the top element.

You can easily implement a stack using a vector, but why reinvent the wheel?

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
The main purpouse of std::stack is to clarify intent and how you plan to use the container


QFE. Please understand that this is quite valuable in and of itself.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this