5
\$\begingroup\$

I am studying data structures and I have implemented a stack using a linked list.

stack.h

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

typedef char StackElement;

typedef struct stack_CDT *Stack;

Stack stack_init();

void stack_destroy(Stack s);

bool stack_is_empty(Stack s);

void stack_push(Stack s, StackElement elem);

StackElement stack_pop(Stack s);

#endif

stack.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "stack.h"

typedef struct node {
    StackElement data;
    struct node *next;
} Node;

Node *node_create(StackElement data)
{
    Node *new = malloc(sizeof *new);
    new->data = data;
    new->next = NULL;
    return new;
}

void node_insert(Node **node_ref, Node *new)
{
    if (new == NULL)
        return;

    new->next = *node_ref;
    *node_ref = new;
}

void node_delete(Node **node_ref)
{
    if (*node_ref == NULL)
        return;

    Node *next = (*node_ref)->next;
    free(*node_ref);
    *node_ref = next;
}

void list_delete(Node **head_ref)
{
    while ((*head_ref) != NULL)
        node_delete(head_ref);
}

typedef struct stack_CDT {
    Node *top;
} StackCDT;

StackCDT *stack_init()
{
    StackCDT *new = malloc(sizeof *new);
    new->top = NULL;
    return new;
}

void stack_destroy(StackCDT *s)
{
    list_delete(&(s->top));
    free(s);
}

bool stack_is_empty(StackCDT *s)
{
    return s->top == NULL;
}

void stack_push(StackCDT *s, StackElement elem)
{
    Node *new = node_create(elem);
    node_insert(&(s->top), new);
}

StackElement stack_pop(StackCDT *s)
{
    if (stack_is_empty(s)) {
        fprintf(stderr, "Can't pop element from stack, stack is empty.\n");
        exit(1);
    }

    StackElement elem = s->top->data;
    node_delete(&(s->top));
    return elem;
}

stacktest.c

#include <stdio.h>
#include <string.h>
#include "stack.h"

#define MAX_STR_LEN 100

void stacktest()
{
    printf("Enter a string(not more than %d characters): ", MAX_STR_LEN);
    char input[MAX_STR_LEN + 1];    
    fgets(input, sizeof input, stdin);
    char *pos;
    if ((pos = strchr(input, '\n')) != NULL)
        *pos = '\0';

    Stack stack = stack_init();
    for (char *c = input; *c; c++)
        stack_push(stack, *c);

    printf("Popped characters are: ");
    while (!stack_is_empty(stack))
        printf("%c", stack_pop(stack));
    printf("\n");

    stack_destroy(stack);
}

int main()
{
    stacktest();
    return 0;
}

Is my implementation all right?

\$\endgroup\$
2
\$\begingroup\$

Generally looks good. Few comments:

  • Node is not used by the client; it is a stack implementation detail, so node_create, node_insert and node_delete should be static.

  • I prefer function returning results rather than void modifying its argument. Consider

    Node * node_insert(Node * ref, Node * new);
    Node * node_delete(Node * ref);
    

    It removes one level of indirection, and simplifies the implementation.

  • An utility function such as stack_pop shall not print anything. In any case, it shall convey the error condition to the caller (an unconditional exit is a bit harsh). Consider setting errno, for example.

\$\endgroup\$
  • \$\begingroup\$ Well, an unconditional abort() on encountering an "impossible" situation, or violation of the contract, is the only useful thing. Whether poping an empty stack is a logic error, and should be treated as such? Yes! Assert in debug-mode, ignore in release-mode: en.cppreference.com/w/cpp/container/vector/pop_back \$\endgroup\$ – Deduplicator Nov 10 '15 at 18:49
  • \$\begingroup\$ @Deduplicator No. Even NO. assert is fine in the application, and is absolutely unsuitable in a library code. The library lacks the context, and has no right to impose a policy. The only thing it may (and shall) do is to inform the caller. \$\endgroup\$ – vnp Nov 10 '15 at 19:03
  • \$\begingroup\$ Say that to the standard committee: If you violate basic preconditions, it's on your head. Hopefully, it leads to a fast crash. Debug-mode makes sure of that, as far as reasonably feasible. Also, remember that unexercised code is broken code, and how do you want to check reasonable behavior on logic-error, when you weed them out the moment you first trigger them? \$\endgroup\$ – Deduplicator Nov 10 '15 at 19:19
4
\$\begingroup\$

No, your implementation is broken:

You forgot to check whether allocation succeeded.


Reviewing your code, you are going way overboard following the "small methods"-mantra in your library-code:

While the Single responsibility principle means every function should do one thing, and only one thing, the size of each task should be properly chosen.

Too little, and the function isn't a useful abstraction, using, writing and remembering it takes more effort than it saves.
(The performance-cost may be negligible (or even non-existent), if it is inlined. Consider marking it static to promote inlining and avoid exporting.)

Too much, and reusability and composability suffer.


Header:

  1. I would avoid a typedef for the element-type. What does it buy you?

  2. Using an opaque pointer is a good idea allowing you to replace the implementation with something more performant later. So, well done there.

  3. Consider leaving the parameter-name out of the declaration when it doesn't make it more descriptive.

  4. You should add a variation on stack_push which signals success, so a caller can opt in to handling failure gracefully:

    bool stack_tryPush(Stack, StackElement);
    
  5. Some more useful additions:

    StackElement stack_peek(Stack);
    StackElement stack_replace(Stack, StackElement);
    

Sourcefile:

  1. You should re-order your includes: Always include the header you are implementing first, then all other headers, sorted for consistency (use the IDE's sorting-macro).
    That way, you will know that your header is self-sufficient and you didn't forget a crucial dependency.

  2. There's abort() for abnormal termination. Consider writing a helper-function if you need to output an error-message and abort in multiple places:

    static void die(const char* message);
    
  3. All your internal functions should not have external linkage, for performance and correctness reasons: Mark them inline.

  4. Putting next first is more common, and possibly slightly more efficient. Also, for a single value value is more idiomatic than data.

  5. Is there any reason why your typedef-name and struct-tag aren't quite equal? That's ittitating.

  6. node_create is a waste: It's literally more work to read, write, and use it than leaving the single use inline.
    As a rule of thumb, extracting 2 lines into their own function is a net loss of readability. Exceptons are often-used pieces of code.

    Actually, that can be generalized to all your internal functions, with the possible exception of node_delete, which is marginal.

  7. There are two kinds of precondition-checks:

    1. Sanity checks, verifying that the programs logic is sane. These are normally disabled in a release build for performance reasons, and use assert().
    2. Tests of untrusted input. How far you can/should/must trust an API's user must be decided in each case. It's your task as API-designer to decide how much you should penalize your users to catch egregious abuse even in release-mode, and whether there's also a debug-mode.
      But there's no excuse for making your internal helper-functions re-assert preconditions even in release-mode.
  8. As you are using C99 (see <stdbool.h>), you can use compound-literals to set all members of a struct-type comfortably even after initialization.

    void stack_push(StackCDT *s, StackElement value)
    {
        Node *new = malloc(sizeof *new);
        *new = (Node){s->top, value};
        if(!new) die("Failed to allocate a new node.");
        s->top = new;
    }
    

Testprogram:

  1. return 0; is implicit in main since C99.
  2. Any reason for extracting your whole main into a different function?
\$\endgroup\$
  • \$\begingroup\$ I used typedef for the stack element to make the stack generic. If I want to change the type of the stack element, then I can just change the typedef in the header file \$\endgroup\$ – In78 Nov 10 '15 at 19:09
  • \$\begingroup\$ Well, that's in itself a good idea. Though you know you are fighting the language there, and you can only ever have one variety of your stack in any program? C++ solves that with templates... \$\endgroup\$ – Deduplicator Nov 10 '15 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.