#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    108
    Rep Power
    1

    Implementing Queue


    Here's the queue ADT I have prepared.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "queue.h" // it contains the prototypes. and also contains this:
                       // typedef struct queue_type *queue; 
    
    struct node {
    	void* data;
    	struct node *next;
    }; //the linked list
    
    struct queue_type {
    	struct node *top;
    	struct node *bottom;
    }; //it has links to the top and bottom of the queue
    
    static void terminate(const char *message)
    {
    	printf("%s\n", message);
    	exit(EXIT_FAILURE);
    } //this would create a terminating message in case of failure
    
    queue create(void)
    {
    	queue s = malloc(sizeof(struct queue_type));
    	if (s == NULL)
    		terminate("Error in create; queue could not be created");
    	s->top = NULL;
    	s->bottom = NULL;
    	return s;
    } // this creates a new blank queue
    
    void destroy(queue s)
    {
    	make_empty(s);
    	free(s);
    } // this destroys a provided queue
    
    void make_empty(queue s)
    {
    	while(!is_empty(s))
    		pop(s);
    } // this empties a provided queue
    
    bool is_empty(queue s)
    {
    	return s->top == NULL;
    } // this checks whether the queue is empty
    
    bool is_full(queue s)
    {
    	return false;
    } // this would always return false. It was created for another program, still didn't remove it
    
    void push(queue s, void *p)
    {
      struct node *temp = malloc(sizeof(struct node));
      if (temp == NULL)
        terminate("Error in push: couldn't allocate memory.");
    
      temp->data = p;
      
      if (s->top == NULL) {
      	s->top = temp;
      	temp = temp->next;
      	s->bottom = s->top;
       }
      else {
      	s->top = temp;
      	temp = temp->next;
      }
    } // it pushes a value into the top of the queue
    
    void *pop(queue s)
    {
      if (is_empty(s))
        terminate("Error in pop: stack is empty.");
    
      struct node *var = s->bottom;
      var = var->next;
      free(s->bottom);
      s->bottom = var;
    } // it deletes a value from the bottom of the queue
    
    void *peek(queue s, int pos)
    {
    	struct node *old_top;
    	struct node *new_node2;
    	char *i;
    	i = malloc(100);
    	
    	if (pos == 0) {
    		new_node2 = s->bottom;
    		i = new_node2->data;
    		free(new_node2);
    		return i;
    	}
    	
    	else if (pos == 1) {
    		old_top = s->top;
    		i = old_top->data;
    		free(old_top);
    		return i;
    	}
    	
    	return 0;
    } // this takes a peek at either the bottom or the top of the queue(0 = bottom, 1 = top)
    The push function works perfectly, as I can use the peek function and check that it returns the correct values. But after using pop, the peek function seems to print garbage. So the problem is probably with pop. Hope someone would look into the problem. I find linked lists quite troublesome for some reason. Have been trying this queue algorithm for the past 10 days :(
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,367
    Rep Power
    1870
    Your peek function calls malloc and free unnecessarily.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    108
    Rep Power
    1
    Originally Posted by salem
    Your peek function calls malloc and free unnecessarily.
    Are you trying to say I should directly return whatever is at s->bottom and s->top ?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    108
    Rep Power
    1
    But it seemed to work fine before I called pop.
  8. #5
  9. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,367
    Rep Power
    1870
    Originally Posted by arman.k.devshed
    But it seemed to work fine before I called pop.
    But in doing so, it trashes the rest of queue data structure.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    108
    Rep Power
    1
    Originally Posted by salem
    But in doing so, it trashes the rest of queue data structure.
    Okay so here's my new pop function:
    Code:
    void *peek(queue s, int pos)
    {
    	if (pos == 0) {
    		return s->bottom->data;
    	}
    	
    	else if (pos == 1) {
    		return s->top->data;
    	}
    	
    	return 0;
    }
    It prints garbage too. My debugger shows there is a segmentation fault after I try to peek immediately after popping. :(
  12. #7
  13. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,367
    Rep Power
    1870
    > struct node *next;
    In several places, you need to make this NULL.
    Otherwise, you just fall off the end of the list and into garbage (otherwise known as a segfault).

    Comments on this post

    • arman.k.devshed agrees
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    108
    Rep Power
    1
    Originally Posted by salem
    > struct node *next;
    In several places, you need to make this NULL.
    Otherwise, you just fall off the end of the list and into garbage (otherwise known as a segfault).
    Thanks a zillion! I forgot to do that, I actually had to check up my previous chapters.. be away from learning for a week, and poof! You forget everything :|

    Here's my push function now:
    Code:
    void push(queue s, void *p)
    {
      struct node *temp = malloc(sizeof(struct node));
      if (temp == NULL)
        terminate("Error in push: couldn't allocate memory.");
    
      temp->data = p;
      
      if (s->top == NULL) {
      	s->top = temp;
      	s->top->next = NULL;
      	s->bottom = s->top;
       }
      else {
      	s->top->next = temp;
      	s->top = temp;
      	s->top->next = NULL;
      }
    }

IMN logo majestic logo threadwatch logo seochat tools logo