Skip to main content

栈的定义及实现

列表是一种最自然的数据组织方式，如果数据存储的顺序不重要，且无需对数据进行查找，那么列表是一种再好不过的数据结构，但对于其它一些应用，列表就显得太过简陋，我们需要一种更复杂的数据结构——栈

一、 什么是栈​

栈是一种后进先出（LIFO，Last-in-first-out） 的数据结构，其数据只能在栈顶添加或删除，因此操作高效快速。

栈顶：栈内的元素只能通过列表的一端访问，这一端称为栈顶。

由于栈后入先出的特点，所以任何不在栈顶的元素都无法访问，要得到栈底的元素，需要先拿掉上面的元素。

举个例子

题目：

有 6 个元素 6，5，4，3，2，1 按顺序进栈，问下列哪一个不是合法的出栈顺序？

  • A：5 4 3 6 1 2 （√）
  • B：4 5 3 2 1 6 （√）
  • C：3 4 6 5 2 1 （×）
  • D：2 3 4 1 5 6 （√）

题目所说的按顺序进栈指的不是一次性全部进栈，而是有进有出，进栈顺序为 6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析：

  • A 答案：65 进栈，5 出栈，4 进栈出栈，3 进栈出栈，6 出栈，21 进栈，1 出栈，2 出栈（整体入栈顺序符合 654321）
  • B 答案：654 进栈，4 出栈，5 出栈，3 进栈出栈，2 进栈出栈，1 进栈出栈，6 出栈（整体的入栈顺序符合 654321）
  • C 答案：6543 进栈，3 出栈，4 出栈，之后应该 5 出栈而不是 6，所以错误。
  • D 答案：65432 进栈，2 出栈，3 出栈，4 出栈，1 进栈出栈，5 出栈，6 出栈。符合入栈顺序。

二、栈的操作​

1、入栈​

使用 push() 方法，将一个元素压入栈。

2、出栈​

使用 pop() 方法，将一个元素弹出栈。

3、预览栈顶元素​

pop() 方法虽然可以访问栈顶元素，但调用后栈顶元素即被删除了，而 peek() 方法则只返回栈顶元素，不删除它，用来预览栈顶元素。

4、记录栈顶元素位置​

我们用变量 top 来记录栈顶元素的位置，标记哪里可以加入新元素；

当向栈内压入元素时，top 值增大，当从栈内弹出元素时，top 值减小。

5、清除栈内所有元素​

用 clear() 方法来清除栈内所有元素

6、记录栈内元素个数​

用变量 length 来记录栈内元素的个数

7、表示栈内是否含有元素​

用 empty 属性来表示栈内是否含有元素，用 length 也可达到同样的目的

三、栈的实现​

1、定义 Stack 类​

function Stack() {
  this.dataStore = []
  this.top = 0
  this.push = push
  this.pop = pop
  this.peek = peek
}

这里用数组 dataStore 保存栈内元素，构造函数将其初始化为一个空数组。

变量 top 记录栈顶位置，被构造函数初始化为 0，表示栈顶对应数组的起始位置 0。

2、实现 push 方法​

当向栈中压入一个新元素时，需要将其保存在数组中变量 top 所对应的位置，然后将 top 值加 1，让其指向数组中下一个空位置。

function push(element) {
  this.dataStore[this.top++] = element
}

3、实现 pop 方法​

pop 和 push 相反——返回栈顶元素，同时将变量 top 的值减 1。

function pop() {
  return this.dataStore[--this.top]
}

关于 i++ 和 ++i


- 使用 i++ 时，i 先将自身的值赋值给变量 a，然后再自增 1 - 使用 ++i 时，i 先将自身的值自增 1，再将自增后的值赋值给变量 a

4、实现 peek 方法​

peek 方法返回数组的第 top-1 个位置的元素，即栈顶元素。

function peek() {
  return this.dataStore[this.top - 1]
}

如果对一个空栈调用 peek 方法，结果为 undefined（因为栈是空的，栈顶没有任何元素）

5、实现 length 方法​

length 方法通过返回变量 top 值的方法返回栈内的元素个数，可用来了解栈内存储了多少个元素。

function length() {
  return this.top
}

6、实现 clear 方法​

clear 方法将变量 top 的值设为 0，用来清空一个栈。

function clear() {
  this.top = 0
}

7、测试 Stack 类的实现​

var s = new Stack()

s.push('a')
s.push('b')
s.push('c')

console.log(s.length()) // 3
console.log(s.peek())   // "c"

var poped = s.pop()

console.log(poped)      // "c"
console.log(s.peek())   // "b"

s.push("d")

console.log(s.peek())   // "d"

s.clear()

console.log(s.length()) // 0
console.log(s.peek())   // undefined

四、栈的应用​

1、回文判断​

回文：指的是一个单词、短语或数字，从前往后写和从后往前写是一样的，比如：“dad”、“racecar”。

使用栈可以轻松判断一个字符串是否是回文：

将字符串的每个字符按从左到右的顺序压入栈，栈内就保存了一个反转后的字符串，尾字符在栈顶，而首字符在栈底；

通过持续弹出栈内的每个元素就可以得到一个新的字符串，这个字符串与原字符串的顺序相反；

只需比较新字符串和原字符串是否相等即可。

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

var word1 = 'hello'
var word2 = 'racecar'

console.log(isPalindrome(word1))  // false
console.log(isPalindrome(word2))  // true

2、阶乘计算​

递归可以用来实现阶乘运算

2-1、普通函数递归实现阶乘​

function factorial(n) {
  if (n === 0) {
    return 1
  } else {
    return n * factorial(n - 1)
  }
}

console.log(factorial(5)) // 120

2-2、栈模拟递归实现阶乘​

使用栈来模拟递归实现阶乘，先将数字从 5 到 1 压入栈，然后使用一个循环，将数字挨个弹出连乘即可。

function factorial(n) {
  var s = new Stack()
  while (n > 1) {
    s.push(n--)
  }
  var product = 1
  while (s.length() > 0) {
    product *= s.pop()
  }
  return product
}

console.log(factorial(5)) // 120