ch3_lqueue.c

本人讲授数据结构课程时的所写的示例程序

/*
队列的链式实现
author: kk.h
date: 2006.9.27
http://www.cocoon.org.cn
*/

#include "stdio.h"
#define MaxSize 100
typedef int ElemType;
typedef struct QNode{
  ElemType elem;
  struct QNode * next;
}QNode;

typedef struct {
  QNode* front;
  QNode* rear;
}LinkQueue;

InitQueue(LinkQueue* pQ)
{
  QNode* node;
  node=(QNode*)malloc(sizeof(QNode));  /*分配一个头节点*/
  node->next = NULL;  
  pQ->front=pQ->rear=node;
}

int EnQueue(LinkQueue* pQ,ElemType e)
{
  QNode* node;
  node=(QNode*)malloc(sizeof(QNode));
  node->elem = e;
  node->next = NULL;

  pQ->rear->next = node;
  pQ->rear = node;
  return 1;
}

int DeQueue(LinkQueue* pQ,ElemType* pe)
{
  QNode* node;
  if (pQ->rear == pQ->front)    /* 队空 */
    return 0;

  node = pQ->front->next;
  *pe = node->elem;
  pQ->front->next = node->next;

  /* 注意有个头节点，当最后一个元素出队时，记得更新尾指针 */
  if (pQ->rear==node)
    pQ->rear=pQ->front;

  free(node);
  return 1;
}

DestoryQueue(LinkQueue* pQ)
{
  while(pQ->front){
    pQ->rear=pQ->front->next;
    free(pQ->front);
    pQ->front = pQ->rear;
  }
}

main()
{
  LinkQueue Q;
  ElemType e;

  InitQueue(&Q);

  e=2;
  EnQueue(&Q,e);
  e=5;
  EnQueue(&Q,e);
  e=3;
  EnQueue(&Q,e);

  while(DeQueue(&Q,&e)){
    printf("\n%d",e);
  }

  DestoryQueue(&Q);
  getch();
}