Thread: Queue stuct - Please Help

How can i make my own QUEUE struct in another program?

For instance, I am working on tty.c program that uses interupts and has a buffer that stores chars from the user, but I want to change these buffers in my "read" and "write" parts of tty.c to use Queues instead.

How you implement the Queue in this example is kind of dependant on how you implemented your read and write routines.

Code:

 int init_queue(Queue *q, int max_chars);  make a new empty queue, filling in *q
 int enqueue(Queue *q,char ch);     enqueue char ch on q, or return -1 if can't
 int dequeue(Queue *q);     dequeue a char and return it, or return -1 if can't
 int queuecount(Queue *q);  return # chars currently in queue

Those function prototypes should probably be in the header too.

>> I have also been told that I may have to use two structs, where one uses points to the other, in order to invoke this, but I am already lost so I think just setting up a Queue struct will be a good start.

Seems like you might want to look into linked lists for this sort of thing.

http://en.wikipedia.org/wiki/Linked_list
http://cslibrary.stanford.edu/103/
http://cslibrary.stanford.edu/104/

Binky!

Well for starters, how can i implement a Queue in tty.c that includes the queue.h library?

At the top of tty.c would I have something like

typedef struct MyQ{
Queue *q;
}MyQ;

and then in ttywrite() make calls to something like inChars->q.enqueue. Is this the correct logic?

-I'm just looking to use the Queue in queue.h and methods of queue.c in the seperate program tty.c as a struct so that I can make instances of that Queue.

Could you show me how this can be done? I am a C# / Java programmer just coming into C for the first time and I am having a tough time understanding how to do this.

queue.h

Code:

// struct declaration

typedef struct queue {      
  char ch[MAXCHARBUF];         /* char contain in queue */
  int front;                   /* front index of queue */
  int rear;                    /* rear index of queue */
  int count;                   /* current numbers of element in queue */ 
  int max;                     /* actually use length */
} Queue;

// function prototypes

int init_queue(Queue *q, int max_chars);  make a new empty queue, filling in *q
int enqueue(Queue *q,char ch);     enqueue char ch on q, or return -1 if can't
int dequeue(Queue *q);     dequeue a char and return it, or return -1 if can't
int queuecount(Queue *q);  return # chars currently in queue q

queue.c

Code:

//function definitions

#include "queue.h"

int init_queue(Queue *q, int max_chars)
{
	// perform stuff to initialize queue

	return 0;
}

int enqueue(Queue *q, char ch)
{
	// perform stuff to enqueue

	return 0;
}

char dequeue(Queue *q)
{
	// perform stuff to dequeue

	return 0;
}

int queuecount(Queue *q)
{
	// return count in queue
	return 0;
}

Note I changed dequeue to return the type in your queue, char. But, in implementing your queue, this note from sgi stl docs are sort of interesting (kinda, you only have chars in your queue)

Originally Posted by http://www.sgi.com/tech/stl/queue.html

[3] One might wonder why pop() returns void, instead of value_type. That is, why must one use front() and pop() to examine and remove the element at the front of the queue, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the front element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use front() to inspect the value at the front of the queue.

To use you queue in some other code

somefile.c

Code:

// new functions

#include "queue.h"
#include "somefile.h"

int ttywrite()
{
        Queue q;
	int num, i;

	init_queue(&q);

	enqueue(&q, 'a');
	enqueue(&q, 'b');
	enqueue(&q, 'c');
	enqueue(&q, 'd');

	num = queuecount(&q);
	for(i = 0; i < num; ++i)
	{
		printf("%c", dequeue(&q));
	}
	
	// prints 'abcd'

	return 0;
}