Implement a stack using a linked list

Question

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

1. 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.
2. 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.
3. The stack_init function does not call malloc, so that one could define an instance of Stack locally, as in the test methods below.
4. 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 <stdbool.h>
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 <stdlib.h>
#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 <assert.h>
#include "stack.h"
static void test_null_stack_should_fail_to_init() {
 // arrange
 Stack* stack = NULL;
 // act
 assert(!stack_init(stack));
}
static void test_empty_stack() {
 // arrange
 Stack stack;
 // act
 assert(stack_init(&stack));
 assert(stack_delete(&stack));
}
static void test_push_then_pop() {
 // arrange
 Stack stack;
 stack_init(&stack);
 stack_push(&stack, 1);
 stack_push(&stack, 2);
 stack_push(&stack, 3);
 int data;
 // act
 assert(stack_pop(&stack, &data));
 assert(data == 3);
 assert(stack_pop(&stack, &data));
 assert(data == 2);
 assert(stack_pop(&stack, &data));
 assert(data == 1);
 assert(!stack_pop(&stack, &data));
 assert(stack_delete(&stack));
}
static void test_push() {
 // arrange
 Stack stack;
 stack_init(&stack);
 stack_push(&stack, 1);
 stack_push(&stack, 2);
 stack_push(&stack, 3);
 // act
 assert(stack_delete(&stack));
}
int main() {
 test_null_stack_should_fail_to_init();
 test_empty_stack();
 test_push_then_pop();
 test_push();
}

• glampert: You're on the right track, but you will probably want to add more methods and keep track of the stack size before it is fully usable. Take std::stack from C++ as a reference interface.

Answer 1

• 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.

• Stack Exchange Broke The Law: Disagree with point 3; it abstracts implementation details from clients. Relatedly, it makes the client code easier to read.
• vnp: Let's agree to disagree. Abstracting implementation is a good strategy as long as it serves a purpose. Abstraction for the sake of abstraction is not.
• Stack Exchange Broke The Law: Suppose you were to change it to Node*... and then in three months you want to add a size field?

Answer 2

1. Unclear why if (self == NULL) in 2 of the 4 functions. Suggest none or all 4.

2. A comment in stack.h concerning the meaning of the return value would be useful. Assume user of Stack does not have access to stack.c. Not clear is success happens with true or false.

3. Using Node and node is a bit too similar - differentiating only on 1 letter case.

4. Maybe want to add a stack_empty() query?

5. typedef struct Node is not needed in stack.h. Suggest moving to stack.c

6. Maybe allow stack_pop(Stack* self, int* data) where data is NULL to pop without saving.