Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

According to Wikipedia, a stack:

is a last in, first out (LIFO) abstract data type and linear data structure.

While an array:

is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

As far as I understand, they are fairly similar. So, what are the main differences? If they are not the same, what can an array do that a stack can't and vice-versa?

share|improve this question
4  
How is your question not answered by what you found in Wikipedia? You can access an array's elements in any order; a stack must be accessed in LIFO order. –  Caleb May 7 '12 at 19:21
6  
@Caleb Just because you read something doesn't mean you understand the concept. In my mind, I didn't fully understand this until I asked. –  Dynamic May 7 '12 at 19:30
3  
-1 You basically posted the answer in your own question. What is it that you're asking, again? –  Andres F. May 8 '12 at 23:41
2  
I've just read meta.programmers and understood why you asked this non-question: it's for a contest. I seriously doubt you didn't understand the Wikipedia article. Shame on you :/ –  Andres F. May 24 '12 at 0:12
1  
@Dynamic Sorry, I don't believe you :/ This is very basic stuff you're asking (and answering yourself). But I'll drop the issue. –  Andres F. May 24 '12 at 0:54

8 Answers 8

up vote 41 down vote accepted

Well, you can certainly implement a stack with an array. The difference is in access. In an array, you have a list of elements and you can access any of them at any time. (Think of a bunch of wooden blocks all laid out in a row.)

But in a stack, there's no random-access operation; there are only Push, Peek and Pop, all of which deal exclusively with the element on the top of the stack. (Think of the wooden blocks stacked up vertically now. You can't touch anything below the top of the tower or it'll fall over.)

share|improve this answer
11  
wooden blocks - nice analogy –  Jesse Black May 7 '12 at 19:07
1  
You say "in a stack, there's no random-access operation" but I disagree, and will add more detail in my answer. –  Scott Whitlock May 9 '12 at 19:37
    
stacks are definitely implemented with random access –  dwelch May 10 '12 at 4:04
2  
You must suck at Jenga. –  DisgruntledGoat May 10 '12 at 19:23
1  
@Mason, I know. It was a joke. –  DisgruntledGoat May 10 '12 at 21:57

In a pure stack, the only allowable operations are Push, Pop, and Peek but in practical terms, that's not exactly true. Or rather, the Peek operation often allows you to look at any position on the stack, but the catch is that it's relative to the one end of the stack.

So, as others have said, an array is random access and everything's referenced to the beginning of the array.

In a stack, you can only add/remove at the working end of the stack, but you still have random access read but it's referenced to the working end. That's the fundamental difference.

For instance, when you pass parameters on a stack to a function, the callee doesn't have to pop the parameters off to look at them. It just pushes local variables on the stack and references all the local variables and parameters based on an offset from the stack pointer. If you were using just an array, then how would the callee know where to look for its parameters? When the callee is done, it pops off its local variables, pushes a return value, returns control to the caller, and the caller pops the return value (if any), and then pops the parameters off the stack. The beauty is that it works no matter how far nested you are into your function calls (assuming you don't run out of stack space).

That's one particular use/implementation, but it illustrates the difference: array is always referenced from the beginning but stacks are always referenced from some working end position.

One possible implementation of a stack is an array plus an index to remember where the working end is.

share|improve this answer

Their responsibilities are different:

  • Stack must be able to pop elements onto the stack and push elements from the stack, hence why it normally has methods Pop() and Push()

  • Array's responsibility is to get/set element at a specified index

share|improve this answer

I think the biggest confusion going on here is implementation versus basic data structures.

In most (more basic languages) an array represents a fixed length set of elements which you can access any at a given time. The fact that you have a bunch of elements like this tells you nothing about how it is supposed to be used (and frankly a computer won't know/care how you use it, as long as you don't violate usage).

A stack is an abstraction used to represent data that should be handled in a certain way. This is an abstract concept because it just says that it has to have some subroutine/method/function that can add to the top or remove from the top, while data below the top doesn't get touched. Purely your choice to use an array this way.

You can make a stack out of many different kinds of data structures: arrays (with some max size), dynamic arrays (can grow when out of space) or linked lists. Personally I feel that a linked list represents the restrictions of a stack the best as you have to put in a bit of effort to see things beyond the first element and it's very easy to add to the front and remove from the front.

So you can use an array to MAKE a stack, but they are not equivalent

share|improve this answer

You can retrieve an item from any index of an A\array.

With a stack, you can retrieve an item in the middle of stack A, by using another stack: B.

You keep taking the top item out of A and putting it into B until you are at the desired item of A, then you put the items from B back on top of stack A.

So, for data that requires the ability to retrieve an arbitrary index, the stack is more difficult to work with.

In the situation where you want "last in, first out" behavior, a stack will give you less overhead than an array.

share|improve this answer

I wouldn't go so far as to say they're "very similar."

An array is used to hold things that will later be accessed sequentially or through the index. The data structure doesn't imply any sort of access method (FIFO, LIFO, FILO, etc...) but it can be used that way if you wanted.

A stack is way of track of things as they're generated. An access method is implied / required depending upon the type of stack that's created. A frame stack would be a LIFO example. Disclaimer - I may be mixing my data structure taxonomy here and a stack may truly only allow LIFO. It would be a different type of queue otherwise.

So I could use an array as a stack (although I wouldn't want to) but I can't use a stack as an array (unless I work really hard at it).

share|improve this answer
1  
In the domain of 'structures for storing collections of objects', I wouldn't say they are very similar. In the domain of programming concepts, I'd say they are fairly similar. In the domain of things generally, I'd say they are almost identical. –  Kirk Broadhurst May 9 '12 at 2:41

The data in an array can be accessed by a key or index. The data in a stack can be accessed when it is popped off of the top of the stack. This means that accessing data from an array is easy if you know its index. Access data from a stack means you have to keep popping elements until you find the one you were looking for, which means data access can take longer.

share|improve this answer

An array is from the programmers perspective, fixed in place and size, you know where you are in it and where the whole thing is. You have access to all of it.

With a stack, you sit on one end of it but have no idea of its size or how far you can safely go. Your access to it is limited to the amount you have allocated, you often dont even know if when allocating the amount you wanted if you just slammed into the heap or program space. Your view of a stack is a small array that you have allocated yourself, the size you wanted, you have control over and can see. Your portion is no different than an array. The difference lies in your array is tacked onto one end of another array for sake of argument and terminology, which you have no visibility of, no idea how big or small, and you cant touch it without possibly causing harm. An array, unless global, is often implemented on the stack anyway, so the array and the stack share the same space for the duration of that function.

If you want to get into the hardware side, then it is processor specific of course, but generally the array is based off of a known starting point/address, the size is known by the compiler/programmer, and addresses are computed into it, sometimes using register offset addressing (load a value from the address defined by this base register value plus this offset register value, likewise when compiled it could be an immediate offset not necessarily register based, depends on the processor of course) which in assembly very much resembles accessing an array in high level code. Likewise with the stack, if available, you can use register or immediate offset addressing, often though it uses a special register, either the stack pointer itself, or a register reserved by the compiler/programmer to be used for accessing the stack frame for that function. And for some processors special stack access functions are used and/or required to access the stack. You have push and pop instructions but they are not used as often as you would think and dont really apply to this question. For some processors push and pop are aliases for instructions that can be used with any register, anywhere, not just the stack pointer on the stack, further removing push and pop from being related to this question.

share|improve this answer

protected by gnat Apr 12 at 8:22

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.