栈和队列

1. 用栈实现队列

232

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

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

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
var MyQueue = function() {
    this.stackIn=[]
    this.stackOut=[]
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stackIn.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    let size=this.stackOut.length
    if(size){
       return this.stackOut.pop()
    }else{
        while(this.stackIn.length){
            this.stackOut.push(this.stackIn.pop())
        }
        return this.stackOut.pop()
    }

};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    let x=this.pop()
    this.stackOut.push(x)
    return x
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.stackIn.length && !this.stackOut.length
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

2. 用队列实现栈

225

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

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

在此用一个队列来实现的

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
var MyStack = function() {
     this.queue=[]
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.queue.push(x)
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
    let size=this.queue.length
    while(size-->1){
        this.queue.push(this.queue.shift())
    }
    return this.queue.shift()
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
    let x=this.pop()
    this.queue.push(x)
    return x
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.queue.length
};

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

3. 有效的括号

20

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

1.创建一个HashMap，把括号配对放进去。
2.创建一个stack（array），for循环遍历字符串，对于每一个字符，如果map里有这个key，那说明它是个左括号，从map里取得相对应的右括号（为什么？）把它push进stack里。否则的话，它就是右括号，需要pop出stack里的最上层字符然后看它是否等于当前的字符。如果不相符，则返回false。
3.循环结束后如果stack不为空，说明还剩一些左括号没有被闭合，返回false。否则返回true。

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
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let isValidMap=new Map()
    isValidMap.set('[',']')
    isValidMap.set('{','}')
    isValidMap.set('(',')')

    let stack=[]
    for(let item of s){
        if(isValidMap.has(item)){
            stack.push(isValidMap.get(item))
        }else{
            if(stack.pop()!==item){
                return false
            }
        }
        
    }
    if(stack.length!==0){
        return false
    }
    return true
};

4. 删除字符串中的所有相邻重复项

1047

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

而消除一对相邻重复项可能会导致新的相邻重复项出现，如从字符串 abba\text{abba}abba 中删除 bb\text{bb}bb 会导致出现新的相邻重复项 aa\text{aa}aa 出现。因此我们需要保存当前还未被删除的字符。一种显而易见的数据结构呼之欲出：栈。我们只需要遍历该字符串，如果当前字符和栈顶字符相同，我们就贪心地将其消去，否则就将其入栈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
    let stack=[]
    for(let item of s){
        let c=null
        if(stack.length && item===(c=stack.pop())){
            continue
        }
        c&&stack.push(c)
        stack.push(item)
    }
    return stack.join('')
};

5. 逆波兰表达式求值

150

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
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
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    let stack=[]
    for(let item of tokens){
        if(item==='+'||item==='-'||item==='*'||item==='/'){
            let num2=stack.pop()
            let num1=stack.pop()
            switch(item){
                case '+':
                    stack.push(num1 + num2);
                    break;
                case '-':
                    stack.push(num1 - num2);
                    break;
                case '*':
                    stack.push(num1 * num2);
                    break;
                case '/':
                    stack.push(num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2)); //注意除法时正数向下取整，负数向上取整
                    
                    break;
            }
        }else{
            stack.push(parseInt(item))
        }
        
    }
    return stack.pop()
};

6. 滑动窗口最大值

239 难

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

1
2
3
4
5
// 设计单调队列的时候，pop，和push操作要保持如下规则：

// pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
// push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

7. 前k个高频元素

347

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

这道题目主要涉及到如下三块内容：

  1. 要统计元素出现频率

  2. 对频率排序

  3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

因为js中没有堆这种数据结构，如果有梦想的人，可以自己通过类去实现一个堆的结构，然后再去做本题目

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const map=new Map()
    for(let item of nums){
        map.set(item,(map.get(item)||0)+1) // 通过哈希表统计各个数字出现的次数
    }
    return [...map].sort((a,b)=>b[1]-a[1]).map(item=>item[0]).slice(0,k) // 找出前k个高频的元素
};