计算机基础数据结构讲解第九篇-顺序队列

??本篇介绍有关队列的知识。队列也是一种特殊的线性表，只允许在表的表的一端进行插入，而在表的另一端进行删除。插入元素称为入队或进队；删除元素称为出队或离队。操作的特性是先进先出。
??队列的常见操作和栈类似，有初始化队列，队列判空，入队，出队，读队头元素。下面介绍队列的顺序存储和链式存储。

一：队列的顺序存储

1.普通的顺序存储队列

??实质是分配一块连续的存储单元存放队列中的元素，并附设两个指针，一个队头指针front指向队头元素，一个队尾指针rear指向队尾元素的下一个位置，也有其他的定义，操作是不同的。
??顺序队列描述为：

#define MaxSize 20              //定义队列中元素的最大个数
typedef struct{
  ElemType data[MaxSize];       //存放队列元素
  int front,rear;               //队头指针和队尾指针
}SqQueue;

??初始状态(队空)： Q.front == Q.rear == 0。
??进队操作：队不满时，先先送值到队尾元素，队尾指针再加一。
??出队操作：队不空时，先取队头元素值，再将队头指针加一。
??但是这种简单的队列会出现假溢出的现象，是因为队满时Q.front仍然等于Q.rear。如何进行改进呢，可以用一种叫做循环队列的存储结构。

2.循环队列

??就使用一种环状结构存储队列，当队首指针Q.front在队满的位置MaxSize-1时，再前进一个位置就自动回到0，这时候可以用取余操作%来实现。
??初始时：Q.front==Q.rear=0。
??队首指针加一：Q.front=(Q.front+1)%MaxSize。
??队尾指针加一：Q.rear=(Q.rear+1)%MaxSize。
??队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。
??出队入队时，指针都按顺时针的方向进1。
??为了区别当Q.rear == Q.front时，是队满还是队空，可以有三种处理方式。
??(1)牺牲一个存储单元区分队空还是队满，即入队的时候少用一个队列单元。则有
??队空：Q.front == Q.rear
??队满：(Q.rear+1)%MaxSize == Q.front
??队列中元素个数：(Q.rear+MaxSize-Q.front)%MaxSize
??(2)用一个计数器计算元素个数
??(3)用一个tag数据成员区分队空还是队满,tag为0时队空，tag为1时队满。
??操作如下：
??初始化：

void InitQueue(SqQueue &Q){
  Q.rear = Q.front = 0;         //初始化队首，队尾指针
}

??判队空：

bool isEmpty(SqQueue Q){
  if(Q.rear == Q.front) return true;    //队空条件
  else return false;
}

??入队：

bool EnQueue(SqQueue &Q,ElemType x){
  if((Q.rear+1)%MaxSize == Q.front) return false; //队满则报错
  Q.data[Q.rear] = x;
  Q.rear = (Q.rear+1)%MaxSize;
  return true;
}

??出队：

bool DeQueue(SqQueue &Q,ElemType &x){
  if(Q.rear == Q.front) return false;  //队空则报错
  x = data[Q.front];
  Q.front = (Q.front+1)%MaxSize;
  return true;
}

计算机基础数据结构讲解第九篇-顺序队列

原文：https://www.cnblogs.com/ITXiaoAng/p/13669665.html