栈(Stack)

数据结构和算法，和语言是无关的

• 栈的特点

  1. 一种受限的线性表，后进先出(LIFO:last in first out)
  2. 其限制是仅允许在栈顶进行插入和删除运算

• 函数调用栈

  

• 栈结构面试
  有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？()

  A. 5 4 3 6 1 2

  B. 4 5 3 2 1 6

  C. 3 4 6 5 2 1

  D. 2 3 4 1 5 6

  

• 栈结构实现(基于数组)

  • 栈的常见操作

    • push(element) : 添加一个新元素到栈顶

    • pop() : 移除栈顶元素，同时返回被移除元素

    • peek() : 返回栈顶的元素，不对栈做任何修改(不会移除栈顶元素，仅仅返回它)

    • isEmpty() : 如果栈里没有任何元素就返回true，否则返回false

    • size() : 返回栈里元素个数

    • toString() : 将栈结构的内容以字符形式返回

  • 栈的实现

    // 声明栈
    function Stack() {
        // 栈中属性
        this.items = [];
        // push 添加元素到栈顶
        this.push = function(element) {
            this.items.push(element);
        }
        // pop 移除栈顶元素, 同时返回移除的元素
        this.pop = function() {
            return this.items.pop();
        }
        // peek 返回栈顶元素
        this.peek = function() {
            if (this.isEmpty()) return null;
            return this.items[this.items.length - 1];
        }
        // isEmpty 栈里没有任何元素就返回true，否则返回false
        this.isEmpty = function() {
            return this.items.length === 0;
        }
        // size 返回栈里元素个数
        this.size = function() {
            return this.items.length;
        }
        // 将栈结构的内容以字符形式返回
        this.toString = function() {
            return this.items.toString();
        }
    }

  • 基于实现的栈通过小程序将10进制转为2进制

    // 十进制转二进制
    function DecToBin(decNum) {
        var stack = new Stack();
        // 依次整除2, 余数即为2进制
        while(decNum > 0) {
            stack.push(decNum % 2);
            decNum = Math.floor(decNum / 2);
        }
        // 将栈中的2进制拼接(例如 10进制4 转换后 栈中为[0,0,1])
        var result = "";
        while(!stack.isEmpty()) {
            result += stack.pop();
            //debugger;
        }
        console.log(result);
    }