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

顺序表循环队列：

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。刚才的例子继续，rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了，如图所示。

接着入队a 6 ，将它放置于下标为0处，rear指针指向下标为1处，如左图所示。若再入队a 7 ，则rear指针就与front指针重合，同时指向下标为2的位置，如右图所示。

此时问题又出来了，我们刚才说，空队列时，front等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？办法一是设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。办法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如左图所示，我们就认为此队列已经满了，也就是说，我们不允许右图情况出现。

顺序表循环队列的顺序存储结构c语言描述：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 循环队列的顺序存储结构 */
typedef struct
{
  QElemType data[MAXSIZE];
  /* 头指针 */
  int front;
  /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
  int rear;
} SqQueue;

顺序表循环队列的初始化：

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

顺序表循环队列求队列长度代码：

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
  return (Q.rear - Q.front  MAXSIZE)% MAXSIZE;
}

顺序表循环队列的入队列操作代码：

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue *Q, QElemType e)
{
 /* 队列满的判断 */
  if ((Q->rear  1) % MAXSIZE == Q->front)
    return ERROR;
  /* 将元素e赋给队尾 */
  Q->data[Q->rear] = e;
  /* rear指针向后移一位置， */
  Q->rear = (Q->rear  1) % MAXSIZE;
  /* 若到最后则转到数组头部 */
  return OK; 
}

顺序表循环队列的出队列操作代码：

/* 若队列不空，则删除Q中队头元素，用e返回其 */
Status DeQueue(SqQueue *Q, QElemType *e)
{
  /* 队列空的判断 */
  if (Q->front == Q->rear)
    return ERROR;
  /* 将队头元素赋给e */
  *e = Q->data[Q->front];
  /* front指针向后移一位置， */
  Q->front = (Q->front  1) % MAXSIZE;
  /* 若到最后则转到数组头部 */
  return OK;
}

链式队列：

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