Stacks

Notes

A stack is a data structure that is similar in spirit to a pile of cafeteria trays.

Think about the trays in the dining halls: when the dining staff put trays out before meals, they pile them from the bottom to the top, and then you take the top-most tray when you arrive. The last tray that the staff put on the piles is the first one taken from the pile.

Similarly, with stacks, the last element inserted will be the first element retrieved. We'll refer to this pattern of insertion and retrieval as "last-in, first-out," or LIFO for short.

A stack's two primary operations are called push and pop. push places a new element on the top of the stack (like a dining hall's tray or a function's stack frame), and pop retrieves the topmost element from the stack, decrementing the stack's size in the process.

Like queues (and unlike arrays), stacks typically don't allow access to elements in the middle.

This is one way to define a stack for char*s.

CAPACITY is a constant and strings is a statically-sized array of char*s that you'll use for storing the char* elements.

size stores the number of elements currently in the stack. You'll need to adjust it appropriately so that you can track the location of the "top" of the stack.

Why is this design suboptimal? It imposes a limit on the size of the stack.

To push an element onto the stack, first make sure that the array isn't full by comparing size to CAPACITY.

If size < CAPACITY, store the element in the next available open slot, which should be at index [size].

To pop an element off the stack, first make sure that there are elements in the array by checking whether size > 0.

If size > 0, decrement size and return the last element in the array, which should be at index [size].

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Push

Implement a push function for this stack.

jharvard@run.cs50.net (~): ./a.out
Pushing 10 strings onto the stack...
0
1
2
3
4
5
6
7
8
9
done!
Making sure that the stack size is indeed 10...good!
Making sure that push() now returns false...good!

********
Success!
********

Try out some pseudocode here!
/*************************************************************************
 * stack.c
 *
 * Implements a simple stack structure for char* s.
 ************************************************************************/

// for strdup() in the testing code
#define _XOPEN_SOURCE 500

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// the capacity of the stack
#define CAPACITY 10

typedef struct
{
    // storage for the elements in the stack
    char* strings[CAPACITY];

    // the number of elements currently in the stack
    int size;
}
stack;

// declare a stack (as a global variable)
stack s;

/**
 * Puts a new element into the stack onto the "top" of the data structure
 * so that it will be retrived prior to the elements already in the stack.
 */
bool push(char* str)
{
    // TODO
}

/**
 * Implements some simple test code for our stack
 */
int main(void)
{
    // initialize the stack
    s.size = 0;

    printf("Pushing %i strings onto the stack...\n", CAPACITY);
    for (int i = 0; i < CAPACITY; i++)
    {
        char str[12];
        sprintf(str, "%i", i);
        push(strdup(str));
        printf("%s\n", str);
    }
    printf("done!\n");

    printf("Making sure that the stack size is indeed %i...", CAPACITY);
    assert(s.size == CAPACITY);
    printf("good!\n");

    printf("Making sure that push() now returns false...");
    assert(!push("too much!"));
    printf("good!\n");

    printf("\n********\nSuccess!\n********\n");

    return 0;
}

Pop

Implement a pop function for this stack.

jharvard@run.cs50.net (~): ./a.out
Pushing 10 strings onto the stack...done!
Popping everything off of the stack...done!
Making sure that pop() returned values in LIFO order...good!
Making sure that the stack is now empty...good!
Making sure that pop() now returns NULL...good!

********
Success!
********

Try out some pseudocode here!
/*************************************************************************
 * stack.c
 *
 * Implements a simple stack structure for char* s.
 ************************************************************************/

// for strdup() in the testing code
#define _XOPEN_SOURCE 500

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// the capacity of the stack
#define CAPACITY 10

typedef struct
{
    // storage for the elements in the stack
    char* strings[CAPACITY];

    // the number of elements currently in the stack
    int size;
}
stack;

// declare a stack (as a global variable)
stack s;

/**
 * Retrieves ("pops") the last ("top") element off of the stack, following
 * the "last-in, first-out" (LIFO) ordering of the data structure. Reduces
 * the size of the stack.
 */
char* pop(void)
{
    // TODO
}

/**
 * Implements some simple test code for our stack
 */
int main(void)
{
    // initialize the stack
    s.size = 10;

    printf("Pushing %i strings onto the stack...", CAPACITY);
    for (int i = 0; i < CAPACITY; i++)
    {    
        char str[12];
        sprintf(str, "%i", i);
        s.strings[i] = strdup(str);
    }
 
    printf("done!\n");

    printf("Popping everything off of the stack...");
    char* str_array[CAPACITY];
    for (int i = 0; i < CAPACITY; i++)
    {
        str_array[i] = pop();
    }
    printf("done!\n");

    printf("Making sure that pop() returned values in LIFO order...");
    for (int i = 0; i < CAPACITY; i++)
    {
        char str[12];
        sprintf(str, "%i", CAPACITY - i - 1);
        assert(strcmp(str_array[i], str) == 0);
        free(str_array[i]);
    }
    printf("good!\n");

    printf("Making sure that the stack is now empty...");
    assert(s.size == 0);
    printf("good!\n");

    printf("Making sure that pop() now returns NULL...");
    assert(pop() == NULL);
    printf("good!\n");

    printf("\n********\nSuccess!\n********\n");

    return 0;
}

Videos

study50 video thumbnail

Monday, Week 6

An introduction to data structures