前端力扣刷题_数据结构篇（队列&栈）

103 阅读 0 评论 68 点赞

我是靠谱客的博主秀丽裙子，这篇文章主要介绍前端力扣刷题_数据结构篇（队列&栈），现在分享给大家，希望可以做个参考。

用两个栈实现队列
在这里插入图片描述
牛客写法：

复制代码

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
var CQueue = function() {
//用两个栈实现队列，所以要创建两个栈
    this.stack1=[];//stack1相当于茶壶
    this.stack2=[];//stack2相当于茶杯
};
/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value);
};
/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    //我们喝水是从杯子里喝，所以先检查杯子有没水，杯子有水，直接从杯子喝；杯子没水了，再看看茶壶里有没有，有就再全部倒进去。这时茶壶底下的水就倒到了杯子上面， 然后从杯子上面开始喝。
    if(this.stack2.length===0){//杯子没水
        if(this.stack1.length===0){//茶壶也没水
            return -1;
        }
        while(this.stack1.length!==0){//while茶壶有水
            this.stack2.push(this.stack1.pop());把茶壶的水倒进杯子里
        }
    }
    return this.stack2.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
var MyQueue = function() {
    this.stack1=[];//茶壶
    this.stack2=[];//茶杯
};

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

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(this.stack2.length===0){
        while(this.stack1.length!==0){
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(this.stack2.length===0){
        while(this.stack1.length!==0){
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2[this.stack2.length-1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack1.length===0&&this.stack2.length===0;
};

包含min函数的栈（最小栈）
思想：借助辅助栈minstack(详见牛客网官方题解，讲的很清楚）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var MinStack = function() {
    this.x_stack = [];
    this.min_stack = [Infinity];
};
MinStack.prototype.push = function(x) {
    this.x_stack.push(x);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};
MinStack.prototype.pop = function() {
    this.x_stack.pop();
    this.min_stack.pop();
};
MinStack.prototype.top = function() {
    return this.x_stack[this.x_stack.length - 1];
};
MinStack.prototype.getMin = function() {
    return this.min_stack[this.min_stack.length - 1];
};

栈的压入、弹出序列!!!
设置辅助栈

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function IsPopOrder(pushV, popV)
{
    let stack=[];
    let index=0;//初始化
    for(let node of pushV){
        stack.push(node);//压入栈
        while(stack.length!==0&&stack[stack.length-1]===popV[index]){//栈顶元素等于popV[index]
            stack.pop();//弹出栈
            index+=1;
        }
    }
    return stack.length===0;
}

翻转单词序列
队列法：
字符串转换为数组pop()再push进res数组，再转化为字符串即可。
有效的括号（判断括号匹配）
栈+哈希表
第一步：用一个对象或哈希表装映射关系右括号->左括号 ‘)’->‘(’, ‘]’->‘[’, ‘}’->‘{’;
第二步：遍历字符串遇到左括号就入栈，遇到右括号就要让对应的左括号出栈，
然后看出栈的字符是不是等于右括号对应的左括号如果不是就直接返回false；
最后：遍历完以后看栈是不是空了空了就证明是满足要求的返回true；

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
var isValid = function(s) {
    const obj={')':'(','}':'{',']':'['};
    const stack=[];
    for(let p of s){
        if(obj[p]){
            if(stack.pop()!==obj[p]) return false;
        }else{
            stack.push(p);
        }
    }
    return stack.length===0;
};

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
var removeDuplicates = function(s) {
    const stack=[];
    for(let p of s){
        if(stack[stack.length-1]===p){//不能用includes因为cbc没挨着的相同字符不能消
            stack.pop();
        }else{
            stack.push(p);
        }
    }
    return stack.join('');
};