JS 实现数据结构

【摘要】 JS 实现数据结构考必过小编为大家整理了关于JS 实现数据结构的信息，希望可以帮助到大家！

JS 实现数据结构

标签：OLE向量空间指点instancegets添加元素自己fontlength

使用JS实现数据结构。

1.栈

栈作为简单的数据结构，JS对其实现的方法也相对简单。

代码：

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    this.stack.pop();
  }
  peek() {
    return this.stack[this.getCount() - 1];
  }
  getCount() {
    return this.stack.length;
  }
  clear() {
    this.stack = [];
  }
  isEmpty() {
    return this.getCount() === 0;
  }
  getStack() {
    console.log(this.stack);
  }
}

示例代码：

function Stacked() {
    let stack = new Stack();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.push(6);
    stack.getStack();
    stack.pop();
    console.log(stack.peek());
}

队列

队列有着先进先出的特点，在使用JS来实现单队列是很简单的一件事。

代码：

class Queue {
  constructor() {
    this.queue = [];
  }
  enQueue(item) {
    this.queue.push(item);
  }
  deQueue() {
    return this.queue.shift();
  }
  getHeader() {
    return this.queue[0];
  }
  getLength() {
    return this.queue.length;
  }
  clear() {
    this.queue = [];
  }
  isEmpty() {
    return this.getLength() === 0;
  }
  getQueue() {
    console.log(this.queue);
  }
}

有一种队列，每一个值都带有自己的优先级，这种队列成为优先级队列。

代码：

class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  // 向队列添加元素（一个或多个）
  // 参数obj的数据格式：{element, priority}
  enQueue(obj) {
    if (obj instanceof Array) {
      for (let i = 0, data; (data = obj[i]); i++) {
        this.enQueue(data);
      }
    } else {
      let added = false;
      for (let i = 0, data; (data = this.queue[i]); i++) {
        // 最小优先级，即将priority值小的元素插入到队列的前面
        if (obj.priority < data.priority) {
          this.queue.sppce(i, 0, obj);
          added = true;
          break;
        }
      }

      // 如果元素没有插入到队列中，则默认加到队列的尾部
      if (!added) this.queue.push(obj);
    }
  }

  deQueue() {
    return this.queue.shift();
  }

  getHeader() {
    return this.queue[0];
  }

  getLength() {
    return this.queue.length;
  }

  clear() {
    this.queue = [];
  }

  isEmpty() {
    return this.getLength() === 0;
  }

  getQueue() {
    this.queue.forEach(function (item) {
      console.log(`${item.element} - ${item.priority}`);
    });
  }
}

为充分利用向量空间，克服假溢出现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列

代码：

class SqQueue {
  constructor() {
    this.queue = new Array();
    this.first = 0; // 队头
    this.last = 0;  // 队尾
    this.size = 0;  // 实际大小
  }

  enQueue(item) {
    // 每当插入一个数据时，进行判断,如果此时first和last相等且last与队列长度相等时，将队列伸长，保证足够的空间填装数据
    if (
      this.first === this.last % this.queue.length &&
      this.last >= this.getLength()
    ) {
      this.resize(this.getLength() + 1);
    }
    this.queue[this.last] = item;
    this.size++;
    this.last = this.last + 1;
  }

  deQueue() {
    if (this.isEmpity()) {
      throw Error("queue is empty");
    }
    let r = this.queue[this.first];
    this.queue.shift();
    this.size--;
    return r;
  }
  
  getHeader() {
    if (this.isEmpity()) {
      throw Error("queue is empty");
    }
    return this.queue[this.first];
  }

  getLength() {
    return this.queue.length;
  }

  isEmpity() {
    return this.first === this.last && this.getLength() === 0;
  }

  resize(length) {
    // 生成新数组，代替原数组。
    let q = new Array(length);
    for (let i = 0; i < length; i++) {
      q[i] = this.queue[(i + this.first) % this.getLength()];
    }
    this.queue = q;
    this.first = 0;
    this.last = this.size;
  }

  getSqQueue() {
    console.log(this.queue);
  }
}

上述代码可在我的GitHub上下载，欢迎大家指点批评。

JS 实现数据结构

标签：OLE向量空间指点instancegets添加元素自己fontlength

以上就是JS 实现数据结构的内容，更多资讯请及时关注考必过网站，最新消息小编会第一时间发布，大家考试加油！