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 aStack* 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 callmalloc
, so that one could define an instance ofStack
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 usevoid*
sincevoid*
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();
}
std::stack
from C++ as a reference interface. – glampert Nov 3 '14 at 22:29