Written with StackEdit中文版.

循环队列

简介

和顺序栈类似，顺序队列除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需附设两个指针front和rear分别只是队头元素及队尾元素的位置。

循环队列，则是将顺序队列臆造为一个环状的空间。为了判断循环队列的“已满”状态，规定这个空间的大小是一个定值，因此在C语言中不能用动态分配的一维数组来实现。

若用户无法预估所用的队列最大长度，则宜采用链队列。

声明与定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define MAXQSIZE 100;//最大队列长度
typedef int QElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

//循环队列——队列的顺序存储结构
typedef struct{
  QElemType *base;//初始化的动态分配存储空间
  int front;//头指针
  int rear;//尾指针
  int size;//队列的总容量
  int ElemNum;//当前队列的元素个数
}SqQueue;

//构造一个大小为len的空队列Q
Status InitQueue(SqQueue* Q, int len);
//清除队列Q
Status ClearQueue(SqQueue* Q);
//判定队列是否为空
Status QueueEmpty(SqQueue Q);
//返回队列中的元素个数，即队列的长度
int QueueLength(SqQueue Q);
//将数组pInput中的len个元素依次插入到队列Q中
//返回值是成功入队的元素个数
int EnQueue(SqQueue* Q, QElemType* pInput, int len);
//从队列Q中取出len个元素到数组pOutput中
//返回值是成功取出的元素个数
int DeQueue(SqQueue* Q, QElemType* pOutput, int len);

相关方法实现

InitQueue

1
2
3
4
5
6
7
8
9
Status InitQueue(SqQueue *Q, int len){
  Q->front = 0;
  Q->rear = 0;
  Q->size = len;
  Q->ElemNum = 0;
  Q->base = (QElemType*)malloc(len * sizeof(QElemType));
  if (!Q->base)exit(OVERFLOW);
  return OK;
}

ClearQueue

1
2
3
4
Status ClearQueue(SqQueue *Q){
  Q->front = Q->rear = Q->ElemNum = 0;
  return OK;
}

QueueEmpty

1
2
3
Status QueueEmpty(SqQueue Q){
  return (0 == Q.ElemNum);
}

QueueLength

1
2
3
int QueueLength(SqQueue Q){
  return (Q.ElemNum);
}

EnQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int EnQueue(SqQueue* Q, QElemType* pInput, int len){
  int wLen = 0;//待入队的元素有len个，wLen从0增加到len-1

  while (Q->ElemNum < Q->size && wLen < len) {//队列没满且还有待入队的元素时
    Q->base[Q->rear] = pInput[wLen];
    Q->rear++;

    if (Q->rear >= Q->size) {//入队元素溢出了
      Q->rear = 0;//重新循环
    }
    wLen++;
    Q->ElemNum++;
  }
  printf("期望入队%d个元素,实际入队%d个元素\n", len, wLen);
  return wLen;//返回值为0表示没有元素入队
}

DeQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int DeQueue(SqQueue* Q, QElemType* pOutput, int len){
  int rLen = 0;//期望取出的元素有len个，最终取出rLen个元素

  while (!QueueEmpty(*Q) && rLen < len) {//队列中还有元素且还需要取元素时
    pOutput[rLen] = Q->base[Q->front];
    Q->front++;

    if (Q->front >= Q->size) {//取了一圈的元素之后
      Q->front = 0;//从头再开始取，即循环
    }
    rLen++;
    Q->ElemNum--;
  }
  printf("期望出队%d个元素,实际出队%d个元素\n", len, rLen);
  return rLen;//返回值为0表示队列中没有元素
}

方法测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(void){
  SqQueue Q;//这里是结构体，不是指针！
  QElemType arrInput[6] = { 3,6,1,-1,9,-7 };//待入队的元素组
  QElemType arrOutput[10];//期望取出的元素组
  InitQueue(&Q, 5);

  EnQueue(&Q, arrInput, 6);
  DeQueue(&Q, arrOutput, 4);
  for (int i = 0; i < 4; i++) {
    printf("%d ", arrOutput[i]);
  }
  printf("\n");

  EnQueue(&Q, arrInput, 3);
  DeQueue(&Q, arrOutput, 5);
  for (int i = 0; i < 4; i++){
    printf("%d ", arrOutput[i]);
  }
  return 0;
}