數(shù)據(jù)結(jié)構(gòu)——棧

ixlei 發(fā)布于2019-08-22 11:19 / 3223人閱讀

摘要：棧是最基本的數(shù)據(jù)結(jié)構(gòu)之一，他的特點是后進先出棧的基本功能進棧添加元素到棧頂出棧刪除棧頂?shù)脑夭⒎祷刈x取棧頂?shù)臄?shù)據(jù)元素判斷棧是否為空，為空返回計算棧存儲數(shù)據(jù)的大小清空棧打印棧中的所有元素代碼實現(xiàn)基本的架構(gòu)如下所添加元素到棧頂進棧的元素出棧，刪

棧是最基本的數(shù)據(jù)結(jié)構(gòu)之一，他的特點是：后進先出

棧的基本功能

進棧：添加元素到棧頂

出棧：刪除棧頂?shù)脑夭⒎祷?/p>

讀取棧頂?shù)臄?shù)據(jù)元素

判斷棧是否為空，為空返回true

計算棧存儲數(shù)據(jù)的大小

清空棧

打印棧中的所有元素

代碼實現(xiàn)

基本的架構(gòu)如下所：

function Stack(){
    let item = [];

    /**
     * 添加元素到棧頂
     * @param m 進棧的元素
     */
    this.enStack = function(m){
    }

    /**
     * 出棧，刪除棧頂?shù)脑夭⒎祷?     */
    this.deStack = function(){
    }

    /**
     * 讀取棧頂?shù)脑?     */
    this.peek = function(){
    }

    /**
     * /判斷棧是否未為空
     */
    this.isEmpty = function(){
    }

    /**
     * 計算棧的容量
     */
    this.size = function(){
    }

    /**
     * 清空棧
     */
    this.clear = function(){
    }

    /**
     * 打印棧中的所有元素
     */
    this.print = function(){
    }

}

this.enStack——進棧操作

    this.enStack = function(m){
        item.push(m);
    }

this.deStack——出棧

    this.deStack = function(){
        return item.pop();
    }

this.peek 讀取棧頂?shù)脑?/p>

    this.peek = function(){
        return item[item.length - 1];
    }

this.isEmpty 判斷棧是否為空

    this.isEmpty = function(){
        return item.length === 0;
    }

this.size 計算棧的容量

    this.size = function(){
        return item.length;
    }

this.clear 清空棧

    this.clear = function(){
        item = [];
    }

this.print 打印棧中的元素

    this.print = function(){
        console.log(item.toString());
    }

棧的實際應(yīng)用

在進制轉(zhuǎn)化的結(jié)果是將余數(shù)倒著排列，這時就需要用到棧，先得到的余數(shù)放后面，后得到的余數(shù)放前面，具體實現(xiàn)過程

十進制轉(zhuǎn)化為二進制

十進制轉(zhuǎn)化為二進制的計算方式：除2取余法

代碼實現(xiàn)過程：

function transformTo(decNumber){
  let remStack = new Stack();
  let rem = "";
  let remString = "";

  while(decNumber){
      rem = decNumber % 2;
      remStack.enStack(rem);
      decNumber = parseInt(decNumber / 2);
  }

  while(!remStack.isEmpty()){
      remString += remStack.deStack().toString();
  }

  return remString;
}

const decRes = transformTo(10);
console.log(decRes);

最后的輸出結(jié)果是：1010

將十進制轉(zhuǎn)化為任意進制

function transformTo(decNumber, base){
    let remStack = new Stack();
    let rem;
    let remString = "";
    let digits = [0,1,2,3,4,5,6,7,8,9,"A","B","C","D","E","F"];

    while(decNumber > 0){
        rem = decNumber % base;
        remStack.enStack(rem);
        decNumber = parseInt(decNumber / base);
    }

    while(!remStack.isEmpty()){
        remString += digits[remStack.deStack()];
    }

    return remString;
}

const decRes = transformTo(1200, 16);
console.log(decRes);

輸出結(jié)果是：4B0