Designing stack and queue from scratch in C

Question

As a beginner and curious guy I'm interested in implementing data structures and algorithms from scratch. Here's my implementation of Stack and Queue, the most fundamental data structures.

Are there are any mistakes/ memory leaks in the code that I have missed? How I can improve my implementation.

#include<stdio.h>
#include<stdlib.h>


typedef struct NODE {
    int data;
    struct NODE *next_node;

    } NODE;


NODE *check_queue(NODE *head);
NODE *check_stack(NODE *head);
void push_node(NODE **head, int value);
void enqueue_node(NODE **head, int value, NODE **tail);
int  pop(NODE **s_head);
int  dequeue(NODE **q_head);
void print_stack(NODE *head);
void print_queue(NODE *head);
void free_memory(NODE **head);



int main(){

    NODE *Q_head = NULL;
    NODE *Q_tail = NULL;
    NODE *S_head = NULL;
    /*operations here*/

    return 0;
}

/*----- check functions for queue and stack if empty-----------*/    

NODE *check_queue(NODE *head){
    return head;
}


NODE *check_stack(NODE *head){
    return head;
}

/*--------------------------------------------------------------*/



void push_node(NODE **head, int value){

    NODE *cache;
    cache = (NODE *) malloc(sizeof(NODE));
    cache->data = value;
    /*first commit / allocate a new head*/

    if ((*head) == NULL) {
        cache->next_node = NULL;
        (*head) = cache; /*assign the cache to head head*/
    }

    else {
        /*point to the previous head*/
        cache->next_node = (*head);
        (*head) = cache;
    }
}


void enqueue_node(NODE **head, int value, NODE **tail) {

    NODE *cache;
    cache = (NODE *) malloc(sizeof(NODE));
    cache->data = value;
    cache->next_node = NULL;

    if ((*head) == NULL && (*tail) == NULL) {
        (*head) = cache; /*assign the cache to head*/
        /*now assign tail the job as a cachet head and extends the queue*/
        (*tail) = (*head);
    }

    else {
        /*now tail is the representative of head and extened the queue*/
        (*tail)->next_node = cache;
        (*tail) = cache;
    }
}


int pop(NODE **s_head){

    if(check_stack((*s_head)) == NULL){
        printf("Stack is empty ! ! !\n");
        return -1;
    }

    else {
        /*put next head into a cache, free present head, take next head to present head*/
        NODE *cache ;
        cache = (*s_head)->next_node;
        int popped_value = (*s_head)->data;
        free((*s_head));
        (*s_head) = cache;
        return popped_value;
    }
}



int dequeue(NODE **q_head){

    if(check_queue((*q_head)) == NULL){
        printf("queue is empty ! ! !\n");
        return -1;
    }

    else {
        /*ditto of stack as we've got queue sequence*/

        NODE *cache ;
        cache = (*q_head)->next_node;
        int dequeued_value = (*q_head)->data;
        free((*q_head));
        (*q_head) = cache;
        return dequeued_value;
    }
}





void print_stack(NODE *head){

    while (head) {

        printf(" %d \n", head->data);
        printf(" |\n");
        head = head->next_node;
    }

    /*for further assurance*/
    if ( head == NULL){
        printf("NULL\n");
    }

    printf("\n");
}






void print_queue(NODE *q_head){

    while (q_head) {


        // printf(" %d  -> ", head->next_node);
        printf(" %d  -> ", q_head->data);
        q_head = q_head->next_node;
    }
    /*for further assurance*/
    if ( q_head == NULL){
            printf("NULL\n");
    }

    printf("\n");
}


void free_memory(NODE **head){
    NODE *cache_head;

    while ((*head)) {

        /*assign next head to the cache*/
        cache_head = (*head)->next_node;
        free((*head));
        (*head) = cache_head;
    }

    printf("memory release complete !!! \n");
}

Answer 1

casting and malloc

Unnecessary casting is generally frowned upon. malloc returns a void*, so you don't need to cast it when you're assigned it.

cache = (NODE *) malloc(sizeof(NODE));

can just be

cache = malloc(sizeof(NODE));

Bug

You've got a bug in your dequeue function. It doesn't update tail, which means that if you empty the queue, then start adding to it again you get errors.

enqueue_node(&Q_head, 1, &Q_tail);
printf("%d\n", dequeue(&Q_head));
enqueue_node(&Q_head, 1, &Q_tail);
printf("%d\n", dequeue(&Q_head));

Results in:

1
queue is empty ! ! !
-1

naming

It's a little odd that your push/enqueue methods have have a _node postfix, but your pop/dequeue methods don't. I'd pick one and stick to it.

heads and tails

I'd rather see the head and tail of the queue wrapped up together in a queue structure. This means that you only have to pass one parameter (the queue) into your enqueue/dequeue. It also means that if you decide to change the way you implement the queue, your clients aren't impacted.

Are Queues Stacks?

As you've implemented it, it's possible to call stack functions on queue nodes and queue functions on stack nodes. Is this really desirable? If not, then making the change above to introduce a QUEUE structure that wraps a QNODE head and QNODE tail would mean that you would at least have some level of type safety and the compiler would warn you if you tried to call dequeue on your stack.

Answer 2

@forsvarir covered most of the important points already, but I have this additional comment:

Useless functions

I found these functions to be useless:

NODE *check_queue(NODE *head){
    return head;
}

NODE *check_stack(NODE *head){
    return head;
}

All these functions do is return the argument passed in. I can sort of see what you were trying to do, though. You were probably trying to write functions to check if the queue/stack are empty. But those functions should return bools, not pointers:

bool is_stack_empty(const NODE *head)
{
    return head == NULL;
}
bool is_queue_empty(const QUEUE *q)
{
    return q->head == NULL;
}