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 */