栈

栈是一种先进后出的特殊线性表结构，存储上分链式存储和顺序存储两种方式。

一、简介

栈是一种先进后出的特殊线性表结构，存储上分链式存储和顺序存储两种方式。

重点目标：

• 用数组实现一个顺序栈
• 用链表实现一个链式栈
• 编程模拟实现一个浏览器的前进、后退功能

二、手写

数组栈

function Stack() {
    let stack = []
    // 尾部添加
    this.push = function(value) {
        stack.push(value)
    }
    // 返回栈顶元素，并在进程中删除它
    this.pop = function() {
        return stack.pop()
    }
    // 返回栈顶元素，但不在堆栈中删除它
    this.peek = function() {
        console.log(stack[stack.length - 1])
        return stack[stack.length - 1]
    }
    // 置空
    this.clear = function() {
        stack = []
    }
    // 获取长度
    this.size = function() {
        console.log(stack.length)
        return stack.length
    }
    // 是否为空
    this.isEmpty = function() {
        return stack.length === 0
    }
    // 打印
    this.print = function() {
        console.log(stack)
    }
}

链表栈

class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class LinkStack {
    constructor() {
        // 头部相当于尾巴
        this.top = null
    }
    push(value) {
        const node = new Node(value)
        if (this.top === null) this.top = node
        else {
            node.next = this.top
            this.top = node // 此时node就是最上面的元素了
        }
    }
    pop() {
        if (this.top === null) return -1
        else {
            const value = this.top.value
            this.top = this.top.next
            return value
        }
    }
    clear() {
        this.top = null
    }
    print() {
        if (this.top !== null) {
            let temp = this.top
            while (temp !== null) {
                console.log(temp.value)
                temp = temp.next
            }
        }
    }
}

exports.CreatedStack = LinkStack

三、思考题

1. 浏览器的前进、后退功能

const stack = require('./linkedStack')

class Browser {
    constructor() {
        this.normalStack = new stack.LinkedStack()
        this.backStack = new stack.LinkedStack()
    }
    pushNormal(name) {
        this.normalStack.push(name)
        this.backStack.clear()
        this.displayStack()
    }
    back() {
        const name = this.normalStack.pop()
        if (name !== -1) {
            this.backStack.push(name)
            this.displayStack()
        }
    }
    front() {
        const value = this.backStack.pop()
        if (value !== -1) {
            this.normalStack.push(value)
            this.displayStack()
        }
    }
    displayStack() {
        console.log('---后退页面---')
        this.backStack.display()
        console.log('---浏览页面---')
        this.normalStack.display()
    }
}

2. 有效括号（#20）

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

    输入: "()"
输出: true
示例 2:

    输入: "()[]{}"
输出: true
示例 3:

    输入: "(]"
输出: false
示例 4:

    输入: "([)]"
输出: false
示例 5:

    输入: "{[]}"
输出: true

解法： 采用栈先进先出

var isValid = function(s) {
    let len = s.length
    if (len == 0) return true
    if (len % 2 != 0 || [')', ']', '}'].indexOf(s[0]) != -1) {
        return false
    }
    let map = {
        "(": ")",
        "[": "]",
        "{": "}"
    }
    var leftArr = []
    for (var ch of s) {
        if (ch in map) leftArr.push(ch); //为左括号时，顺序保存
        else { //为右括号时，与数组末位匹配
            if (ch != map[leftArr.pop()]) return false;
        }
    }
    return !leftArr.length //防止全部为左括号
};

56 ms 34. 5 MB

参考链接： https://www.cnblogs.com/pluslius/p/10327841.html https://github.com/wangzheng0822/algo

参考链接： https://www.cnblogs.com/xbblogs/p/9891288.html