Home CPSC 340

Stacks

Overview

The next data structure we will look at is the stack. The data structures we have looked at thus far, arrays and linked lists, have been primarily concerned with how data is physically stored and accessed. Stacks, on the other hand, are primarily concerned with how data is logically stored and accessed. In fact, a stack can be built using either an array or a linked list as the base.

Logically, you can think of a stack as a bunch of things piled on top of each other. The only part of the stack that can be directly dealt with is the top. If you have a stack of papers, the only one you directly read is the top one. Likewise, if you have a stack of dinner plates, the only one you can directly put food on is the one on top.

If you want to take something from the stack, you can only take the thing that is on top of the stack. The rest of the stack is totally inaccessible as long as the thing on top is there. Taking the top thing off of the stack is usually called "popping from" the stack. When we pop from the stack, we both read the top and remove it.

Likewise, if you want to add something to the stack, you have to add it to the top. You can't insert at the bottom, or the middle, or any other place. Adding something to the top of a stack is called "pushing onto" the stack. Once that is done, the old top becomes buried and the thing we just pushed becomes the top.

Stacks are sometimes called a "Last In First Out" or LIFO data structure because the last thing that was added is going to be the first one out.


Applications of Stacks

Stacks are so much more limited in terms of how they can be used than other data structures, that you might think they are of limited use. As it turns out, there are several problems that can be solved best with stacks:

And many more.


Implementing a Stack with an Array

We can use an array to implement a stack. In order to do this, we will create an array to hold all of the items in the stack and keep track of where the top is. If we have a stack of integers, implemented as an array, then we start with the array empty and set top to -1.

Then when we push items onto the stack, we will increment the top and store our numbers there:

To pop items off the stack, we will simply decrement the top. We don't really need to erase the numbers out of the array. Since we change the index stored as the top, the next time we try to push or pop, it will be like those numbers aren't there.

How can we use an array to implement a stack?






Once we have our stack, how can we use it to check if parenthesis are nested correctly?







Implementing a Stack with a Linked List

One drawback of using an array to implement a stack is that we can fill up the array. We don't handle this in the example above, but if we try to push on a stack that is full, we will write past the bounds of our array. To properly handle this case, we would need to allocate a new array and copy everything over.

In order to avoid that, we can store the stack inside of a linked list instead of an array. Because we only ever care about the top of the stack, a singly-linked list will suffice. When writing a stack with a linked list, we can change the terminology a little bit and rename the next pointer to "underneath" and the head of the list to "top":


private:
    struct Node {
        int data;
        Node* underneath;
    };

    Node* top;

In an empty stack, the top node is equal to NULL. In a stack with nodes, we always keep a pointer to the top node, which has a pointer to the one underneath it and so on. The bottom of the stack has an underneath pointer of NULL:

When we push an item onto the stack, we are essentially adding at the front of the linked list. Likewise when we pop we are removing from the front of the linked list. Because stacks are more restrictive than an actual linked list, they are a bit simpler to program.

How could we use a linked list to implement a stack?







"The" Stack and Function Calls

Another area that exhibits "Last In First Out" behavior is function calls in a computer program. Consider the following code:


void f(int x) {
    cout << x;
}

void g(int x) {
    f(x + 1);
}

void h(int x) {
    g(x * 2);
}

int main( ) {
    h(7);
    return 0;
}

When this code runs, execution starts in main, then goes to h, then g, then f. When the functions begin to return, the chain of execution then goes back from f, back to g, then h and finally back to main where the program ends:

When a program runs, a stack is maintained to keep track of which function we are in. The block for each function is called a "stack frame" and contains information about the function like the values of the parameters, the local variables, and where the function is supposed to return to. This stack is called the "call stack" or just "the stack".

Each time a function is called, a new stack frame is created and it is pushed onto the call stack. Each time a function returns, its stack frame is popped off of the stack. When your program runs, it only ever accesses the function that it is currently in, or the top of the stack.

You will not have to worry about the call stack very often because it is maintained for you by the compiler.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.