HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcMinor

Implement a stack using a linked list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
stackimplementusinglistlinked

Problem

I am to implement a stack in C using a linked list. My code is below. My design:

  • I use stack_ prefix to each function, and each function has a Stack* self pointer. This is similar to object-oriented languages’ bundling of data and methods. I do not know how idiomatic this is in C.



  • Each function returns a bool indicating success or failure. A more detailed implementation would have error codes and messages. I do not know how idiomatic this is in C.



  • The stack_init function does not call malloc, so that one could define an instance of Stack locally, as in the test methods below.



  • I used int as the type of data, but this could be modified for other types. I did not use void since void would lose type safety.



stack.h

#ifndef STACK_H_
#define STACK_H_

#include 

typedef struct Node {
  int data;
  struct Node* next;
} Node;

typedef struct {
    Node* root;
} Stack;

bool stack_init(Stack* self);
bool stack_delete(Stack* self);
bool stack_pop(Stack* self, int* data);
bool stack_push(Stack* self, int data);

#endif  // STACK_H_


stack.c

#include 
#include "stack.h"

bool stack_init(Stack* self) {
  if (self == NULL) {
    return false;
  }

  self->root = NULL;
  return true;
}

bool stack_delete(Stack* self) {
  Node* next;
  while (self->root != NULL) {
    next = self->root->next;
    free(self->root);
    self->root = next;
  }

  return true;
}

bool stack_push(Stack* self, int data) {
  if (self == NULL) {
    return false;
  }

  Node* node = malloc(sizeof(Node));
  if (node == NULL) {
    return false;
  }

  node->data = data;
  node->next = self->root;
  self->root = node;

  return true;
}

bool stack_pop(Stack* self, int* data){
  Node* root = self->root;
  if (root == NULL) {
    return false;
  }

  *data = root->data;
  self->root = root->next;
  free(root);

  return true;
}


stack_test.c

```
#include
#include "stack.h"

static void test_null_stack_should_fail_to_init() {
// arrange
Stack* stack = NUL

Solution

-
stack_delete only returns true. If a return value from a function carries no information, better make it void.

-
There is no consistency in testing parameters. Some functions test for self not being null, other directly proceed to calculating self->root.

-
The Stack existence is only justifiable if it has more data members than just root. As @glampert mentioned in comments, tracking size is one of the candidates. On the other hand, abandoning Stack for good, and letting client manage the root, as in

Node * stack_push(Node * root, data);
....

root = stack_push(root, data);


is also a viable strategy.

-
It would be nice to provide a non-destructive top() interface to access the root data. There is even a popular belief that a pop-like function should only pop an element from the top of stack (as opposed to pop element and return data); in this school of thought top() is a must.

Code Snippets

Node * stack_push(Node * root, data);
....

root = stack_push(root, data);

Context

StackExchange Code Review Q#68798, answer score: 5

Revisions (0)

No revisions yet.