home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / progmisc / ad12.zip / QUEUE.AD < prev    next >
Text File  |  1990-02-27  |  2KB  |  68 lines
  1.  ┌ * Queue
  2.  │ * Implemenation of a queue as a linked data structure
  3.  │ *
  4.  │ * Operations supported:
  5.  │ *     enqueue(x)       place item x at the end of the queue
  6.  │ *     head             return the item at the head of the queue
  7.  │ *     dequeue          remove next item from the front of the queue
  8.  │ *     empty            return true iff the queue is empty
  9.  │ *
  10.  │ ┌ * Data structures
  11.  │ │ *     qHead          pointer to the head of the queue
  12.  │ │ *     qTail          pointer to the tail of the queue
  13.  │ │ *     qItem          queue member structure
  14.  │ │ *        next        pointer to next item on queue
  15.  │ │ *        anItem      the item itself - must be of proper type
  16.  │ │ *                    to contain the type of items on the queue
  17.  │ │ 
  18.  │ │ typedef long member; * storing longs on this queue
  19.  │ │ typedef struct item item;
  20.  │ │ 
  21.  │ │ struct item {
  22.  │ │      item *next;
  23.  │ │      member anItem;    
  24.  │ │      };
  25.  │ │ item *quhead = NULL, *qtail = NULL;
  26.  │ └  
  27.  │ 
  28.  │ ┌ * Functions 
  29.  │ │ 
  30.  │ │ * add an item to queue
  31.  │ │ ┌ void enqueue(item x) {
  32.  │ │ │ * Allocate a new item structure
  33.  │ │ │ item *new;             * pointer to new node
  34.  │ │ │ new = malloc(sizeof item);
  35.  │ │ │ 
  36.  │ │ │ * Place the item on the queue
  37.  │ │ │ new->item = x;
  38.  │ │ │ new->next = NULL;
  39.  │ │ │ 
  40.  │ │ │ ╒ If (empty())
  41.  │ │ │ │ {
  42.  │ │ │ │ * Queue is empty, point the queue head and tail at the new item
  43.  │ │ │ │ qHead = new;
  44.  │ │ │ │ qTail = new;
  45.  │ │ │ │ }
  46.  │ │ │ ├ Else
  47.  │ │ │ │ {
  48.  │ │ │ │ * Queue is not empty, insert the item and point everything to it
  49.  │ │ │ │ qTail->next = new;
  50.  │ │ │ │ qTail = new;
  51.  │ │ │ │ }
  52.  │ │ │ └ 
  53.  │ │ │ 
  54.  │ │ └ }
  55.  │ │ 
  56.  │ │ * remove next item from queue
  57.  │ │ ┌ void dequeue() { │ │ │ * head is always next item │ │ │ qHead = qHead->next; │ │ │  │ │ │ ╒ If (qHead == NULL) │ │ │ │      * queue is now empty │ │ │ │      qTail = NULL; │ │ │ └  │ │ │  │ │ └ }
  58.  │ │ 
  59.  │ │ * return item at head of queue; don't remove
  60.  │ │ ┌ member head() { │ │ │ return (qHead->anItem); │ │ └  }
  61.  │ │ 
  62.  │ │ * return true if the queue is empty, false otherwise
  63.  │ │ ┌ int empty() { │ │ │ return (qHead == NULL); │ │ └  }
  64.  │ │ 
  65.  │ └  
  66.  │ 
  67.  └ 
  68.