COMP1511 Revision Stacks Sample Solutions

Revision Video: Introduction to Stacks and Queues

Revision Video: ADT Interface for Stacks and Queues

Revision Video: Stacks - Implementing the ADT

Revision Video: Stacks - Bracket balanced strings

Revision Video: Stacks - Reverse a sequence

Revision Video: Queues Implementation

Revision Video: Abstract Data Types - Introduction

Revision Video: Abstract Data Type (ADT) - Implementation

Revision Exercise: Practice inserting into a linked list stack!

Download push_item.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/21T3/activities/push_item/push_item.c .

Your task is to add code to this function in push_item.c:

struct item *push_item(struct item *stack, int data) {

    return NULL;
}

In this exercise you will be asked to implement the function: push_item.

You will implement the push_item function, which takes two arguments: a struct item *stack and an int data. The function should create a struct item and add it to the top of the stack.

Your function should work if passed in an empty stack and the autotest will construct a stack with your code.

What the main function does is scans numbers until end of input and pushes those items onto the stack in the order they were inputted.

dcc push_item.c -o push_item
./push_item
Enter items: 1 2 3
The stack was: 3 -> 2 -> 1 -> X
dcc push_item.c -o push_item
./push_item
Enter items: 5 6 12 34 -4 2 5
The stack was: 5 -> 2 -> -4 -> 34 -> 12 -> 6 -> 5 -> X
dcc push_item.c -o push_item
./push_item
Enter items:
The stack was: X

Assumptions/Restrictions/Hints

  • You may assume all inputs are valid. In other words, the stack passed in will be either a struct item * or NULL, and the data will be an int.

When you think your program is working you can use autotest to run some simple automated tests:

1511 autotest push_item
Sample solution for push_item.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct item {
    int data;
    struct item *next;
};

struct item *new_item(int data);

struct item *push_item(struct item *stack, int data) {

    struct item *new = new_item(data);
    new->next = stack;

    return new;
}

struct item *new_item(int data) {
    struct item *new = malloc(sizeof(struct item));
    new->data = data;
    new->next = NULL;

    return new;
}

/**
 * This is a simple main function that you can use to test your 
 * push_item function.
 * It will not be marked - only your push_item function will be marked.
 *
 * Note: The autotest does not call this main function!
 * It calls your push_item function directly.
 * Any changes that you make to this main function will not affect the autotests.
 */
int main(void) {

    printf("Enter items: ");
    struct item *stack = NULL;
    int data;
    while (scanf("%d", &data) == 1) {
        stack = push_item(stack, data);
    }

    printf("The stack was: ");
    struct item *curr = stack;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("X\n");
    
    return 0;
}