数据结构(栈 Stack)

栈(Stack):是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。
栈的特点是:遵循LIFO (last in, first out)(后进先出)的原则。先进后出从栈顶放入元素的操作叫入栈(压栈),取出元素叫出栈(弹栈)。
image.png

入栈操作:


image.png

出栈操作:


image.png

栈常见的操作:

push(element):添加一个新元素到栈顶位置;
pop():移除栈顶的元素,同时返回被移除的元素;
peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它);
isEmpty():如果栈里没有任何元素就返回true,否则返回false;
size():返回栈里的元素个数。这个方法和数组的length属性类似;
clear() : 清空栈;
toString():将栈结构的内容以字符串的形式返回。

  function Stack() {
    // 栈元素
    this.items = [];
    //1.入栈
    Stack.prototype.push = (element) => {
      this.items.push(element);
    }
    // 2.pop删除栈顶元素,并返回该元素
    Stack.prototype.pop = () => {
      return this.items.pop(); //pop方法删除最后一个元素,并返回删除的该值
    }
    // 3.取出栈顶元素
    Stack.prototype.peek = () => {
      return this.items[this.items.length - 1]
    }
    // 4.判断栈是否为空
    Stack.prototype.isEmpty = () => {
      return this.items.length === 0
    }
    // 5.获取栈的个数
    Stack.prototype.size = () => {
      return this.items.length;
    }
    // 6.输出栈数据,希望这种形式: 20 10 100
    Stack.prototype.toString = () => {
      let Str = ''
      for (let i of this.items) {
        Str += i + ' ';
      }
      return Str
    }
  }
  let s = new Stack()
  //测试案例:
  s.push(20);
  s.push(10);
  s.push(100);
  s.push(77);
  console.log(s.toString()); //打印:20 10 100 77
  //删除两个元素
  console.log(s.pop()); //77
  console.log(s.pop()); //100
  //取出栈顶元素
  console.log(s.peek()); //10
  //是否为空
  console.log(s.isEmpty()); //false
  //剩余大小
  console.log(s.size()); //2
  //最终打印
  console.log(s.toString()); //20 10

使用es6写法封装栈

// 栈结构的封装
class Stack{

  constructor() {
    this.items = [];
  }

  // push(item) 压栈操作,往栈里面添加元素
  push(item) {
    this.items.push(item);
  }

  // pop() 出栈操作,从栈中取出元素,并返回取出的那个元素
  pop() {
    return this.items.pop();
  }

  // peek() 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }

  // isEmpty() 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // size() 获取栈中元素个数
  size() {
    return this.items.length;
  }

  // toString() 返回以字符串形式的栈内元素数据
  toString() {
    let result = '';
    for (let item of this.items) {
      result += item + ' ';
    }
    return result;
  }
}

栈的实际应用:

十进制转二进制

  let decTobin = decNumber => {
    //1.定义一个栈对象,保存余数
    var stack = new Stack()

    // 2.循环入栈操作
    while (decNumber > 0) {//当除法结果不为零时,入栈添加
      // 2.1.获取余数并放入栈中
      stack.push(decNumber % 2)
      // 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
      decNumber = Math.floor(decNumber / 2)
    }

    // 3.循环出栈操作
    let binaryString = '';
    while (stack.items.length != 0) {
      binaryString += stack.pop();
    }
    return binaryString;
  }

  //测试代码
  console.log(decTobin(10)); //1010
  console.log(decTobin(100)); //1100100
  console.log(decTobin(1000)) //1111101000

十进制转任意进制

let decTobin = (decNumber, base) => {
 if (base < 2 || base > 36) {
   return "表示不了这个进制"
 }
 //1.定义一个栈对象,保存余数
 var stack = new Stack()
 var digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 // 2.循环操作
 while (decNumber > 0) {
   // 2.1.获取余数并放入栈中
   stack.push(decNumber % base)
   // 2.2.获取整除后的结果作为下一次运算的数字(floor:向下取整)
   decNumber = Math.floor(decNumber / base)
 }

 // 3.从栈中取出值
 let binaryString = '';
 while (stack.items.length != 0) {
   binaryString += digits[stack.pop()]; //根据下标返回字符值,如:"01"[1]=11
 }
 return binaryString;
}

//测试代码
console.log(decTobin(100345, 2)); //11000011111111001
console.log(decTobin(100345, 8)); //303771
console.log(decTobin(100345, 16)); //187F9
console.log(decTobin(100345, 35)); //2BW0
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容