数组

let array = [1, 2, 3]
栈:

let stack = [1, 2, 3]
// 进栈
stack.push(4)
// 出栈
stcak.pop()
队列:

let queue = [1, 2, 3]
// 进队
queue.push(4)
// 出队
queue.shift()

在 JavaScript 中, 数组的存储

class Stack {
  constructor(...args){
    this.stack = [...args]
  }

  // 
  push(...items){
    return this.stack.push(...items)
  }

  pop(){
    return this.stack.pop()
  }

  peek(){
    return this.isEmpty() ? undefined : this.stack(this.size() -1)
  }

  isEmpty(){
    return this.size() == 0
  }

  size(){
    return this.stack.length
  }
}
class Queue{
  constructor(...args){
    this.queue = [...args]
  }

  enqueue(...items){
    return this.queue.push(...items)
  }

  dequeue(...items){
    return this.queue.shift()
  }

  front(){
    return this.isEmpty() ? undefined : this.queue[0]
  }

  back(){
    return this.isEmpty() ? undefined : this.queue[this.size() -1]
  }

  isEmpty(){
    return this.size() == 0
  }

  size(){
    return this.queue.length
  }
}

  1. 快数组(FastElements)

FixedArray 是 V8 实现的一个类似于数组的类,它表示一段连续的内存,可以使用索引直接定位。新创建的空数组默认就是快数组。当数组满(数组的长度达到数组在内存中申请的内存容量最大值)的时候,继续 push 时, JSArray 会进行动态的扩容,以存储更多的元素。

  1. 慢数组(SlowElements)

慢数组以哈希表的形式存储在内存空间里,它不需要开辟连续的存储空间,但需要额外维护一个哈希表,与快数组相比,性能相对较差。

例如:向快数组里增加一个大索引同类型值

var arr = [1, 2, 3]
arr[2000] = 10;

当往 arr 增加一个 2000 的索引时,arr 被转成慢数组。节省了大量的内存空间(从索引为 2 到索引为 2000)。

用两个栈实现队列

/**
 * initialize your data structure here.
 */
var MinStack = function() {
  this.stack = [];
  this.minV = Number.MAX_VALUE;
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  // update 'min'
  const minV = this.minV;
  if (x < this.minV) {
    this.minV = x;
  }
  return this.stack.push(x - minV);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  const item = this.stack.pop();
  const minV = this.minV;

  if (item < 0) {
    this.minV = minV - item;
    return minV;
  }
  return item + minV;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  const item = this.stack[this.stack.length - 1];
  const minV = this.minV;

  if (item < 0) {
    return minV;
  }
  return item + minV;
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
  return this.minV;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

最后更新于

这有帮助吗?