js数据结构

栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾为栈顶（top），表头为栈底（bottom），不含元素的空表为空栈。

栈又称为后进先出（last in first out）的线性表。

堆栈可以用链表和数组两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是 Stack 结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。

1
// 找的链式表示
function Stack() {
  this.top = null;
  this.size = 0;
}
module.exports = Stack;
Stack.prototype = {
  constructor: Stack,
  push: function (data) {
    var node = {
      data: data,
      next: null
    };

    node.next = this.top;
    this.top = node;
    this.size++;
  },
  peek: function () {
    return this.top === null ?
      null :
      this.top.data;
  },
  pop: function () {
    if (this.top === null) return null;

    var out = this.top;
    this.top = this.top.next;

    if (this.size > 0) this.size--;

    return out.data;
  },
  clear: function () {
    this.top = null;
    this.size = 0;
  },
  displayAll: function () {
    if (this.top === null) return null;

    var arr = [];
    var current = this.top;

    for (var i = 0, len = this.size; i < len; i++) {
      arr[i] = current.data;
      current = current.next;
    }

    return arr;
  }
};

var stack = new Stack();

stack.push(1);
stack.push('asd');

stack.pop();
stack.push({a: 1});
console.log(stack);

堆栈的应用

回溯
递回
深度优先搜寻

示例1：数值进制转换
公式： N = (N / d) * d + N % d N：十进制数值， d：需要转换的进制数

1
function numTransform(number, rad) {
  var s = new Stack();

  while (number) {
    s.push(number % rad);
    number = parseInt(number / 8, 10);
  }

  var arr = [];
  while (s.top) {
    arr.push(s.pop());
  }
  console.log(arr.join(''));
}

numTransform(1348, 8);
numTransform(1348, 2);

示例2：括号匹配检查
在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使得原有的在栈中的所有未消解的期待的急迫性都降一级。另外，在算法开始和结束时，栈都应该是空的。

1
function bracketsMatch(str) {
  var stack = new Stack();
  var text = '';

  for (var i = 0, len = str.length; i < len; i++) {
    var c = str[i];
    if (c === '[') {
      stack.push(c);
    } else if (c === ']') {
      if (!stack.top || stack.pop() !== '[') throw new Error('unexpected brackets:' + c);
    } else {
      text += c;
    }
  }
  console.log(text);
}

console.log(bracketsMatch('[asd]'));

示例3：行编辑
当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”,以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补进，则可以键入一个退行符“@”，以表示当前行中的字符均无效。 为此，可设这个输入缓冲区为一个栈结构，每当从终端接收了一个字符之后先做如下判断：
如果它既不是”#”也不是”@”，则将字符压入栈；
如果是”#”，则从栈顶删去一个字符；
如果是”@”，则清空栈。

1
function LineEditor(str) {
  this.stack = new Stack();
  this.str = str || ''
}
LineEditor.prototype = {
  getResult: function () {
    var stack = this.stack;
    var str = this.str;
    for (var i = 0, len = str.length; i < len; i++) {
      var c = str[i];
      switch (c) {
        case '#':
          stack.pop();
          break;
        case '@':
          stack.clear();
          break;
        default:
          stack.push(c);
          break;
      }
    }

    var result = '';
    var current = stack.top;
    while (current) {
      result = current.data + result;
      current = current.next;
    }

    return result;
  }
};

var le = new LineEditor('whli##ilr#e(s#*s)\
    \noutcha@putchar(*s=#++)');
console.log(le.getResult());

示例4：表达式求值
表达式求值是程序设计语言编译中的一个最基本问题、它的实现是栈应用的又一个典型例子。这里介绍一种简单直观，广为使用的算法，通常称为“运算符优先法”。
// from： http://wuzhiwei.net/ds_app_stack/

1
var prioty = {
  "+": 1,
  "-": 1,
  "%": 2,
  "*": 2,
  "/": 2,
  "^": 3,
  "(": 0,
  ")": 0,
  "`": -1
};

function doop(op, opn1, opn2) {
  switch (op) {
    case "+":
      return opn1 + opn2;
    case "-":
      return opn1 - opn2;
    case "*":
      return opn1 * opn2;
    case "/":
      return opn1 / opn2;
    case "%":
      return opn1 % opn2;
    case "^":
      return Math.pow(opn1, opn2);
    default:
      return 0;
  }
}

function opcomp(a, b) {
  return prioty[a] - prioty[b];
}

function calInfixExpression(exp) {
  var cs = [];
  var ns = [];
  exp = exp.replace(/\s/g, "");
  exp += '`';
  if (exp[0] === '-') {
    exp = "0" + exp;
  }
  var c;
  var op;
  var opn1;
  var opn2;
  for (var i = 0; i < exp.length; ++i) {
    c = exp[i];
    // 如果是操作符
    if (c in prioty) {
      // 如果右边不是左括号且操作符栈的栈顶元素优先权比右边大
      // 循环遍历进行连续运算
      while (c != '(' && cs.length && opcomp(cs[cs.length - 1], c) >= 0) {
        // 出栈的操作符
        op = cs.pop();
        // 如果不是左括号或者右括号，说明是运算符
        if (op != '(' && op != ')') {
          // 出栈保存数字的栈的两个元素
          opn2 = ns.pop();
          opn1 = ns.pop();
          // 将与操作符运算后的结果保存到栈顶
          ns.push(doop(op, opn1, opn2));
        }
      }
      // 如果右边不是右括号，保存到操作符栈中
      if (c != ')') cs.push(c);
    } else {
      // 多位数的数字的情况
      while (!(exp[i] in prioty)) {
        i++;
        c += exp[i];
      }
      ns.push(parseFloat(c));
      i--;
    }
  }
  return ns.length ? ns[0] : NaN;
}

var exp1 = calInfixExpression('5+3*4/2-2^3+5%2');
console.log(exp1);

实际上有效的递归调用函数(或过程)应包括两部分：递推规则(方法)，终止条件。

为保证递归调用正确执行，系统设立一个“递归工作栈”，作为整个递归调用过程期间使用的数据存储区。

每一层递归包含的信息如：参数、局部变量、上一层的返回地址构成一个“工作记录” 。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。

从被调函数返回调用函数的一般步骤：

1若栈为空，则执行正常返回。

2从栈顶弹出一个工作记录。

3将“工作记录”中的参数值、局部变量值赋给相应的变量；读取返回地址。

4将函数值赋给相应的变量。

5转移到返回地址。

1 队列的基本概念
队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。

队首(front) ：允许进行删除的一端称为队首。

队尾(rear) ：允许进行插入的一端称为队尾。 　　

例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。

队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ，即队列的修改是依先进先出的原则进行的

利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素，称为顺序队列。

队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。

1
function Queue() {
  this.rear = this.front = null;
  this.size = 0;
}
exports.Queue = Queue;
Queue.prototype = {
  clear: function () {
    this.rear = this.front = null;
    this.size = 0;
  },
  getHead: function () {
    return this.front ? this.front.data : null;
  },
  enQueue: function (elem) {
    if (this.front === null) {
      this.rear = this.front = {data: elem, next: null};
    } else {
      var p = {data: elem, next: null};
      this.rear.next = p;
      this.rear = p;
    }
    this.size++;
  },
  deQueue: function () {
    if (this.front) {
      var elem = this.front.data;
      this.front = this.front.next;
      if (this.front === null) {
        this.rear = null;
      }
      this.size--;
      return elem;
    } else {
      return null;
    }
  },
  queueTraverse: function (iterator) {
    var current = this.front;
    while (current) {
      if (iterator(current.data)) break;
      current = current.next;
    }
  },
  peekAt: function (index) {
    index = index || 0;

    if (index < this.size) {
      var current = this.front;
      for (var i = 0; i < index; i++) {
        current = current.next;
      }
      return current.data;
    }

    return null;
  },
  displayAll: function () {
    if (this.front === null) {
      return null;
    }

    var arr = [];
    var current = this.front;

    for (var i = 0, len = this.size; i < len; i++) {
      arr[i] = current.data;
      current = current.next;
    }

    return arr;
  }
};

var queue = new Queue();
queue.enQueue(1);
queue.deQueue();
queue.enQueue(2);
queue.enQueue(3);
console.log(queue.peekAt(0));
console.log(queue.peekAt(1));
console.log(queue.peekAt(2));
console.log(queue.peekAt(3));
console.log(queue.displayAll().join());

循环队列

顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(Circular Queue)。

在循环队列中进行出队、入队操作时，队首、队尾指针仍要加1，朝前移动。只不过当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时，其加1操作的结果是指向向量的下界0。

用模运算可简化为：i=(i+1)%MAX_QUEUE_SIZE ;

显然，为循环队列所分配的空间可以被充分利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，真正实用的顺序队列是循环队列。

1
// 循环队列
function CycleQueue() {
  this.base = {};
  this.front = this.rear = 0;
  this.MAXQSIZE = 100;
}
exports.CycleQueue = CycleQueue;
CycleQueue.prototype = {
  enQueue: function (data) {
    if ((this.rear + 1) % this.MAXQSIZE === 0) throw new Error('cycleQueue is already full!');

    this.base[this.rear] = data;
    this.rear = (this.rear + 1) % this.MAXQSIZE;
  },
  deQueue: function () {
    if (this.front === this.rear) throw new Error('cycleQueue is already empty');

    var elem = this.base[this.front];
    this.front = (this.front + 1) % this.MAXQSIZE;

    return elem;
  },
  clear: function () {
    this.base = {};
    this.front = this.rear = 0;
  },
  size: function () {
    return (this.rear - this.front + this.MAXQSIZE) % this.MAXQSIZE;
  },
  peekAt: function (index) {
    index = (index || 0 + this.MAXQSIZE) % this.MAXQSIZE;

    return this.base[index + this.front] || null;
  },
  getHead: function () {
    var elem = this.base[this.front];
    return elem ? elem : null;
  },
  queueTraverse: function (iterator) {
    for (var i = this.front, len = this.rear = this.front; i < len; i++) {
      if (iterator(this.base[i], i)) break;
    }
  },
  displayAll: function () {
    var base = [].slice.call(this.base);

    return base.slice(this.front, this.rear - this.front);
  }
};

var queue = new CycleQueue();
queue.enQueue(1);
queue.deQueue();
queue.enQueue(2);
queue.enQueue(3);
console.log(queue.peekAt(0));
console.log(queue.peekAt(1));
console.log(queue.peekAt(2));
1
var List = require('../linkedList/complete-LinkedList');
var Queue = require('./Queue').Queue;

// 事件类型，有序链表LinkList的数据元素类型
function Event(occurTime, eventType) {
  // 事件发生时刻
  this.occurTime = occurTime || 0;
  // 事件类型，0表示到达事件，1至4表示四个窗口的离开事件
  this.eventType = eventType || 0;
}

// 队列的数据元素类型
function QueueElemType(arrivalTime, duration) {
  // 到达时刻
  this.arrivalTime = arrivalTime || 0;
  // 办理事务所需时间
  this.duration = duration || 0;
}

function Bank() {
  // 事件表
  this.eventList = null;
  this.event = null;
  // 4个客户队列
  this.queues = new Array(4);
  this.totalTime = 0;
  this.customerNum = 0;
  this.closeTime = 0;
}
Bank.prototype = {
  cmp: function (event1, event2) {
    if (event1.occurTime < event2.occurTime)
      return -1;
    else if (event1.occurTime === event2.occurTime)
      return 0;
    else
      return 1;
  },
  // 初始化操作
  openForDay: function () {
    // 初始化累计时间和客户数为0
    this.totalTime = 0;
    this.customerNum = 0;
    // 初始化事件链表
    this.eventList = new List();
    // 设定第一个用户到达事件
    this.event = new Event(0, 0);
    // 插入到事件表
    this.eventList.orderInsert(this.event, this.cmp);

    // 置空队列
    for (var i = 0, len = this.queues.length; i < len; i++)
      this.queues[i] = new Queue();
  },
  // 处理客户到达事件
  customerArrived: function (durtime, intertime) {
    ++this.customerNum;

    // 生成随机数
    durtime = durtime || Math.floor(Math.random() * 20) + 1;   // 办理业务所需时间
    intertime = intertime || Math.floor(Math.random() * 5) + 1;  // 两个相邻客户时间间隔
    // 下一客户到达时刻
    var t = this.event.occurTime + intertime;
    // 银行尚未关门，插入事件表，这里还包括客户的离开时间
    if (t < this.closeTime && t + durtime < this.closeTime) {
      this.eventList.orderInsert(new Event(t, 0), this.cmp);
    }

    // 求长度最短队列
    var minQueueIndex = 0;
    var allEqualed = false;
    for(var i = 0, len = this.queues.length; i < len && this.queues[i + 1]; i++){
      if(this.queues[i].size === 0) {
        minQueueIndex = i;
        break;
      }
      if(this.queues[i].size < this.queues[i + 1].size){
        minQueueIndex = i;
        allEqualed = false;
      } else if(this.queues[i].size < this.queues[i + 1].size){
        minQueueIndex = i;
        allEqualed = true;
      } else {
        minQueueIndex = i + 1;
        allEqualed = false;
      }
    }
    // 如果所有队列长度都相等，取第一个
    if(allEqualed) minQueueIndex = 0;

    this.queues[minQueueIndex]
      .enQueue(new QueueElemType(this.event.occurTime, durtime));

    // 设定第i队列的一个离开事件并插入事件表
    if (this.queues[minQueueIndex].size === 1) {
      this.eventList.orderInsert(new Event(this.event.occurTime + durtime, minQueueIndex + 1), this.cmp);
    }
    // 保存最新客户的到达时间
    this.event.occurTime = t;
  },
  // 处理客户离开事件
  customerDeparture: function (type) {
    // 删除第i队列的排头客户
    var i = type - 1 || 0;
    var customer = this.queues[i].deQueue();
    // 累计客户逗留时间
    this.totalTime += this.event.occurTime - customer.arrivalTime;

    // 设定第i队列的一个离开事件并插入事件表
    if (this.queues[i].size) {
      customer = this.queues[i].getHead();
      this.eventList.orderInsert(new Event(this.event.occurTime + customer.duration, i), this.cmp);
    }
  },
  simulation: function (closeTime) {
    this.closeTime = closeTime || 0;
    this.openForDay();
    while (this.eventList.head) {
      var elem = this.eventList.delFirst().data;
      if (elem.eventType === 0)
        this.customerArrived();
      else
        this.customerDeparture(elem.eventType);
    }
    console.log('The average time is ' + this.totalTime / this.customerNum);
  }
};
new Bank().simulation(20);