Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A04 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A04 notes: Basic Data Structures - Queues

In this lecture

• Kruse: Chapter 4.1 to 4.2
• Deitel & Deitel: Chapter 12.6
• Standish: Chapter 7
• Langsam: Chapter 4.1

• A sequence of items where items are inserted at one end, called the rear, and deleted from the other end, called the front.
• Also called First-In First-Out lists, or FIFO lists.

• Is a good method if the queue is regularly emptied.
• The queue tends to move down the array, and space at the beginning of the array can be wasted.

• Solves the problem of wasted space, in the Linear implementation, by treating the array as if its two ends were joined together to form a circl e.

Code for this lecture

/* queue.h */
#ifndef QUEUEH
#define QUEUEH

#include <stdbool.h> 

#define MAXQUEUE 20

struct QueueRec
{
 int   count;
 int   front;
 int   rear;
 float entry[MAXQUEUE];
};

typedef struct QueueRec  Queue;

void intializeQueue(Queue* queuePtr);
bool queueEmpty(Queue* queuePtr);
bool queueFull(Queue* queuePtr);
void append(Queue* queuePtr, float item);
float serve(Queue* queuePtr);

#endif

/* queue.c */
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/* Initialize a queue to be empty. */
void initializeQueue(Queue* queuePtr)
{
 queuePtr->count = 0;
 queuePtr->front = 0;
 queuePtr->rear = MAXQUEUE - 1;
}

/* Returns true if queue is empty */
bool queueEmpty(const Queue* queuePtr)
{
  if (queuePtr->count <= 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

/* Returns true if the queue is full */
bool queueFull(const Queue* queuePtr)
{
  if (queuePtr->count >= MAXQUEUE)
  {
     return true;
  }
  else
  {
     return false;
  }
}

/* Append an item to the rear of a queue. */
void append(Queue* queuePtr, float item)
{
  if (queueFull(queuePtr))
  {
     fprintf(stderr, "Queue is full\n");
     exit(1);
  }
  else
  {
     queuePtr->rear++;
     if (queuePtr->rear == MAXQUEUE)
     {
        queuePtr->rear = 0;
     }
     queuePtr->entry[queuePtr->rear] = item;
     queuePtr->count++;
  }
}

/* Serve the item at the front of a queue. */
float serve(Queue* queuePtr)
{
 float item;

 if (queueEmpty(queuePtr))
 {
    fprintf(stderr, "Queue is empty\n");
    exit(1);
 }
 else
 {
    item = queuePtr->entry[queuePtr->front];
    queuePtr->front++;
    if (queuePtr->front == MAXQUEUE)
    {
        queuePtr->front = 0;
    }
    queuePtr->count--;
 }
 return item;
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:01:07