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

    Join Date
    Jan 2014
    Posts
    134
    Rep Power
    1

    Implementing Queue with array of structures


    Here's the code I am struggling with:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "queue.h" //it contains prototypes for this file
    
    struct part {
    	int data;
    }; //the linked list
    
    struct part *queue;
    int front = 0, rear = 0;
    
    static void terminate(const char *message)
    {
    	printf("%s\n", message);
    	exit(EXIT_FAILURE);
    } //this would create a terminating message in case of failure
    
    void create(int size)
    {
    	queue = malloc(sizeof(struct part) * size);
    	if (queue == NULL)
    		terminate("Error in create; queue could not be created");
    } // this creates a new blank queue
    
    void destroy(void)
    {
    	free(queue);
    } // this destroys a provided queue
    
    void push(int p)
    {
    	extern int size;
    	if (front == size) {
    		terminate("Queue is full\n");
    	}
    	queue[front++].data = p; 
    } // it pushes a value into the top of the queue
    
    void pop(void)
    {
    	if (front == rear)
    		terminate("Error in pop: queue is empty.");
    	rear++;
    } // it deletes a value from the bottom of the queue
    
    int peek(int pos)
    {
    	if (pos == 0) {
    		return queue[rear].data;
    	}
    	
    	else if (pos == 1) {
    		return queue[front].data;
    	}
    	return 0;
    } // this takes a peek at either the bottom or the top of the queue(0 = bottom, 1 = top)
    I have commented what a function is about at the end of each function. I think I have a problem with my peek function. Garbage integers are printed. I would be glad if someone could help. Thanks in advance!
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,895
    Rep Power
    481
    The code compiles to an object without warnings. (After removing #include"queue.h" or providing a dummy file.)

    This comment is incorrect because you're working with an array not a linked list.
    }; //the linked list


    Why would you not supply a main program that exhibits the problem?


    You've got extern size. Maybe there's some way you've fixed that in queue.h, although I would think that create should set the value.


    In peek you need to return queue[front-1]
    Code:
    int peek(int pos) {
      if (0 == pos)
        return queue[rear].data;
      if (1 == pos)
        return queue[front-1].data;
      return 0;
    } // this takes a peek at either the bottom or the top of the queue(0 = bottom, 1 = top)

    Comments on this post

    • arman.k.devshed agrees
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    This type of queue seems limited. It could be enhanced by making it a circular array. Both front and rear would wrap around back to zero once they reached "size".

    Your usage of "front" and "rear" is reversed. Front means the first element of a queue, such as C++ queue::front == first element of a queue. Rear or back == last element of a queue (the last one added), such as C++ queue::back.

    Switching the index names to front (first element) and back (last element added), you could waste one member and consider the circular array to be full when ((back+1)%size) == front, or you could maintain a count for the number of members in the queue, and consider the queue to be full when count == size.
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    134
    Rep Power
    1
    Originally Posted by b49P23TIvg
    The code compiles to an object without warnings. (After removing #include"queue.h" or providing a dummy file.)

    This comment is incorrect because you're working with an array not a linked list.
    }; //the linked list


    Why would you not supply a main program that exhibits the problem?


    You've got extern size. Maybe there's some way you've fixed that in queue.h, although I would think that create should set the value.


    In peek you need to return queue[front-1]
    Code:
    int peek(int pos) {
      if (0 == pos)
        return queue[rear].data;
      if (1 == pos)
        return queue[front-1].data;
      return 0;
    } // this takes a peek at either the bottom or the top of the queue(0 = bottom, 1 = top)
    Yes sorry that comment was wrong, I was building this based on another program, so forgot to modify that comment. And making it [front-1] fixed the problem! Thanks a lot sir!

    As for extern size, I was not sure how to make the create function set the value. I can't make it static after being passed the value from the create function call in main. So I need to pass the value each time I call push. Any way around this?
  8. #5
  9. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    134
    Rep Power
    1
    Originally Posted by rcgldr
    This type of queue seems limited. It could be enhanced by making it a circular array. Both front and rear would wrap around back to zero once they reached "size".

    Your usage of "front" and "rear" is reversed. Front means the first element of a queue, such as C++ queue::front == first element of a queue. Rear or back == last element of a queue (the last one added), such as C++ queue::back.

    Switching the index names to front (first element) and back (last element added), you could waste one member and consider the circular array to be full when ((back+1)%size) == front, or you could maintain a count for the number of members in the queue, and consider the queue to be full when count == size.
    Okay I will be trying your suggestion! Thank you :)
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    Originally Posted by arman.k.devshed
    Okay I will be trying your suggestion!
    On a side note, if you want the peek functions to be quicker, then pre-increment the back index on pushback(), and post-increment the front index on popfront(). Then peek can just use the existing front or back indexes.

    I usually init back to size-1, and front to 0, knowing that back will pre-increment to 0 (wrap around), along with using a count (instead of comparing indexes to check for empty, non-empty, or full).

IMN logo majestic logo threadwatch logo seochat tools logo