介绍

栈（stack）又名 堆栈。它是一种操作受限的线性存储结构，受限规则为添加和删除栈的元素必须遵循 LIFO模式（后进先出）。

以 被封住的底的羽毛球桶 为例，想要取一个球，需要从桶口取，放一个球进去，也必须放在最靠近桶口的位置。最先放进去的球，最后才能取出来，后放进去的球会先取出来。

从 stack 英文介绍--堆叠，也可以看出，栈这种数据结构就像是堆叠在一起的货物，想要取出下面的货物，就需要先搬开上面的货物。

理解了这种数据结构，我们看下关于栈的一些概念：

• 栈顶: 栈可以存取操作的这一端，对应桶口。
• 栈底：栈存取操作授权受限的一端，对应桶底。
• 入栈：也叫压栈、进栈。即向站内新插入元素。
• 出栈：也叫退栈。即从栈中删除元素。
• 空栈：栈内元素为空时，称为空栈。

分类

栈分为顺序栈和链栈。

• 顺序栈：指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设有指针top指示栈顶元素在顺序栈中的位置；另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。
• 链栈：指采用链式存储结构实现的栈，通常链栈用单链表表示。

顺序栈是静态分配的，最大空间容量受到限制，当栈满时再入栈，需要寻求一组更大的连续存储单元作为新的栈，将原栈数据复制进去，插入新的元素。

链栈插入新的元素使动态分配的，一般不需要考虑空间不够的情况。

代码实现

顺序栈

function Stack() {
  this.dataStore = []; // 保存栈内元素 
  this.top = 0; // 标记可以插入新元素的位置，栈内元素增加变量增加，减少，变量减少 
  this.push = push; // 入栈操作 
  this.pop = pop; // 出栈操作 
  this.peek = peek; // 返回栈顶元素 
  this.clear = clear; // 清空栈 
  this.length = length; // 返回栈的长度 
}
function pop() {
  return this.dataStore[--this.top];
}
function push(element) {
  this.dataStore[this.top++] = element;
}
function peek() {
  return this.dataStore[this.top - 1];
}
function clear() {
  this.top = 0;
}
function length() {
  return this.top;
}

链栈

function LinkStack() {
  this.length = 0
  this.top = null // 栈顶指针
  this.push = push
  this.pop = pop
  this.clear = clear
  this.toString = toString
}

function Node(data) {
  this.data = data
  this.next = null
}

// 入栈
function push(data) {
  const node = new Node(data);
  
  if (!this.top) {
    this.top = node
    this.length++
    return true
  } else {
    let current = this.top
    node.next = current

    this.top = node
    this.length++
    return true
  }
}

// 出栈
function pop() {
  let current = this.top
  if (current) {
    this.top = current.next
    current.next = null
    this.length--
    return current.data
  } else {
    throw "error null stack"
  }
}

// 清空栈
function clear() {
  this.top = null
  this.length = 0
  return true
}

// 打印
function toString() {
  let str = ''
  let current = this.top
  while (current) {
    str += current.data + ' '
    current = current.next
  }
  return str
}

应用

符合 LIFO 原则的地方都可以用栈来实现。

• JavaScrip中的调用栈
• 许多程序提供的撤销/重做功能
• 括号匹配
• 通过后缀表达式求值
• 判断回文字符串

栈在括号匹配算法中的应用

function isRight(str) {
  let stack = new LinkStack()

  // 从字符串中提取括号
  let rstr = ''
  for (let i = 0; i < str.length; i++) {
    if (['(', ')', '[', ']', '{', '}'].includes(str[i])) {
      rstr += str[i]
    }
  }

  for (let i = 0; i < rstr.length; i++) {
    // 左括号入栈 右括号跳过在之后与栈顶左括号匹配
    if (['(', '[', '{'].includes(str[i])) {
      stack.push(rstr[i])
      continue
    }

    if (stack.length) {
      switch (stack.top.data + rstr[i]) {
        case '()':
          stack.pop()
          break
        case '[]':
          stack.pop()
          break
        case '{}':
          stack.pop()
          break
        default:
          return false
      }
    } else {
      // 含有右括号，但左括号已经匹配完了
      return false
    }
  }
  // 栈为空，表示所有左括号与右括号都匹配上了
  return !stack.length
}

console.log(isRight('(()){}{}'))

栈在判断是否为回文字符串中的应用

function isPalindrome(word) {
  let s = new Stack();
  for (let i = 0, len = word.length; i < len; i++) {
    s.push(word[i]);
  }
  let rword = "";
  while (s.length() > 0) {
    rword += s.pop();
  } 0
  if (word == rword) {
    return true;
  } else {
    return false;
  }
}
let w1 = "abcdcba";
let w2 = "ald;jfkd";
console.log(isPalindrome(w1)) // true
console.log(isPalindrome(w2)) // false