TypeScript算法与数据结构-队列和循环队列
1. 队列(Queue)
队列也是一种线性的数据结构, 队列是一种先进先出的数据结构。类似于生活中的排队买东西,先进入队列的人可以先购买到东西。这次的队列具体实现依然会采用之前自己封装好的数组,具体的优势依然是我们可以清晰的算出每次操作的时间复杂度。对于基本的队列而言,主要包含两个基本的操作入队(enqueue)
和出队(dequeue)
。
对于队列而言,入队发生在尾部,出队发生在首部,队列是一种先进先出的数据结构First in First out
。
我们依然会给队列定义一个接口,然队列类实现这个接口
interface Queue<E> {
getSize(): number; // 获取队列中元素的个数
isEmpty(): boolean; // 判断队列中的元素是否为空
enqueue(e: E): void; // 入队一个元素
dequeue(): E; // 出队一个元素
getFront(): E; // 获取当前队首的元素
}
1.1 构造函数
这里我们用到了之前封装好的数组
class ArrayQueue<E> implements Queue<E> {
private array: MyArray<E>;
constructor(capacity = 10) {
this.array = new MyArray<E>(capacity);
}
}
1.2 入队
入队我们只需要将元素添加到array
的尾部,这里的时间复杂度为O(1)
enqueue(e: E): void {
this.array.addLast(e);
}
1.3 出队
出队的话我们需要将元素从array
的头部移除,这里的时间复杂度为O(n)。这里为什么需要O(n)的时间复杂度,因为一旦我们要将第一个元素移除,那我们必须遍历整个array,将从位置1开始的每个元素向前移动一个位置。
dequeue(): E {
return this.array.removeFirst();
}
2.循环队列
循环队列是对队列的一种优化,入队和出队时,在不触发扩容和缩容操作的情况下,均能实现O(1)的时间复杂度。循环队列的原理是利用两个指针,一个指向队列的头部,一个指向队列的尾部。对于循环队列而言我们依然会实现上面的接口。
这里的构造函数会和之前的构造函数有所不同,主要是添加了两个执行队列头元素和队列尾元素的指针,初始状态下,循环队列的头指针和尾指针都
class LoopQueue<E> implements Queue<E> {
private data: Array<E>;
private front: number = 0;
private tail: number = 0;
private size: number = 0;
constructor(capacity = 10) {
this.data = new Array<E>(capacity + 1); // 这里需要在用户传入初始容量的基础上加1
}
}
2.1 入队
循环队列入队的操作非常简单,将tail节点所指向的节点赋值为所需要添加的节点e,然后维护一下tail指针所指向的位置。这里有一点需要注意的是,当队尾没有空元素时,队列尾指针会循环至队列的头部,然后从头开始。这也就是为什么称之为循环队列。循环队列的入队操作的时间复杂度为O(1)。
enqueue(e: E) {
// 如果循环队列已满,那此时需要扩容
if ((this.tail + 1) % this.data.length === this.front) {
this.resize(this.getCapacity() * 2);
}
this.data[this.tail] = e;
this.tail = (this.tail + 1) % this.data.length;
this.size++;
}
2.2 出队
出队的操作和入队相似,将当前front位置的元素置为undefined
,然后维护一下front指针的位置。同样的,在不触发缩容操作的情况下,出队操作能保证O(1)的时间复杂度
dequeue(): E {
if (this.isEmpty()) {
throw new Error('Cannot dequeue from an empty queue.');
}
let ret: E = this.data[this.front];
this.data[this.front] = undefined;
this.front = (this.front + 1) % this.data.length;
this.size--;
if (this.size === this.getCapacity() / 4 && this.getCapacity() / 2 !== 0) {
this.resize(this.getCapacity() / 2);
}
return ret;
}
2.3 循环队列的优势
循环队列的优势在于
- 循环队列最大程度的利用的数组的空间,节省内存
- 循环队列实现了入队和出队的操作都是O(1)的时间复杂度
最新文章
- C# 打开指定目录并定位到文件
- NBUT 1535
- 1022. D进制的A+B (20)
- C++学习5
- CICS的database中R D中参数的含义
- ado.net的5个主要对象
- LeetCode28 Implement strStr()
- UVa 11889 (GCD) Benefit
- CI 笔记 数据库
- ACM2075_A/B
- Unity Dx9 Occlusion Query plugin
- hdu 5423 Rikka with Tree(dfs)
- EasyUI - 要引入的JS文件
- zoj - 3209 - Treasure Map(精确覆盖DLX)
- cocos2d-x 网络请求
- 打开另外一个App
- 复制vmware中的centos后无法上网问题
- Request.QueryString(";id";)与Request(";id";)区别
- python进阶------进程线程(三)
- NOIP复习篇
热门文章
- WPF 4 Ribbon 开发 之 标签工具栏(Tab Toolbar)
- WPF 代码实现动画
- WPF TreeView绑定xaml的写法
- C# 异步委托的使用
- php 获取今日、昨日、本周,上周、本月,上月,季度的起始时间戳和结束时间戳的方法
- iOS Widget简单使用
- Windows 上静态编译 Libevent 2.0.10 并实现一个简单 HTTP 服务器(无数截图)
- GIS基础软件及操作(十二)
- Delphi中用MessageBox()API函数做倒计时对话框(使用Hook安装CBTHookCallback,计时器更改文字,SetWindowText API真正修改文字,引用未知函数)good
- 专访Rust——由Mozilla开发的系统编程语言(目标人群就是那些纠结的C++程序员,甚至也是他们自己)