Sign in to follow this  
load_bitmap_file

C++ Stack Usage

Recommended Posts

Hello. Could someone explain why/when to use stacks as data structures? All the links I got when I googled only dealt with how stacks are used by compilers. I think I understand how they work, but given the stack functions, I can't see why stacks would be used over a list or a deque. Secondly, my book tells me stacks use deques by default but can be made to use vectors or lists or some other container instead. Again, I don't see why. The only operations that occur on stacks are at the top end so deques seem to be the only logical choice..

Share this post


Link to post
Share on other sites
A Stack is FILO (first in last out) or LIFO (last in First out) they are the same thing.
A Queue is LILO or FIFO (same thing).

You would use a stack whenver you need to reverse order is one use for it, other uses is whenver you see fit because it's not ONLY for a list of uses because any other datastructure can be used for several reasons.

A Stack example

Stack|
Add "A" to stack
Stack|A
Add "Q" to stack
Stack|AQ
Remove an object from stack
Stack|A (returned Q)

A Queue example

Queue-|
Add "A" to Queue
Queue-A|
Add "Q" to Queue
Queue-AQ|
Remove an object from Queue
Queue-Q| (returned A)

A queue is like a line ... first come first serve a crowded elevator... while a stack is like a crowded elvator ... first people in get pushed toward the back and the last in is closest to the door.

Share this post


Link to post
Share on other sites
I said if you needed to reverse the order of something it's mindless. Also if you want to make a generic temporary holding place for a specific type of data you don't have to make extra varables on the fly with different levels of scope you just have to a generic type global stack and push and pop. As for lower level programming it's insanely useful, and if you don't know what for then you probably haven't programmed a lot in Assembler. As with everything else there are several different uses for any data structure, and several different ways to get around even using a data structure. If you have no use for a stack then don't use it. If after a while of programming you see a need for a stack, then use it.

The biggest use I personally have for using a stack is reverseing the order of information.

Share this post


Link to post
Share on other sites
Do you mean accessing data in reverse or "flip-flopping" all the elements in an array? Either way, the other standard containers have reverse iterators and the reverse() function to handle those operations.

Also, I'm not sure about using a global stack. Wouldn't you need a different stack for every data type you want? And afterwards wouldn't all the elements have to be cleared out and whatnot?

I've never used assembler so I don't know about that aspect of stacks. That would explain all the compiler-related stack stuff I found though.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You use std::stack when you want a stack. Its just a conceptual thing AFAICT, and really I'm not sure why they implemented some data types but not others (such as making map vs a binary tree - they might be the same internally, but the exposed interfaces would be quite different)

-Extrarius

Share this post


Link to post
Share on other sites
Well You wouldn't need to make a stack for each data type, just one they all inherit from (like Object class in java).

As for the reverse iterator ... that's fine, you may not need to use a stack. But if you don't whenever, it's converted into a stack whenever it's put into the assembler level.

I do agree that a lot of uses a stacks in higher level languages is reduced but It still gets used even if you don't.

I don't know if that's what you want to hear, :) but i hope it helped.

Share this post


Link to post
Share on other sites
a stack is an abstract data type (ADT), note the word "abstract" it can be represented by almost infinite number of ways.

Users of an ADT shouldn't need to care how it's representated they just wont to use the operations of a stack which is mainly push & pop operations. So thats why it's there it allows to view a container as stack where it logically makes sense to have that view.

The methods of push_back/front & pop_back/front in some of the other containers in STL such as list isn't normal operations of a list ADT there just convenience methods for the user so you may not see these operations in other container libraries for lists.

When do you use a stack? well when its required in your solution to a problem. Which would come up from the concepts in your problem domain.

Say you had a problem where you had to make a program that simulated the task of manually cleaning the dishes. Your work area has a sink, one side has a "stack" of dirty dishes initially the other is where you "stack" the clean ones, you can only clean a plate one at time.

If you look at the problem do you think a list of dishes sounds wright to represent the data in your program? not really a stack of dishes is more logical. Don't get me wrong you can use a list if you really wonted it to but doesn't seem like a good abstraction if you know what i mean.

Share this post


Link to post
Share on other sites
That's a good example thanks snk.
I hate not being able to think up an example is a pain sometimes.
As he said it's abstract not concrete. In fast you can make a stack out of a list, or array, or 50 variables.

Share this post


Link to post
Share on other sites
Quote:
Original post by load_bitmap_file
I think I've got it figured out now. Thanks to you both gryfang and snk_kid!

I still want to know why you would want someone would want a "vector stack" or a "list stack" instead of a "deque stack" though.


I'm not sure if i understood you correctly so i'll give you two answers.

If you mean't a list of stack of something then thats only if it comes up when conceptualizing the solutions.

If you mean't using the various containers to represent a stack, well if you remember what we where saying how it's abstract and can be represented by almost any structure, depending on which structure you decide to use has implications on how efficently it preforms a paritcular operation. Like a list is better for insertion & deletion in arbitrary places, vector is better for such and such.

When you use a stack you may decide that your going to be doing a particular operation more often than the rest, you check STL's documentation and see that say a list is more faster/efficent at that particular operation.

There is a notation used to measure against. It's called big-O notation you would learn about that if you took a course or read a book on data structures & algorithms.

Share this post


Link to post
Share on other sites
One problem with using vector as a stack is that you give the users of the stack too much freedom. If you are trying to limit the usage of your container to a FILO paradigm, you don't want users calling push_back, pop_front whenever they want.

A good usage of stacks is in implementing your own scripting language. As users call various functions in their scripts, you need to keep track of the running script's "program stack" so you know where to return in the higher-level script when a function is complete.

Regards,
Jeff

Share this post


Link to post
Share on other sites
Whoops, I got mixed up about what functions were available to stack. Thanks all!

EDIT: Ack, I've confused myself again. When making a stack of vectors, the vector functions don't become available to that stack object right? The intellisense thingy in VS didn't say so and I got a compiler error when I tried accessing pop_back() from a stack of type vector. Doesn't that mean that no matter what type of stack it is, it'll still only perform the same operations defined in stack and nothing else (EDIT: meaning that deques will always be the best type for stacks)?

EDIT (again): I think I may have understood you snk_kid. I meant declaring a stack like this:

std::stack<int, vector<int> > aStack;

Share this post


Link to post
Share on other sites
Quote:
Original post by load_bitmap_file
Whoops, I got mixed up about what functions were available to stack. Thanks all!

EDIT: Ack, I've confused myself again. When making a stack of vectors, the vector functions don't become available to that stack object right? The intellisense thingy in VS didn't say so and I got a compiler error when I tried accessing pop_back() from a stack of type vector. Doesn't that mean that no matter what type of stack it is, it'll still only perform the same operations defined in stack and nothing else (EDIT: meaning that deques will always be the best type for stacks)?

EDIT (again): I think I may have understood you snk_kid. I meant declaring a stack like this:

std::stack<int, vector<int> > aStack;


Becareful on the terminology it's not a stack of vector, it's a stack of ints implementated with a vector. Yes the interface is different and you can find out what operations are in the interface from here and yes deque is the best all round structure to use and it's the default so if do:

std::stack<int> my_stack_of_ints;


defaults to a deque implementation.

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