A stack is exactly what it sounds like, and a virtual stack has the same physical limitations a stack of plates would. You cannot remove an item from the stack, except for the item right at the top, and you cannot add an item to the stack, except to the top. This probably seems a little limiting, but at least it’s efficient; insertion and removal of elements is O(1), and so is element access.

Stack
Stack

Come to think of it, we just saw a data structure with efficiency like that, the singly linked list. Indeed, you can add elements to the end of a singly linked list, as well as remove and access the element at the end in constant time. (Note that it doesn’t matter which end of the data structure is the “top”, just that one of them is, if that makes sense.) Isn’t a stack just a list then? Well, it could be. It would be entirely faesible to create a stack using a linked list as an underlying data structure, as the efficiencies match up, and we don’t need random element access in a stack, so that removes that issue the list had. But remember how inefficient singly linked lists are with space? Removing some operations but keeping the same space efficiency hardly seems like a fair trade off! What else could we use then?

Lets write down our requirements. We need a data structure with:

  • O(1) insertion and deletion at one end
  • O(1) element access at the same end
  • High space efficiency (ideally)

Well we know that a singly-linked list fits the first two, but it’s a bit too heavyweight for the third. THe most space efficient structure we’ve got was the std::vector, and helpfully that also allows for constant time element insertion and deletion at the end! Building one from scratch though just requires a dynamic array of some sort, not necessarily an STL std::vector. Consider this example class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
template <class T>
class Stack
{
    private:

    T* data;
    unsigned int numElements;

    public:

    Stack()
    {
        data = NULL;
        numElements = 0;
    }

    // Add a new element to the top of the stack (O(1))
    void push(T element)
    {
        // Allocate memory for the new element
        // Use C-style allocation as C++ style does not efficiently allow for
        // this kind of thing
        data = (int*)realloc(data, (numElements+1)*sizeof(T));
        // Add the new element to the stack
        data[numElements] = element;
        // Increment the number of elements
        ++numElements;

        return;
    }

    // Remove the top element from the stack (O(1))
    void pop()
    {
        // Don't remove the top element if there isn't one!
        if(numElements == 0) return;

        // Delete the top element
        data = (int*)realloc(data, (numElements-1)*sizeof(T));

        // Decrement the number of elements
        --numElements;

        return;
    }

    // Access the element on the top of the stack (O(1))
    T top()
    {
        // If there are no elements in the stack, return an empty object
        if(numElements == 0)
        {
            T element;

            return element;
        }
        // Otherwise return the top element
        return data[numElements-1];
    }

    // Return true if the stack has no elements in it (O(1))
    bool empty()
    {
        return numElements == 0;
    }

    ~Stack()
    {
        // Repeatedly pop elements off of the stack until there are none left
        while(!empty()) pop();
    }
};

Here we’ve used a dynamic array, and have only implemented the functions we need for the data structure to actually be a stack; push, pop, top and empty. “Pushing” and “popping” are just putting an element onto the stack and taking one off. Before we continue it is important to note the nature of pushing and popping values. A stack can be classified as a LIFO data structure; the Last element In is the First element Out. This makes sense; if you put several plates on top of each other, the one you put on first will be at the bottom, and you will have to take every other plate off first to get to it. The consequenceof this is that the when you pop a sequence of values off of a stack, you recieve them in the reverse of how they were put on. Pushing 1,2,3 will give you 3,2,1 when you pop. This symmetry is actually a very useful property, you just have to watch out for it.

That’s all very well and good, but so far a stack is just a restriction of one of our existing structures, why are they important? Well, stacks are really quite fundamental to how computers work. In fact, you can create an entire computer design based solely on a single stack a stack machine), so they’re quite powerful.

Consider a function definition in C++; it has a name, a return type, some arguments, and some code inside of it. The name is irrelevant, it’s only there to aid the programmer, so we can ignore that. We’ll ignore the return type for now too, let’s just look at the arguments. A function can have any number of arguments the programmer wishes, and this is fine if they’re all referenced by name. But a computer doesn’t use names, it uses memory addresses and registers, and it can’t simply move the function arguments into registers as they might already be in use. Instead each argument is pushed in sequence onto a stack, and then popped off again when needed inside of the function. The computer can also push the values of each register to the stack, as a kind of backup. The registers can then be used for something else, before their values are replaced again by popping the values back.

As another example, let’s go back to the stack machine idea. Say we want to create a machine that can add, subtract, multiply and divide integers; the basic mathematical operations. Using a standard computer architecture, we would need a data structure that allowed for random element access to store the code, and another that stored the data the machine would operate on. A typical computer would combine these into one data structure, an array. To compute 2 * (4 + 5) / 3 using this system, we could do this

  • Move 4 into memory address 0
  • Move 5 into memory address 1
  • Add together address 0 and address 1 and store in address 0
  • Move 2 into memory address 1
  • Multiply address 0 by address 1 and store in address 0
  • Move 3 into memory address 1
  • Divide address 0 by address 1 and store in address 0
  • Result is now in address 1

This works perfectly and there is nothing wrong with it. But can we do it another way? Of course we can, we could use a stack!

  • Push 4 onto stack
  • Push 5 onto stack
  • Add the top two values on the stack together, and replace with the result
  • Push 2 onto stack
  • Multiply top two values, and replace with result
  • Push 3 onto stack
  • Divide second value by top value and replace with result
  • Result is now on top of the stack

We’ve used the same number of instructions, but we haven’t accessed any random pieces of memory, we’ve just used a single stack. And because we haven’t used memory addresses—in principle—the final code is much smaller. If you performed arithmetic this way, you could write the previous equation as 4 5 + 2 * 3 /. This removes the parentheses too, and is totally unambiguous. (This notation is called postfix notation, and was used in older HP calculators.)

As I mentioned earlier STL has it’s own stack class—aptly named stack—that uses vectors or lists (or something called a deque, but that’s pretty STL specific) as the underlying data structure, depending on the programmer’s choice. The STL implementation is far more efficient than the example stack code I presented (designed for readability, not performance*). A sample use is as below

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stack>
#include <vector> // Not necessary if only using default stack
#include <iostream>

int main(void)
{
    // Create a stack with the default container
    std::stack<int> container;

    container.push(1); // Push a value onto the stack
    container.push(2);
    container.pop(); // Pop a value off of the stack

    cout << container.top() << endl;

    // Create a stack using a vector
    std::stack<int, std::vector<int>> container2;
    // If you aren't using C++11, then write
    // std::stack<int, std::vector<int> > container2;
    // instead. The space is necessary.

    container2.push(10);
    container2.pop();
    if(container2.empty()) cout << "Container2 is empty!" << endl;
    else cout << "Container2 is not empty!" << endl;

    return 0;
}

*But it does use up slightly less memory than the STL version. 12kiB for the example code, in fact.