CS 210 Queue Code
Queue Algorithms, Part 2
This set of algorithms deals with queues implemented using linked lists.
Error is a routine that takes a type of error as an
argument and does whatever is appropriate.
Linked Sequential Queues
These routines assume a record as described below and two pointer variables
front and rear, initialized to NULL.
The routine createnode() sets its argument to be a NULL pointer
when there is no more space
struct Q {
int stuff; /* we don't care exactly what this is
struct Q *next;
};
void addq(int item) {
/* this adds item to the rear of the queue */
struct Q *x;
1. x=createnode(x);
2. if (x != NULL) { /* this is the check for a 'full' queue */
3. x->stuff = item;
4. x->next = NULL;
5. if (rear == NULL) /* first one */
6. rear = front = x;
7. else {
8. rear->next = x;
9. rear = x;
10. }
}
11. else
12. error(queue_full);
} /* addq */
int getq() {
/* this returns the item at the front of the queue */
int x;
struct Q *y;
1. if (front != NULL) {
2. y = front;
3. front = front->next;
4. x=y->thing;
5. free(y);
6. return(x);
}
7. else
8. error(queue_empty);
} /* getq */
Linked Circular Queues
There are no algorithms here since the reason we built circular
sequential queues was to reuse the memory.
The fact that we get new space as needed and return it in linked linear
queues makes this unnecessary.