C语言队列实例

/* queue.h -- interface for a queue */
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>

// INSERT ITEM TYPE HERE
// FOR EXAMPLE,
//typedef int Item;  // for use_q.c
// OR typedef struct item {int gumption; int charisma;} Item;
// OR  (for mall.c)
/**/
 typedef struct item
 {
 long arrive;      // the time when a customer joins the queue
 int processtime;  // the number of consultation minutes desired
 } Item;
/**/

#define MAXQUEUE 10

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;  /* pointer to front of queue  */
    Node * rear;   /* pointer to rear of queue   */
    int items;     /* number of items in queue   */
} Queue;

/* operation:        initialize the queue                       */
/* precondition:     pq points to a queue                       */
/* postcondition:    queue is initialized to being empty        */
void InitializeQueue(Queue * pq);

/* operation:        check if queue is full                     */
/* precondition:     pq points to previously initialized queue  */
/* postcondition:   returns True if queue is full, else False   */
bool QueueIsFull(const Queue * pq);

/* operation:        check if queue is empty                    */
/* precondition:     pq points to previously initialized queue  */
/* postcondition:    returns True if queue is empty, else False */
bool QueueIsEmpty(const Queue *pq);

/* operation:        determine number of items in queue         */
/* precondition:     pq points to previously initialized queue  */
/* postcondition:    returns number of items in queue           */
int QueueItemCount(const Queue * pq);

/* operation:        add item to rear of queue                  */
/* precondition:     pq points to previously initialized queue  */
/*                   item is to be placed at rear of queue      */
/* postcondition:    if queue is not empty, item is placed at   */
/*                   rear of queue and function returns         */
/*                   True; otherwise, queue is unchanged and    */
/*                   function returns False                     */
bool EnQueue(Item item, Queue * pq);

/* operation:        remove item from front of queue            */
/* precondition:     pq points to previously initialized queue  */
/* postcondition:    if queue is not empty, item at head of     */
/*                   queue is copied to *pitem and deleted from */
/*                   queue, and function returns True; if the   */
/*                   operation empties the queue, the queue is  */
/*                   reset to empty. If the queue is empty to   */
/*                   begin with, queue is unchanged and the     */
/*                   function returns False                     */
bool DeQueue(Item *pitem, Queue * pq);

/* operation:        empty the queue                            */
/* precondition:     pq points to previously initialized queue  */
/* postconditions:   the queue is empty                         */
void EmptyTheQueue(Queue * pq);

#endif

/* queue.c -- the Queue type implementation*/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/* local functions */
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node * pn, Item * pi);

void InitializeQueue(Queue * pq)
{
    pq->front = pq->rear = NULL;
    pq->items = 0;
}

bool QueueIsFull(const Queue * pq)
{
    return pq->items == MAXQUEUE;
}

bool QueueIsEmpty(const Queue * pq)
{
    return pq->items == 0;
}

int QueueItemCount(const Queue * pq)
{
    return pq->items;
}

bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;

    if (QueueIsFull(pq))
        return false;
    pnew = (Node *) malloc( sizeof(Node));
    if (pnew == NULL)
    {
        fprintf(stderr,"Unable to allocate memory!\n");
        exit(1);
    }
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
        pq->front = pnew;           /* item goes to front     */
    else
        pq->rear->next = pnew;      /* link at end of queue   */
    pq->rear = pnew;                /* record location of end */
    pq->items++;                    /* one more item in queue */

    return true;
}

bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;

    if (QueueIsEmpty(pq))
        return false;
    CopyToItem(pq->front, pitem);
    pt = pq->front;
    pq->front = pq->front->next;
    free(pt);
    pq->items--;
    if (pq->items == 0)
        pq->rear = NULL;

    return true;
}

/* empty the queue                */
void EmptyTheQueue(Queue * pq)
{
    Item dummy;
    while (!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
}

/* Local functions                 */

static void CopyToNode(Item item, Node * pn)
{
    pn->item = item;
}

static void CopyToItem(Node * pn, Item * pi)
{
    *pi = pn->item;
}

/* use_q.c -- driver testing the Queue interface */
/* compile with queue.c                          */
#include <stdio.h>
#include "queue.h"  /* defines Queue, Item       */

int main(void)
{
    Queue line;
    Item temp;
    char ch;

    InitializeQueue(&line);
    puts("Testing the Queue interface. Type a to add a value,");
    puts("type d to delete a value, and type q to quit.");
    while ((ch = getchar()) != 'q')
    {
        if (ch != 'a' && ch != 'd')   /* ignore other input */
            continue;
        if ( ch == 'a')
        {
            printf("Integer to add: ");
            scanf("%d", &temp);
            if (!QueueIsFull(&line))
            {
                printf("Putting %d into queue\n", temp);
                EnQueue(temp,&line);
            }
            else
                puts("Queue is full!");
        }
        else
        {
            if (QueueIsEmpty(&line))
                puts("Nothing to delete!");
            else
            {
                DeQueue(&temp,&line);
                printf("Removing %d from queue\n", temp);
            }
        }
        printf("%d items in queue\n", QueueItemCount(&line));
        puts("Type a to add, d to delete, q to quit:");
    }
    EmptyTheQueue(&line);
    puts("Bye!");

    return 0;
}