stack.c

Jonas Altrock ew20b126@technikum-wien.at

The whole source file stack.c.

Back to postfix.c

/* */

Include C-library for allocation of memory.

#include <stdlib.h>

Include our stack header file stack.h.

#include "stack.h"

A linked-list stack

This simply linked list structure has nodes that each have a value and a pointer to the next node in the list. The last node has a NULL pointer as the next field.

In this exercise only numbers are important, so the nodes only hold integers as values. In a more sophisticated stack implementation, we could use a void * universal pointer type, or even a union for different value types.

The struct stack consist only of the pointer to the top element, which is the head of the linked list.

typedef struct stack_node {
    struct stack_node *next;
    int value;
} stack_node_t;

struct stack {
    stack_node_t *top;
};

stack_create()

Allocate a stack structure and return a handle for outside code.

stack_handle_t stack_create() {
    struct stack *s = calloc(1, sizeof(struct stack));
    return s;
}

stack_push()

Add a value on top of the stack.

void stack_push(stack_handle_t s, int v) {
    stack_node_t *n = malloc(sizeof(stack_node_t));
    n->next = s->top;
    n->value = v;
    s->top = n;
}

stack_pop()

Remove to value on top of the stack.

int stack_pop(stack_handle_t s) {
    stack_node_t *n = s->top;

Normally it would be a serious error to expect a value when popping from an empty stack, but for this exercise a 0 is ok.

    if (n == NULL) {
        return 0;
    }

Set the top pointer of the stack to the next node and free the old node memory.

    s->top = s->top->next;
    int v = n->value;
    free(n);
    return v;
}

stack_destroy()

Free all dynamic memory used by the stack.

void stack_destroy(stack_handle_t s) {
    stack_node_t *n;

    while (s->top != NULL) {

Remember top pointer, then pop node by advancing to next.

        n = s->top;
        s->top = s->top->next;

Free the node memory.

        free(n);
    }

Free the stack

    free(s);
}

stack_top

Get the value at the top of the stack.

int stack_top(stack_handle_t s) {
    stack_node_t *n = s->top;
    return n->value;
}

stack_len()

Count the elements in the stack.

int stack_len(stack_handle_t s) {
    int l = 0;
    stack_node_t *n = s->top;

    while (n != NULL) {
        l += 1;
        n = n->next;
    }

    return l;
}