概念

栈和队列都是简单的基础数据结构，栈(stack)实现的是后进先出(LIFO)策略，队列则是先进先出(FIFO)策略。
话不多说，我们看看LeetCode上tag为栈的几道题目。

LeetCode之栈

255.Verify Preorder Sequence in Binary Search Tree
给定数组，判断其是否是二叉搜索树(BST)的先序遍历，假定数组元素没有重复。
要求空间复杂度：O(1)

分析：BST的先序遍历特点是对于根节点而言左子树（小于根节点的值）在前，右子树在后。因此我们对数组遍历入栈，小于栈顶继续入栈，大于栈顶则一直pop出栈顶元素，直到遍历完数组后，只剩下最后一个（最大元素）为止。

优化：但是这样需要额外的栈存储空间，空间复杂度O(n)，因此在原数组上进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var isPreOrderBST = function (nums) {
  //two pointer i,j
  var i = -1, pre = -Number.MAX_VALUE;
  for (var j = 0; j < nums.length; j++) {
    if (nums[j] < pre) return false;
    //if the element is bigger than the pre, it's in the right.
    //Pop out all the smaller
    while (nums[j] > nums[i]) {
      pre = nums[i--];
    }
    //shift the right node to the left pointer
    nums[++i] = nums[j];
  }
  return true;
};

272.Closest Binary Search Tree Value II
找出BST中距目标值最近的K个值

这道题与Closest Binary Search Tree Value I中找出最近的值相比，相当于要进行K次搜索当前树中距离目标值最近的值。需要额外空间来存储搜索的中间结果。
我能想到的思路是对二叉树进行中序遍历，得到的有序数组可以进行二叉搜索target，再向两边进行外扩。但这样复杂度超过了O(n),而且题目中也给了提示，即用函数来得到下一个小值或大值。
这里直接用讨论区的解法（自己想不出这样的解法）。用两个栈，栈顶分别存储在遍历中得到的最大的小于target的数与最小的大于target的数，用getPredecessor()与getSuccessor()来获取下一个这样的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
var findKClosest = function (root, target, k) {
  var res = [];
  var preStack = [], sucStack = [];
  predecessor(root, preStack, target);
  successor(root, sucStack, target);
  var pre = getPredecessor(preStack);
  var suc = getSuccessor(sucStack);
  if (pre !== null && suc !== null && pre.val == suc.val) pre = getPredecessor(preStack);
  while (k-- > 0) {
    if (pre == null || Math.abs(suc.val - target) <= Math.abs(pre.val - target)) {
      res.push(suc.val);
      suc = getSuccessor(sucStack);
    } else if (suc == null || Math.abs(pre.val - target) < Math.abs(suc.val - target)) {
      res.push(pre.val);
      pre = getSuccessor(preStack);
    }
  }
  return res;
};
//init the smaller stack
var predecessor = function (root, stack, target) {
  var node = root;
  while (node !== null) {
    if (node.val == target) {
      stack.push(node);
      break;
    }
    else if (node.val < target) {
      stack.push(node);
      node = node.right;
    } else {
      node = node.left;
    }
  }
};
//init the larger stack
var successor = function (root, stack, target) {
  var node = root;
  while (node !== null) {
    if (node.val == target) {
      stack.push(node);
      break;
    } else if (node.val > target) {
      stack.push(node);
      node = node.left;
    } else {
      node = node.right;
    }
  }
};
//get next smaller element
var getPredecessor = function (stack) {
  if (stack.length == 0) {
    return null;
  }
  var pre = stack.pop();
  var cur = pre.left;
  while (cur !== null) {
    stack.push(cur);
    cur = cur.right;
  }
  return pre;
};
//get next larger element
var getSuccessor = function (stack) {
  if (stack.length == 0) return null;
  var suc = stack.pop();
  var cur = suc.right;
  while (cur !== null) {
    stack.push(cur);
    cur = cur.left;
  }
  return suc;
};

439.Ternary Expression Parser
解析三元表达式，”T”与”F”分别表示True与False，数字均为单位
Input: “T?T?F:5:3”
Output: “F”

分析：这道题目倒是栈的典型应用，从右至左字符入栈，遇到栈顶为’?’时，根据当前元素判断表达式结果是下一个出栈字符还是下下下个出栈字符，并将结果再压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var parseTernary = function (str) {
  var stack = [];
  for (var i = str.length - 1; i >= 0; i--) {
    if (stack.length > 0 && stack[stack.length - 1] == '?') {
      stack.pop();
      var first = stack.pop();
      stack.pop(); //pop out ':'
      var second = stack.pop();
      if (str[i] == 'T') {
        stack.push(first);
      } else {
        stack.push(second);
      }
    } else {
      stack.push(str[i]);
    }
  }
  return stack[0];
};

栈的典型应用还有构建数学表达式的前缀表达式或者后缀表达式，在某些使用递归的场合也可以用栈来实现，比如二叉树的三种遍历，如果有空，我会后文加上这部分。