JavaScript 算法 1_1 下压堆栈 (链表实现)

JavaScript 算法 1_1 下压堆栈 (链表实现)

链表是一种递归的数据结构

目录


1. 节点结构

node = {
	ele: null,
    next: null,
}

这里使用了 ele 作为一个节点的元素内容, next 作为下个节点的索引


2. 构造链表

let next = {};
Object.assign(next, {ele:null, next:null});
next.ele = item;

使用了 Object.assign 函数复制了节点结构


3. 从表头插入和删除元素

 push(item){
    let oldFirst = this.first;
    let next = {};
    Object.assign(next, {ele: null, next: null});
    next.ele = item;
    this.first = next;
    this.first.next = oldFirst;
    this.count++;
  }
  pop(){
    let top = this.first.ele;
    this.first = this.first.next;
    this.count--;
    return top;
  }
  • 插入时先保存栈顶元素到 oldFirst, 后创建 next 节点, 置为栈顶
  • 删除时移除栈顶元素并返回

4. 代码实现

链表类

// 类定义
class Stack{
  constructor() {
    // 栈顶元素, 包括 next 和 ele
    this.first = null;
    this.count = 0;
  }
  isEmpty(){
    return this.count === 0;
  }
  size(){
    return this.count;
  }
  push(item){
    let oldFirst = this.first;
    let next = {};
    Object.assign(next, {ele: null, next: null});
    next.ele = item;
    this.first = next;
    this.first.next = oldFirst;
    this.count++;
  }
  pop(){
    let top = this.first.ele;
    this.first = this.first.next;
    this.count--;
    return top;
  }
  // 下回分解迭代器
  // [Symbol.iterator](){
  //
  // }
}

使用方式

const stack = new Stack();

// 可以使用任意类型放入
stack.push(20);
stack.push('小歪');
stack.push([20, 30]);
stack.push({name: '张三'});

let pop = stack.pop();
// pop: { name: '张三' } 
pop = stack.pop();
// [ 20, 30 ]
pop = stack.pop();
// 小歪
pop = stack.pop();
// 20
console.log(stack);
// Stack { first: null, count: 0 }

代码可以按要求运行 √

JavaScript 算法 1_1 下压堆栈 (链表实现)

上一篇:JavaScript 算法 1_2 先进先出队列 (链表实现)


下一篇:javascript去除数组中的重复项