1、有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解答：利用栈的后进先出的特性，如果是括号的左边则进栈，否则查看栈顶和当前括号字符是否闭合。最后查看栈是否为空，为空则有效，否则无效

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isValid = function(s) {
  6.   const map = new Map([['(', ')'], ['[', ']'], ['{', '}']])
  7.   const stack = []
  8.   for (let i = 0; i < s.length; i ++) {
  9.     const char = s[i]
  10.     if (map.has(char)) {
  11.       stack.push(char)
  12.     } else {
  13.       const topChar = stack.pop()
  14.       if (map.get(topChar) !== char) return false
  15.     }
  16.   }
  17.   return stack.length === 0
  18. };

2、栈的最小值

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

解答：难点在于查找min。可以使用两个栈，其中一个栈专门用来保存最小值。利用栈的后进先出的特性可以保证栈顶总是最小值。

  1. /**
  2.  * initialize your data structure here.
  3.  */
  4. var MinStack = function() {
  5.   this.stack = []
  6.   this.minStack = []
  7. };
  9. /** 
  10.  * @param {number} x
  11.  * @return {void}
  12.  */
  13. MinStack.prototype.push = function(x) {
  14.   this.stack.push(x)
  15.   if (
  16.     this.minStack.length === 0 ||
  17.     this.minStack[this.minStack.length - 1] >= x
  18.   ) {
  19.     this.minStack.push(x)
  20.   }
  21. };
  23. /**
  24.  * @return {void}
  25.  */
  26. MinStack.prototype.pop = function() {
  27.   if (this.stack.length === 0) throw new Error()
  28.   const top = this.stack.pop()
  29.   if (top === this.minStack[this.minStack.length - 1]) this.minStack.pop()
  30. };
  32. /**
  33.  * @return {number}
  34.  */
  35. MinStack.prototype.top = function() {
  36.   return this.stack[this.stack.length - 1]
  37. };
  39. /**
  40.  * @return {number}
  41.  */
  42. MinStack.prototype.getMin = function() {
  43.   if (this.minStack.length === 0) throw new Error()
  44.   return this.minStack[this.minStack.length - 1]
  45. };
  47. /**
  48.  * Your MinStack object will be instantiated and called as such:
  49.  * var obj = new MinStack()
  50.  * obj.push(x)
  51.  * obj.pop()
  52.  * var param_3 = obj.top()
  53.  * var param_4 = obj.getMin()
  54.  */

3、用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

解答1：难点在于队列是先进先出，而栈是先进后出。也就是说如果要使用队列模拟栈，则队列中元素顺序应该是和栈相反。简单来说，就是每次push的元素需要放在队首，这样每次push操作后，队列的顺序就是和栈相反。为了达到这个目的，可以使用一个辅助队列，一个存放数据的数据队列，每次将新元素push进辅助队列，然后如果数据队列中有元素，则将数据队列中的元素依次出队放入辅助队列。然后交换两个队列。这样每次push结束后辅助队列总是空的，数据队列中则放置所有的数据且顺序和元素push顺序相反。

  2. var MyStack = function() {
  3.   this.queue1 = []
  4.   this.queue2 = []
  5. };
  7. /** 
  8.  * @param {number} x
  9.  * @return {void}
  10.  */
  11. MyStack.prototype.push = function(x) {
  12.   this.queue2.push(x)
  13.   while (this.queue1.length) {
  14.     this.queue2.push(this.queue1.shift())
  15.   }
  16.   let temp = this.queue1
  17.   this.queue1 = this.queue2
  18.   this.queue2 = temp
  19. };
  21. /**
  22.  * @return {number}
  23.  */
  24. MyStack.prototype.pop = function() {
  25.   return this.queue1.shift()
  26. };
  28. /**
  29.  * @return {number}
  30.  */
  31. MyStack.prototype.top = function() {
  32.   return this.queue1[0]
  33. };
  35. /**
  36.  * @return {boolean}
  37.  */
  38. MyStack.prototype.empty = function() {
  39.   return this.queue1.length === 0
  40. };
  42. /**
  43.  * Your MyStack object will be instantiated and called as such:
  44.  * var obj = new MyStack()
  45.  * obj.push(x)
  46.  * var param_2 = obj.pop()
  47.  * var param_3 = obj.top()
  48.  * var param_4 = obj.empty()
  49.  */

解答2：根据解答1，其实使用一个队列即可完成，具体方法是push操作时每次push新元素到队列中，假设队列长度为n，然后将队列的前n-1个元素依次出队然后再入队即可。

  2. var MyStack = function() {
  3.   this.queue = []
  4. };
  6. /** 
  7.  * @param {number} x
  8.  * @return {void}
  9.  */
  10. MyStack.prototype.push = function(x) {
  11.   this.queue.push(x)
  12.   let len = this.queue.length
  13.   while (len > 1) {
  14.     this.queue.push(this.queue.shift())
  15.     len --
  16.   }
  17. };
  19. /**
  20.  * @return {number}
  21.  */
  22. MyStack.prototype.pop = function() {
  23.   return this.queue.shift()
  24. };
  26. /**
  27.  * @return {number}
  28.  */
  29. MyStack.prototype.top = function() {
  30.   return this.queue[0]
  31. };
  33. /**
  34.  * @return {boolean}
  35.  */
  36. MyStack.prototype.empty = function() {
  37.   return this.queue.length === 0
  38. };
  40. /**
  41.  * Your MyStack object will be instantiated and called as such:
  42.  * var obj = new MyStack()
  43.  * obj.push(x)
  44.  * var param_2 = obj.pop()
  45.  * var param_3 = obj.top()
  46.  * var param_4 = obj.empty()
  47.  */

4、用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

解答1：和上题一样，需要改变顺序。利用栈先进后出的特性，将一个栈的元素依次取出放进另一个栈，就完成了顺序的颠倒。因此使用一个辅助栈和一个存放数据的数据栈，数据栈存放最终的数据，辅助栈用于颠倒顺序。每次push操作的时候先将数据栈的元素依次放进辅助栈（还原顺序），然后将新元素推入辅助栈，再将辅助栈的元素推入数据栈。最终得到一个顺序颠倒的数据栈。

  2. var MyQueue = function() {
  3.   this.stack1 = []
  4.   this.stack2 = []
  5. };
  7. /** 
  8.  * @param {number} x
  9.  * @return {void}
  10.  */
  11. MyQueue.prototype.push = function(x) {
  12.   while (this.stack1.length) {
  13.     this.stack2.push(this.stack1.pop())
  14.   }
  15.   this.stack2.push(x)
  16.   while (this.stack2.length) {
  17.     this.stack1.push(this.stack2.pop())
  18.   }
  19. };
  21. /**
  22.  * @return {number}
  23.  */
  24. MyQueue.prototype.pop = function() {
  25.   return this.stack1.pop()
  26. };
  28. /**
  29.  * @return {number}
  30.  */
  31. MyQueue.prototype.peek = function() {
  32.   return this.stack1[this.stack1.length - 1]
  33. };
  35. /**
  36.  * @return {boolean}
  37.  */
  38. MyQueue.prototype.empty = function() {
  39.   return this.stack1.length === 0
  40. };
  42. /**
  43.  * Your MyQueue object will be instantiated and called as such:
  44.  * var obj = new MyQueue()
  45.  * obj.push(x)
  46.  * var param_2 = obj.pop()
  47.  * var param_3 = obj.peek()
  48.  * var param_4 = obj.empty()
  49.  */

解答2：上述方法逻辑清晰，但是每次push都需要进行两次while循环比较耗费性能。实际从解答1得知，数据栈存放的元素顺序是和队列的顺序相反的，也就是说每次只要数据栈不为空，每次pop的时候从数据栈出栈一个元素即可。如果数据栈为空，再将辅助栈元素全部推进数据栈即可。这里的关键在于将方法一每次push操作进行while循环改成数据栈为空时再进行while循环。

  2. var MyQueue = function() {
  3.   this.stack1 = []
  4.   this.stack2 = []
  5.   this.front = null
  6. };
  8. /** 
  9.  * @param {number} x
  10.  * @return {void}
  11.  */
  12. MyQueue.prototype.push = function(x) {
  13.   this.stack2.push(x)
  14.   if (this.stack2.length === 1) this.front = x // 保存辅助栈的栈底元素，当将辅助栈推送到数据栈时，栈底元素就变成了队首元素，也就是peek的返回值
  15. };
  17. /**
  18.  * @return {number}
  19.  */
  20. MyQueue.prototype.pop = function() {
  21.   if (this.empty()) throw new RangeError('cannot pop element from empty queue.')
  22.   if (this.stack1.length === 0) {
  23.     while (this.stack2.length) {
  24.       this.stack1.push(this.stack2.pop())
  25.     }
  26.   }
  27.   return this.stack1.pop()
  28. };
  30. /**
  31.  * @return {number}
  32.  */
  33. MyQueue.prototype.peek = function() {
  34.   if (this.stack1.length) return this.stack1[this.stack1.length - 1]
  35.   return this.front
  36. };
  38. /**
  39.  * @return {boolean}
  40.  */
  41. MyQueue.prototype.empty = function() {
  42.   return this.stack1.length === 0 && this.stack2.length === 0
  43. };
  45. /**
  46.  * Your MyQueue object will be instantiated and called as such:
  47.  * var obj = new MyQueue()
  48.  * obj.push(x)
  49.  * var param_2 = obj.pop()
  50.  * var param_3 = obj.peek()
  51.  * var param_4 = obj.empty()
  52.  */