队列

队列是一种特殊的线性表，其特殊之处在于，它只允许你在队列的头部删除元素，在队列的尾部添加新元素

队列的方法

• enqueue 从队列尾部添加一个元素
• dequeue 从队列头部删除一个元素
• head 返回头部的元素，不是删除
• size 返回队列的大小
• clear 清空队列
• isEmpty 判断队列是否为空
• tail 返回队列尾结点

function Queue() {
  var items = []   // 存储数据

  // 向队列尾部添加一个元素
  this.enqueue = function(item) {
    items.push(item)
  }

  // 移除队列头部的元素
  this.dequeue  = function() {
    return items.shift()
  }

  // 返回队列头部的元素
  this.head = function() {
    return items[0]
  }

  // 返回队列尾部的元素
  this.tail = function() {
    return items[items.length - 1]
  }

  // 返回队列的大小
  this.size = function() {
    return items.length
  }

  // 清空队列
  this.clear = function() {
    items = []
  }

  // 判断队列是否为空
  this.isEmpty = function() {
    return items.length === 0
  }
}

题目

• 有一个数组a[100]存放 0-99，要求每隔两个数删掉一个数，到末尾时循环至开头继续执行，求最后一个被删掉的数

  思路：先将这100个数放入队列，使用while循环，while 循环终止的条件是队列里只有一个元素。使用 index 变量从 0 开始计数，步骤如下：
  1. 从队列头部删除一个元素，index + 1
  2. 如果index%3==0，就说明这个元素是需要删除的元素，如果不等于0，就不是需要被删除的元素，则把它添加到队列的尾部

function del_ring(arr_list) {
  // 把数组里的元素都放到队列中
  var queue = new Queue()
  for(var i=0; i< arr_list.length; i++) {
    queue.enqueue(arr_list[i])
  }

  var index = 0
  while(queue.size() != 1) {
    // 弹出一个元素, 判断是否需要删除
    var item = queue.dequeue()
    index += 1
    // 每隔两个就要删除掉一个, 那么不是被删除的元素就放回队列尾部
    if(index%3 != 0) {
      queue.enqueue(item)
    }
  }
  return queue.head()
}

var arr_list = []
for(var i=0; i<100; i++) {
  arr_list.push(i)
}

console.log(del_ring(arr_list))    // 90

• 用队列计算裴波那契数列的第n项

  思路分析：裴波那契数列的前两项是 1 1，此后每一项都是该项前面两项之和，即 f(n) = f(n-1) + f(n-2)
  先将两个 1 添加到队列中，之后使用 while 循环，用 index 计数，循环终止的条件是 index < n -2
  1.使用dequeue方法从队列头部删除一个元素，该元素为 del_item
  2.使用head方法获得队列头部的元素，该元素为 head_item
  3.del_item + head_item = next_item， 将next_item放入队列，只能从尾部添加元素
  4.index + 1
  循环结束时，队列里面有两个元素

function fibonacci(n) {
  queue = new Queue()
  var index = 0
  // 先放入斐波那契数列的前两个数值
  queue.enqueue(1)
  queue.enqueue(1)
  while(index < n-2) {
    // 出队列一个元素
    var del_item = queue.dequeue()
    // 取出队列头部元素
    var head_item = queue.head()
    var next_item = del_item + head_item
    // 将计算结果放入队列
    queue.enqueue(next_item)
    index += 1
  }

  queue.dequeue()
  return queue.head()
}

• 用两个队列实现一个栈

  两个队列分别命名为 queue_1，queue_2，实现的思路如下：
  1 push，实现push方法时，如果两个队列都为空，那么默认向queue_1里添加数据，如果有一个不为空，则向这个不为空的队列里添加数据
  2 top， 两个队列，或者都为空，或者有一个不为空，只需要返回不为空的队列的尾部元素即可。
  3 pop， pop方法比较复杂，pop方法要删除的是栈顶，但这个栈顶元素其实是队列的尾部元素。每一次做pop操作时，将不为空的队列里的元素一次删除并放入到另一个队列中直到遇到队列中只剩下一个元素，删除这个元素，其余的元素都跑到之前为空的队列中了。
  在具体实现中，我们定义额外的两个变量，data_queue和empty_queue，data_queue始终指向那个不为空的队列，empty_queue始终指向那个为空的队列。

function QueueStack() {
  var queue_1 = new Queue()
  var queue_2 = new Queue()
  var data_queue = null       // 放数据的队列
  var empty_queue = null       // 空队列, 备份使用

  // 确认哪个队列放空数据, 哪个队列做备份空队列
  var init_queue = function() {
    // 都为空, 默认返回 queue_1
    if(queue_1.isEmpty() && queue_2.isEmpty()) {
      data_queue = queue_1
      empty_queue = queue_2
    } else if(queue_1.isEmpty()) {
      data_queue = queue_2
      empty_queue = queue_1
    } else {
      data_queue = queue_1
      empty_queue = queue_2
    }
  }

  // push 方法
  this.push = function(item) {
    init_queue()
    data_queue.enqueue(item)
  }

  // top 方法
  this.top = function() {
    init_queue()
    return data_queue.tail()
  }

  // pop 方法
  /**
   * pop方法要弹出栈顶元素, 这个栈顶元素, 其实就是queue的队尾元素
   * 但是队尾元素是不能删除的, 我们可以把 data_queue里的元素(除了队尾元素) 都移除放入到empty_queue中
   * 最后移除data_queue的队尾元素并返回
   * data_queue 和 empty_queue 交换了身份
   */

    this.pop = function() {
      init_queue()
      while(data_queue.size() > 1) {
        empty_queue.enqueue(data_queue.dequeue())
      } 
      return data_queue.dequeue()
   }
}
var q_stack = new QueueStack()
q_stack.push(1)
q_stack.push(2)
q_stack.push(4)

console.log(q_stack.top())    // 栈顶4
console.log(q_stack.pop())    // 移除4
console.log(q_stack.top())    // 栈顶变为 2
console.log(q_stack.top())    // 移除 2

• 杨辉三角

function print_yanghui(n) {
  var queue = new Queue()
  queue.enqueue(1)
  // 第一层 for 循环控制打印几层
  for(var i=1; i<=n; i++) {
    var line = ""
    var pre = 0
    // 第二层 for 循环控制答应第i层
    for(var j=0; j<i; j++) {
      var item = queue.dequeue()
      line += item + " "
      // 计算下一行的内容
      var value = item + pre
      pre = item
      queue.enqueue(value)
    }
    // 每一层最后一个数字是1, 上面的for循环没有计算最后一个数
    queue.enqueue(1)
    console.log(line)
  }
}
print_yanghui(10)