Why do we need stacks when we already have so many data structures

Question

Why do we need stacks when we already have so many data structures that can also handle managing data in reverse directions [linked list & vectors]? What's so useful/distinctive about stacks that other data structures don't have?
Also, why are only arrays and linked lists compatible with stacks, why arent vectors compatible with stacks?

Answer 1

This sounds like a homework question. I'd argue the final question is based on a flawed premise.

First, stacks are an age-old concept. Every computer I've ever programmed at the assembly code level has used them. So partly they exist for historical reasons.

But it's a useful concept. Stacks have three basic operations:

• Push
• Peek
• Pop

They're an easy, first-in, last-out structure. They're GREAT for certain types of languages. There are programming languages built on the concept of stacks. They're exceedingly easy to write. (The language itself.) And they're kind of fun.

For instance:

8 7 mul

That's legal code in PostScript and a variety of other stack-based languages. The interpreter breaks that into tokens and then it sees an 8 and pushes it onto the stack. It sees the 7 and pushes that. It sees the mul and knows multiple takes two operands, so it pops the 7, pops the 8, multiplies them, and pushes 56. When that line is done, the stack has just a 56 on it (plus whatever was on it earlier than this.

Stacks are also a very useful in other forms of parsing. I use them when parsing certain types of input (like XML). When I reach an "end of object" marker, then I pop the top item on the stack, and the next thing I encounter in my input is working on the new top of stack item.

But stacks are a CONCEPT, not an IMPLEMENTATION. Arrays, linked lists, and vectors are all reasonable ways to implement a stack.

As for the last question -- it's a flawed question. What's the difference between an array and a vector? Well, that might be language-specific. In C++, arrays are fixed-length (and I almost never use them). I would use a vector to implement a stack, with the top of the stack being the last item in the vector.

That's a lighter-weight answer than using linked lists, depending upon how big your stack is going to grow. (Every time you grow a vector beyond whatever is allocated, it can be kind of expensive, so if you don't allocate enough space ahead of time, linked lists might be cheaper.)

Answer 2

After doing some reading + research, here's what I think:

1. Why do we need stacks when we already have so many data structures that can also handle managing data in reverse directions [linked list & vectors]? we need stacks because of their feature to store data in reverse, and output the data in LIFO, along with their simplicity. Other data structures store data in sequential order, the order in which the data was originally provided, and stacks go in LIFO [this sequence is needed when working with applications]. Also since stacks are much simpler to use compared to linked lists and vectors, they are the ideal candidate, with their top powers of push, peek, and pop. Think of it like this: "Don't use a bomb to kill flies when you have a net"

2. What's so useful/distinctive about stacks that other data structures don't have? Other data structures are not as simple as stacks since stacks have 3 built-in functions: push, peek and pop. And even though we can store data reversed in vectors and linked lists, it is much more complicated. So think of it as a simple tool to get the job done. Think of it like this: we use a for-loop even though we have a while loop that does the same job, but a for-loop is short simple and built for that specific purpose, whereas a while loop is a bigger and a bit unnecessary for a task that a for-loop can accomplish

3. Also, why are only arrays and linked lists compatible with stacks, why aren't vectors compatible with stacks? With stacks, we use arrays and linked lists and NOT VECTORS because stacks were created using vectors. Hint, hint push, pop, are features that vectors have as well... Also, storing a vector within a stack is like storing a vector within a vector that is wrong and the compiler will throw an exception.

Answer 3

A stack is an ADT (abstract data type), consisting of a mathematical model (a sequence of elements) and some operations performed on that model (push, pop, isEmpty, makenull, and top). In many applications, these are the only operations you would want to do on a list: every time you delete an element, it’s the element that was most recently inserted into the list. An important application of stacks is call stacks, which are used to implement procedure calls. When a procedure A calls a procedure B in your program, a new stack frame for procedure B is pushed onto the call stack.

ADT’s are called interfaces in Java, and are the specs, while data structures are about how these specs are implemented. A stack can be implemented using an array data structure, or a linked list data structure, in such a manner that all the five stack ADT operations can be performed in O(1) time.

So, I wouldn’t call a stack a data structure; I would call it an ADT. Examples of data structures include arrays, sorted arrays, linked lists, doubly linked lists, binary search trees, hash tables, max heap, etc. Each data structure is well suited for a subset of operations that they perform efficiently on. Depending on which subset of operations (ADT) arises in your application or algorithm, you can choose a data structure that performs this subset of operations efficiently.