What are stacks used for? Why are they in C++?

Question

I've been reviewing C++ with the book Practical C++ Programming, and came across these things called Stacks. Defined in the book, it is defined as an algorithm for storing data.

From what I've seen in the book, it looks a lot like assembly...I also recall reading something about something that is 16 bit.

So my question: What are stacks used for, are they still useful or is it an old method of doing something that can be done more simply and efficiently with 32/64 bit computers? I'm just really confused about what purpose stacks serve.

---

Edit: Since my question is so vague, I'll rephrase it... What is a stack, and when should it be used.

Solution 1

Depends on which stack you're talking about.

The first is a storage location in memory.

A stack is a last-in, first-out data structure which is still very useful regardless of 16/32/64 bit computers.

As others have said, the call stack (or 'the stack') is an example of a Stack in action.

Solution 2

Stacks are not a method, but rather a data structure, last in, first out (LIFO).

In C++, std::stack<> is a class template whose data can be any type. There are many situations where last in, first out is exactly what you need.

An example are virtual machines or interpreters that utilise a stack architecture to save the running state during execution of functions/procedures. Consider the following the interpreter of a language where sub-procedures may not change the state of the caller:

std::stack<RunState> state;
Instruction i = fetch();

switch (i.type()) {
case Instruction.Call:
    state.push (state.top());
    break;
case Instruction.Return:
    state.pop();
    break;
...
}

Wikipedia has more examples for the use of stack data structures. Some sorting problems are solved relatively easily with stacks.

As with all data structures, and C++ has quite some of them (lists, queues, sets, maps (a.k.a. associative arrays, a.k.a. dictionaries), arrays/vectors, and more), you may not need them now and maybe not even in 2 years, but you should know about them, their properties, advantages, disadvantages, and when it is the right moment to use them.

Solution 3

Essentially, they are used when you need to store data in a LIFO (Last In, First Out) fashion. You can find informations here. Working on a 16/32/64/whatever bits architecture has nothing to do with the principle of a stack.

Solution 4

You could use a stack in case of standard LIFO logic. There are a lot of problems that required the LIFO logic.

View more solutions

Comments

[sepp2k]

The call stack is also first-in, last-out. So it's not a different kind of stack - it's just one example of a stack.

[Sebastian Mach]

I am being an arse, but a near 100k contributor who declares C experience should know that the "memory-stack" is an application of stacks.

[Justin Niessner]

@phresnel - I'd agree. And I do. Extremely poorly worded answer trying to show that the OP may have been reading about either the data structure itself or its application. Hence the re-wording. Sorry for the confusion.

[Sebastian Mach]

@JustinNiessner: But maybe I was too much of an arse. Maybe you just meant something like "want an explanation of call stacks or want an explanation of stack data structures". Sorry if I was too offensive.