4
\$\begingroup\$

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");
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I've just simply edited if ((*head) == NULL && (*tail) == NULL){...} to if ((*head) == NULL){...} that would enable the snippet update new tail in enqueue() function. May I wish an elaborated discussion on bug and heads and tails section please. \$\endgroup\$ – ph03n1x Jul 22 '16 at 6:49
  • \$\begingroup\$ what I've noticed a queue and stack are same however they differ in en-queuing and pushing order. Other than can't they be printed and popped/de-queued in same order ? _first man in the queue is head and last book in a stack is the head, isn't it? _ however, if I'm wrong please give me some elaborated discussion. \$\endgroup\$ – ph03n1x Jul 22 '16 at 7:04
  • \$\begingroup\$ @ph03n1x try push_node(&Q_head, 3);enqueue_node(&Q_head, 1, &Q_tail) with your current fix. \$\endgroup\$ – forsvarir Jul 22 '16 at 7:12
  • 1
    \$\begingroup\$ @ph03n1x The structure of a stack and queue is very similar and it's not uncommon for collections to support 'add_end', 'add_front' type functions however, whilst I might model a linked_list that supported these methods I wouldn't expose them that way for my stack and queue. When I make the decision to use a queue, it's usually because I want something optimized for a FIFO approach, rather than something that is flexible. However, opinions can obviously differ. \$\endgroup\$ – forsvarir Jul 22 '16 at 7:22
  • \$\begingroup\$ Well, in that case we can declare stack head and queue head/tail in global territory that our user can only give the values and rest of the works will be done in push_node(int value); and enqueue_node(int value); functions. Anyway, where can I see the Queue template source/ implementation code of C++ STL ? Please give me a link of source. \$\endgroup\$ – ph03n1x Jul 22 '16 at 9:07
2
\$\begingroup\$

@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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.