JavaScript数据结构与算法Item2--栈

曾经终败给现在 2022-07-16 01:23 227阅读 0赞

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的  
末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

## 1 栈的创建 ##

首先，我们需要一种数据结构来保存栈里的元素。可以选择数组：

var items = [];

接下来，要为我们的栈声明一些方法。

 push(element(s))：添加一个（或几个）新元素到栈顶。

 pop()：移除栈顶的元素，同时返回被移除的元素。

 peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。

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

 clear()：移除栈里的所有元素。

 size()：返回栈里的元素个数。这个方法和数组的length属性很类似。

## 2 从十进制到二进制 ##

学会了如何使用Stack类，现在就用它解决一些计算机科学中的问题。  
现实生活中，我们主要使用十进制。但在计算科学中，二进制非常重要，因为计算机里的所  
有内容都是用二进制数字表示的（0和1）。没有十进制和二进制相互转化的能力，与计算机交流  
就很困难。

![oh0ZoQX.png][]

// 栈的使用实例一：十进制转二进制(带余除法)
      function DataTansfer(num){
        var stack = new Stack(),
        yushu,
        result = '';
        while(num>0){
          yushu  = Math.floor(num % 2);
          stack.push(yushu);
          num = Math.floor(num/2);
        }
        while(!stack.isEmpty()){
          result += stack.pop().toString();
        }
        return result;
      }
    
    console.log(divideBy2(233)); //输出11101001
    console.log(divideBy2(10)); //输出1010
    console.log(divideBy2(1000)); //输出1111101000

## 3 任意进制间的转换 ##

我们很容易修改之前的算法，使之能把十进制转换成任何进制。除了让十进制数字和2整除  
转成二进制数，还可以传入其他任意进制的基数为参数，就像下面算法这样：

// 栈的使用实例二：实现任何进制数的转换
      function DataTansfer(num,base){ 
        var stack = new Stack(),
        yushu,
        digitals = '0123456789ABCDEF',
        result = '';
        while(num>0){
          yushu  = Math.floor(num % base);
          stack.push(yushu);
          num = Math.floor(num/base);
        }
        while(!stack.isEmpty()){
          result += digitals[stack.pop()];
        }
        return result;
      }
    
      console.log(DataTansfer(10010,2));
      console.log(DataTansfer(10010,8));
      console.log(DataTansfer(10010,10));
      console.log(DataTansfer(10010,16));

[oh0ZoQX.png]: http://i.imgur.com/oh0ZoQX.png