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

Stack and Queue Linked List Implementations

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

Problem

I'm relatively new to C as a language, but I wouldn't call myself a beginner. That being said, I don't believe my C "coding style," so to speak, is particularly developed. Also, I'm new to error handling in C as well.

stack.c

#include 
#include 

typedef struct node {
    int val;
    struct node* next;
} node_t;

typedef struct stack {
    struct node* head;
} stack_t;

stack_t* create_list(void)
{
    stack_t* stack = malloc(sizeof *stack);
    if (stack != NULL) {
            stack->head = NULL;
    }
    return stack;
}

void push(stack_t* list, int val)
{
    node_t* newnode = malloc(sizeof *newnode);
    if (newnode != NULL) {
            newnode->val = val;
            newnode->next = list->head;
    }
    list->head = newnode;
}

int pop(stack_t* list)
{
    int val = list->head->val;
    node_t* next = list->head->next;
    free(list->head);
    list->head = next;
    return val;
}

void destroy_list(stack_t* list)
{
    do {
            node_t* head = list->head;
            node_t* next = head->next;
            free(head);
            list->head = next;
    } while (list->head);
    free(list);
}

void foreach(stack_t* list, int (*func)(const int))
{
    node_t* curr = list->head;
    do {
            curr->val = func(curr->val);
            curr = curr->next;
    } while(curr);
}

int print_val(const int val)
{
    printf("value: %d\n", val);
    return val;
}

int main(int argc, char* argv[])
{
    printf("creating list\n");
    stack_t* list = create_list();
    printf("pushing value 2\n");
    push(list, 2);
    printf("top value: %d\n", list->head->val);
    printf("pushing value 5\n");
    push(list, 5);
    printf("top value: %d\n", list->head->val);
    printf("iterating top-down\n");
    foreach(list, print_val);
    printf("popping top value\n");
    int popped = pop(list);
    printf("popped: %d\n", popped);
    printf("top value: %d\n", list->head->val);
    destroy_list(list);
    return 0;
}


queue.c

```
#include
#include

type

Solution

-
Naming

stack_t * create_list(); and queue_t create_list() are misnomers. To begin with, you cannot use both of them in the same applications. Besides, it discloses unnecessary details of the implementation, and really confuses the reviewer.

-
DRY

The common (list related) code shall be factored out into a list.c with the interfaces in list.h; stack.c and queue.c should use the exported interfaces, for example,

void destroy_stack(stack_t * stack)
{
    destroy_list(stack->head);
}


-
Empty object is valid

destroy_list and foreach suffer the common problem: they presume that the list is not empty. An attempt to apply them to an empty object results in a null-pointer dereference. Use while() {} instead.

-
enqueue is implemented correctly, kudos.

Code Snippets

void destroy_stack(stack_t * stack)
{
    destroy_list(stack->head);
}

Context

StackExchange Code Review Q#162453, answer score: 3

Revisions (0)

No revisions yet.