数据结构之栈

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的
末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞在这一摞盘子的最上面。

栈的创建

实现一个栈,当务之急是决定存储数据的底层数据结构。这里采用的是数组

1. 创建一个类来表示栈, 声明stack类

function Stack() {
  // 各种属性和方法的声明
}

2. 首先,我们需要一种数据结构来保存栈里的元素。可以选择数组:

var items = []

3. 为我们的栈声明一些方法

push(element(s)) : 添加一个或几个新元素到栈顶
pop() : 移除栈顶的元素，　同时返回被移除的元素
peek() : 返回栈顶的元素, 不对栈做任何修改
isEmpty() : 如果栈里没有任何元素就返回 true, 否则返回 false 
clear() : 移除栈里所有的元素
size() : 返回栈里的元素个数, 和数组的 length 很相似

• 实现 push, 该方法只添加元素到栈顶,也就是栈的末尾

this.push = function(element) {
  items.push(element)
}

• pop 方法，这个方法主要用来移除栈里的元素。栈遵从LIFO原则,因此移出的是最后添加进去的元素

this.pop = function() {
  return items.pop()
}

• 想知道栈里最后添加的元素是什么,可以用peek方法。这个方法将返回栈顶的元素

this.peek = function() {
  return items[items.length - 1]
}

包含三个元素的栈，最后一个 length - 1

]

• isEmpty ,如果栈为空的话将返回 true ,否则就返回 false

this.isEmpty = function() {
  return items.length === 0
}

• 类似于数组的 length 属性,我们也能实现栈的 length 。对于集合,最好用 size 代替 length 。因为栈的内部使用数组保存元素,所以能简单地返回栈的长度

this.size = function () {
  return items.length
}

• clear 方法用来移除栈里所有的元素,把栈清空

this.clear = function () {
  items = []
}

• 为了检查栈里的内容,我们来实现一个辅助方法,叫 print 。它会把栈里的元素都输出到控制台

this.print = function () {
  console.log(items.toString())
}

• 上面我们就创建了栈，全部代码

function Stack () {

  let items = []

  this.push = function (elements) {
     items.push(elements)
  }

  this.pop = function () {
    return items.pop()
  }

  this.peek = function () {
    return items[items.length - 1]
  }

  this.isEmpty = function () {
    return items.length === 0
  }

  this.size = function () {
    return items.length
  }

  this.clear = function () {
    items = []
  }

  this.print = function () {
    console.log(items.toString())
  }

}

4. 使用Stack 类

1. 初始化 Stack 类
let stack = new Stack()

stack.isEmpty()  // true

stack.push(5)
stack.push(8)

stack.peek()  // 8
stack.print()  // 5, 8

stack.push(11)
stack.size()  // 3

stack.isEmpty()  // false

stack.push(15)

对栈的操作

stack.pop()
stack.pop()

stack.print()  // 5,8

去元素的过程

从十进制到二进制

要把十进制转化成二进制,我们可以将该十进制数字和2整除(二进制是满二进一),直到结
果是0为止

二进制

// javaScript有数字类型,但是它不会区分究竟是整数还是浮点数。因此,要使用 Math.floor 函数让除法的操作仅返回整数部分
function divideBy2 (decNumber) {
  var remStack = new Stack(),
      rem,
      binaryString = ''
  
  // 满足和2做整除的条件
  while (decNumber > 0) {
    // 当前结果和2的余数,放到栈里
    rem = Math.floor(decNumber % 2)
    remStack.push(rem)
    // 让结果和2做整除
    decNumber = Math.floor(decNumber / 2)
  }
  // pop 方法把栈中的元素都移除,把出栈的元素变成连接成字符串
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString()
  }
  return binaryString
}

console.log(divideBy2(233))  // "11101001"

将十进制转成二进制时,余数是0或1;在将十进制转成八进制时,余数是0到8之间的数;但是将十进制转成16进制时,余数是0到8之间的数字加上A、B、C、D、E和F(对应10、11、12、13、14和15)。因此,我们需要对栈中的数字做个转化才可以(行{1} 和行 {2})

// 能把十进制转换成任何进制
function baseConverter(decNumber, base){
  var remStack = new Stack(),
      rem,
      baseString = '',
      digits = '0123456789ABCDEF'; //{1} 
  while (decNumber > 0){
    rem = Math.floor(decNumber % base);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / base);
  } 
  while (!remStack.isEmpty()){
    baseString += digits[remStack.pop()]; //{2}
  }
  return baseString;
}

回文

使用栈,可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后,栈内就保存了一个反转后的字符串,最后的字符在栈顶,第一个字符在栈底

function isPalindrome(word) {
  var s = new Stack()
  for(var i = 0; i < word.length; i++) {
    s.push(word[i])
  }
  var rword = ''
  while (s.size() > 0) {
    rword += s.pop()
  }
  return word === rword ? true : false
}

console.log(isPalindrome('12321'))  // true
console.log(isPalindrome('abcdcba'))  // true
console.log(isPalindrome('1236361'))  // false