CS 210 Queue Code
Queue Algorithms, Part 1
This set of algorithms deals with queues implemented using arrays.
Error is a routine that takes a type of error as an
argument and does whatever is appropriate.
Linear Sequential Queues
These routines assume an array of integers, numbered from 1 to QSIZE
named Q and two variables front and rear, both initialized to -1.
void addq(int item) {
/* this adds item to the rear of the queue */
1. if (!is_q_full()) {
3. Q[++rear] = item;
}
4. else
5. error(queue_full);
} /* addq */
int getq() {
/* this returns the item at the front of the queue */
1. if (!is_q_empty()) {
3. return(Q[++front]);
}
4. else
5. error(queue_empty);
} /* getq */
Boolean is_q_empty() {
/* returns true if the queue is empty */
1. if (front == rear){
2. front = rear = -1; // to delay running out of queue space
3. return(TRUE);
}
4. else
5. return(FALSE);
} /* is_q_empty */
Boolean is_q_full() {
// returns true if the queue is full */
1. return(rear == QSIZE-1)
} /* is_q_full */
Linear Circular Queues
These routines assume an array of items, numbered from 0 to QSIZE-1
named Q and two variables front and rear, both initialized to 0.
void addq(int item) {
/* this adds item to the rear of the queue */
1. rear = (rear + 1) % QSIZE;
2. if (! is_q_full())
3. Q[rear] = item;
4. else
5. error(queue_full);
} /* addq */
int getq() {
/* this returns the item at the front of the queue */
1. if (! is_q_empty())
2. front = (front + 1) % QSIZE;
3. return(Q[front]);
4. else
5. error(queue_empty);
6. endif
} /* getq */
Boolean is_q_empty() {
/* returns true if the queue is empty */
1. return(front == rear);
} /* is_q_empty
Function is_q_full() returns Boolean
/* returns true if the queue is full */
/* The code here is the same as is_q_empty */
} /* is_q_full */