队列的定义

队列是只允许在一端插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的基本操作

image.png

循环队列的定义

循环队列就是头尾相接的顺序存储结构。

image.png

特点

数组未满时可以插入新的队尾元素。

image.png
初始化：rear=front=0
队列为空：rear == front（链队为空：rear==fornt==NULL）
队列已满：(rear + 1)% MAX_SIZE == front
队列长度：(rear-front+maxsize)%maxsize
队头指针：front=(front+1)%maxsize
队尾指针：rear=(rear+1)%maxsize

处理队满或者队空

  1. 少用一个空间，即空间大小为 MAX_SIZE 时，有 MAX_SIZE-1 个元素就认为是队满。
  2. 单独设置一个标识以区别队列是否是满状态或者空状态。

    实现

    JavaScript

  1. class Queue {
  2.     constructor() {
  3.       this.items = [];
  4.     }
  5.     // 添加新元素
  6.     enqueue(element) {
  7.         this.items.push(element);
  8.     }
  9.     // 移除元素
  10.     dequeue() {
  11.       return this.items.shift();
  12.     }
  13.     // 查看队列头元素
  14.     front() {
  15.       return this.items[0];
  16.     }
  17.     // 检查队列是否为空
  18.     isEmpty() {
  19.       return this.items.length == 0;
  20.     }
  21.     // 队列元素个数
  22.     size() {
  23.       return this.items.length;
  24.     }
  25.     // 打印队列元素
  26.     print() {
  27.       console.log(this.items.toString());
  28.     }
  29. }

应用

  • 页面置换算法
  • 缓冲区
  • cpu资源竞争

    广义表

广义表就是通常所说的列表，它放松了对表元素的原子性限制，允许他们有自身结构。

那么广义表E((a,(a,b),((a,b),c)))的长度和深度分别为：1 ,4。去掉最外面的一层括号，剩下的还是一个整体，故长度是1，深度是脱几层括号能把最里面的数露出来，显然是右边的那个ab，共脱了4层括号。

画出广义表 LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构

image.png