How frequent is a "stack" used in programming? In other words, would we loose something if we replace a stack with an array? Or is there any special case where a stack can't be replaced by anything else? I'm just a C++ beginner, and all I know about stacks is what they are used to store data, so the subject doesn't seem clear for me. Any information is apreciated.
Asked
Active
Viewed 317 times
1
-
1An array is just a type of stack. http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#Array – ceejayoz Mar 06 '15 at 17:05
-
1a stack enforces a storage paradigm. You use it if you need an container that supports First In Last Out. – NathanOliver Mar 06 '15 at 17:07
-
You can't do the same thing with just an array. You can do the same thing with an array, plus a variable to keep track of the "top", plus some code to treat it like a stack. So why not encapsulate that in an abstract data type and call it a stack? – Mike Seymour Mar 06 '15 at 17:07
-
this is not C++ question per-se , it should be under "data structures" tag. any way , each case has its needs , stack is used whenever FILO behavior is needed. – David Haim Mar 06 '15 at 17:07
-
As a beginners, you only need to know that when it holds more data than its capacity, it blows up your program. With that in mind, you can replace it with "automatic storage duration". When you have learned the difference of the two, you'll be able to answer this question yourself. – user3528438 Mar 06 '15 at 17:11
-
@user3528438 I don't understand that. – Neil Kirk Mar 06 '15 at 17:13
-
I'll answer to the first question (*"how frequent is a stack used in programming?"*) Well, each and every program that runs at a given moment in a computer, any computer, running any operating system in this world uses a stack, with or without the consent or the knowledge of its programmer. The stack is used to store the arguments and the local variables of the function currently running and of its caller and the caller of its caller and so on up to `main()`. Sure, this is implemented by the OS and the compiler but I can say the stack is one of the most used data structure in programming. – axiac Mar 06 '15 at 17:19
-
Using an array or a linked list is just an implementation detail. The specific feature of a stack is its *last-in first-out* policy. – axiac Mar 06 '15 at 17:21
-
An array doesn't support any of the stack operations - push, pop, and so on (it can only do indexing), so you can't replace a stack with an array. If you implement the stack operations for arrays, you've replaced the array with a stack, and you're back at square one. – molbdnilo Mar 06 '15 at 17:22
3 Answers
9
A "stack" is a generic name of a data structure that supports first-in last-out. An array is one possible implementation of a stack. A linked list could also implement a stack.
Consider a stack which grows dynamically as more elements are added to it, with no preset limit. A simple C-style array couldn't support this, as it has a size limited at compile-time. A std::vector, which works like an array in some ways but is more sophisticated, would allow this dynamic growth. (A linked-list would too, but would usually be less efficient).
Neil Kirk
- 21,327
- 9
- 53
- 91
-
Am I missing something? What precludes a C-style array from dynamically changing size at runtime? I would think another important factor would be the way the _Stack_ API constrains how it used. – James Adkison Mar 06 '15 at 17:11
-
@JamesAdkison By C-style array, I am referring to `int a[5];` for example. I know it's not the technical term for it. But I don't know that :) – Neil Kirk Mar 06 '15 at 17:13
-
I still think an integral part to the answer is that the API of a stack is important to controlling its usage (i.e., it enforces the semantics of FILO) regardless of the underlying storage implementation (which you've covered). – James Adkison Mar 06 '15 at 17:18
1
"First-in, last-out" is not always as descriptive for a new programmer as it might be for someone who has more programming experience. The concept of a stack - not, here, specifically referring to the C++ (or other-language) object - is a concept that permeates programming, at-large (a concept which is well described throughout SO and one I am sure that I would get "incorrect" were I to describe it in great detail, here).
There is indeed a link between the design and behavior of the stack data type you discuss and the programming 'thing' that is referred to as a call stack. In computer hardware, there is also a notion of a stack, briefly discussed, below.
To do the Call Stack Some Injustice
A call stack, specifically, is what keeps track of the calls in a program. The more calls that are made, the more calls are added on "top" of a stack. Once a call is finished, it's instance is removed from the stack, and control of the program is returned to the calling function.
So, I have three "functions" : A, B, C.
A calls B. B then calls C.
The order of the stack then is:
C
B
A
C takes priority for its resolution over the others (or, "it has control"). The others will not finish their operations until C has been resolved. Once it's resolved, it's "popped" off the stack, and B then does what it needs to do. Here, we find the notion of FILO (First In, Last Out): A is the first call; however, it is not resolved - in this case - until the others are complete.
Wikipedia's got a great description of the call stack and a great image for it, as well (without reading the article, the image isn't much help, see below image for discussion):
For our very high level purposes, this image shows us one important thing about the concept of a stack, at large: it is envisaged as a series of elements (in this case procedure locations - the yellow bars) stacked one on top of the other. Accessing the call stack works as described above: what's immediately needed is added on top, and removed once it is no longer needed.
A stack of cards or a stack of plates is often used as an analogy for the description of a stack's behavior.
This answer to a Stack Overflow question gives a great explanation of the stack.
Equal Injustice to the Hardware Stack
You are better to read about the hardware stack, elsewhere; however, from my understanding, it performs similarly to the call stack, above, but with data rather than procedures. Unfortunately, I do not yet know enough to distinguish between the hardware stack and the call stack. But, regardless, the notion of FILO still applies.
Why Is Stack Important?
The purpose of the stack object abstraction is to better mimic the operations of a stack. In fact, if my understanding is correct, the stack was proposed as the way to control procedural calls and is often what is implemented at the "architecture level" for memory management.
The stack data type abstraction forces the programmer to interact with the abstraction in a way that mimics - or is the root of - the call stack and the hardware stack. We could certainly do this with an array, but stack gives us the ability to do, easily.
-
1I think he was referring to the general concept of a stack and not "the stack" as often refereed to in programming. – Neil Kirk Mar 06 '15 at 17:40
1
This answer assumes that you are interested in the differences between the C++ STL stack<> and vector<> template classes.
A stack provides a sub-set of the functionality of a vector. This means a stack implementation has more freedom than a vector implementation.
A stack guarantees:
- Constant time push
- Constant time pop
But a vector guarantees in addition to the above:
- Constant time random access with an index
To provide constant time random access with indexes, all elements must be stored contignously, which is not required for a stack. A vector must be reallocated and copied when the size exceeds the capacity, but a stack does not need that. Hence a stack could be implemented with a linked list, but a vector can't, because of the additional requirements.
In other words, would we loose something if we replace a stack with an array?
Yes, we would loose some freedom in the implementation.
alain
- 11,939
- 2
- 31
- 51
-
Is the complexity an integral part of the definition of a general data structure type? – Neil Kirk Mar 06 '15 at 17:40
-
In the stl classes, the complexity is a part of the definition. I think some data types can only be distinguished by their different comlexities. If a list provides random access by traversal, the only difference is the complexity. – alain Mar 06 '15 at 17:44
-
@NeilKirk If you're interested, I found a nice question about the [Complexity guarantees](http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers) – alain Mar 06 '15 at 20:43