上周还说写写markdown的学习，但是看了一遍博客发现似乎没什么可说的，看了一圈教程发现似乎只要模仿就好了，参考链接
https://www.jianshu.com/p/q81RER
所以这周想随便写写。
两种数据结构
栈和队列，两种我们用的最多也是最常见的两种数据结构。让我回忆一下，在学习数据结构的时候，一开始介绍了顺序表，链表，然后就是栈和队列，再然后就是树，图一类的比较复杂的数据结构。而栈和队列，可以说是比较常用的两种，因为其实现方式简单，很多语言把这两种数据结构专门封装了库，而且这两种本身也和程序的执行有关（调用栈等等）。
区别与共同点
从这里开始我将结合js做一些常用点的讨论。首先，栈和队列，无论在当时进行编写的时候还是后来用js进行练习，我都认为，顺序表，链表，栈和队列都可以理解为数组，甚至树和图也可以这么理解。不过他们会有很多自己的特性，以至于他们不能完全像数组那么随意。
就今天的主角——栈和队列来说，他们的共同特点就是，只能从首尾进行插入和删除，栈是只能从头进行插入和删除，队列是要从头进行插入，从尾部进行删除。栈和队列这样的特性，决定了他们的各自数据插入删除的结构，栈必须是后进先出，因为他只有栈顶一个出入口，队列是先进先出，灵魂绘图。。。：
所以无论何时我们做任何操作的时候，我们必须记住两个各自的特性，从删除到添加，从搜索到遍历，从逆序到交换等各种操作都得讲究这种先进先出，后进先出的特性。比如我要在栈或者中删除B，那么绝对不可以像数组删除一样直接从中间干掉就好，需要满足两者的特性，栈必须B移到栈顶删除，队列必须到队列尾删除，交换的时候不能破坏栈与队列的结构，或者也可以一个一个的pop，然后再一个一个的push进来。
未完。。。。
更复杂的形式（链栈，链队列，循环队列）
手写js的栈与队列
今天再填一个坑，手写了js的栈和队列，当然使用了typescript，所以从形式上是更直观的面向对象
------
interface ObjectT {
value: string,
}
class Stack {
private stackContent: ObjectT[]
private stackTop?: ObjectT
private objectNumber: number
constructor(stack:ObjectT[]) {
this.stackContent = stack || []
this.objectNumber = this.stackContent.length
if(this.objectNumber != 0) {
this.stackTop = this.stackContent[0]
}
}
public push(obj: ObjectT) {
this.objectNumber++
for(let i = this.objectNumber-1;i >= 0;i--) {
if(i == 0) {
this.stackContent[i] = obj
}
else {
this.stackContent[i] = this.stackContent[i-1]
}
}
this.stackTop = this.stackContent[0]
console.log(this.stackContent)
console.log(this.stackTop)
}
public pop() {
if(this.objectNumber > 0) {
for(let i = 0;i < this.objectNumber-1;i++) {
this.stackContent[i] = this.stackContent[i+1]
}
let result = this.stackTop
this.stackTop = this.stackContent[0]
delete this.stackContent[this.objectNumber-1]
this.objectNumber--
return result
}
}
}
class Queue {
private queueContent: ObjectT[]
private queueTop?: ObjectT
private queueTail?: ObjectT
private objectNumber: number
constructor(queue: ObjectT[]) {
this.queueContent = queue || []
this.objectNumber = this.queueContent.length
if(this.objectNumber != 0) {
this.queueTop = this.queueContent[0]
this.queueTail = this.queueContent[this.objectNumber-1]
}
}
public push(obj:ObjectT) {
this.objectNumber++
for(let i = this.objectNumber-1;i >= 0;i--) {
if(i == 0) {
this.queueContent[i] = obj
}
else {
this.queueContent[i] = this.queueContent[i-1]
}
}
this.queueTop = this.queueContent[0]
this.queueTail = this.queueContent[this.objectNumber-1]
console.log(this.queueContent)
console.log(this.queueTop)
console.log(this.queueTail)
}
public pop() {
if(this.objectNumber > 0) {
let result = this.queueTail
delete this.queueContent[this.objectNumber-1]
this.objectNumber--
this.queueTail = this.queueContent[this.objectNumber-1]
console.log(this.queueContent)
return result
}
}
}
-----------
网友评论