结构体数组 数据结构学习(3)

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。结构体数组为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点，如图所示。

空队列时，front和rear都指向头结点。

链队列的结构描述：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 结点结构 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct
{
  /* 队头、队尾指针 */
  QueuePtr front, rear;
} LinkQueue;

链式队列入队操作：

入队操作时，其实就是在链表尾部插入结点。

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 结点结构 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct
{
  /* 队头、队尾指针 */
  QueuePtr front, rear;
} LinkQueue;

链式队列入队操作：

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemTypee)
{
  QueuePtr s =(QueuePtr)malloc(sizeof(QNode));
  /* 存储分配失败 */
  if (!s)
    exit(OVERFLOW);
  s->data = e;
  s->next = NULL;
  /* 把拥有元素e新结点s赋给原队尾结点的后继， */
  Q->rear->next = s;
  /* 把当前的s设置为队尾结点，rear指向s*/
  Q->rear = s;
  return OK;
}

链式队列出队操作：

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

/* 若队列不空，删除Q的队头元素，用e返回其，并返回OK，否则返回ERROR */
Status DeQueue(LinkQueue *Q, QElemType*e)
{
  QueuePtr p;
  if (Q->front == Q->rear)
      return ERROR;
  /* 将欲删除的队头结点暂存给p*/
  p = Q->front->next;
  /* 将欲删除的队头结点的赋给e */
  *e = p->data;
  /* 将原队头结点后继p->next赋给头结点后继 */
  Q->front->next = p->next;
  /* 若队头是队尾，则删除后将rear指向头结点*/
  if (Q->rear == p)
      Q->rear = Q->front;
  free(p);
  return OK;
}

循环队列与链队列的比较：

从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。总的来说，在可以确定队列长度最大的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

例子：

实现一个链队列，任意输入一串字符串，以@为结束标志，然后将队列中的元素逐一取出，打印在屏幕上。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69035-3.html