JavaScript實現棧結構詳細過程

Posted on by

一、認識棧結構

我們知道數組是一種常見的數據結構，並且可以在數組的任意位置插入和刪除數據，但是有時候，我們為瞭實現某些功能，必須對這種任意性加以限制，而棧和隊列就是比較常見的受限的數據結構，我們先來看看棧。
棧（stack),它是一種受限的線性表，後進先出（LIFO）

  • 其限制性是允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對的，把另一端，稱為棧底。
  • LIFO（last in first out）表示就是後進入的元素，第一個彈出棧空間。
  • 向一個棧中插入一個新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；
  • 從一個棧刪除元素又稱作出棧或者退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

其結構圖如下所示：

在這裡插入圖片描述

生活中類似於棧的

例如：當我們敲代碼時，如果發生錯誤需要刪除，那麼最先敲上去的是最後被刪除的。

接下來我們就一起來實現一下棧結構的封裝，將采用的方式是基於數組實現的。

二、棧結構封裝

首先創建一個類封裝棧結構，如下：

function Stack(){
            
        }

在其內部添加屬性和方法，將數組通過屬性的方法添加給該類。然後采用原型的方法添加常用的操作。

棧常用的操作有：

  • push(element)：添加一個新元素到棧頂位置。
  • pop() ：移除棧頂的元素
  • peek( ) ：返回棧頂的元素，不對棧做任何修改
  • isEmpty() ：判斷棧是否空，如果棧裡沒有任何元素，則返回true，否則返回false
  • size() ：返回棧裡的元素個數
  • toString() ：將棧結構的內容以字符形式返回

接下來，我們就來將他們一一實現：

 function Stack(){
     this.items = [];
     // 添加一個新元素到棧頂位置。push()
     Stack.prototype.push = function(element){
        this.items.push(element);
     }
      // 移除棧頂的元素pop()
     Stack.prototype.pop = function(){
         return this.items.pop();
     }
     //  返回棧頂的元素，不對棧做任何修改peek()
     Stack.prototype.peek = function(){
         return this.items[this.items.length-1];
     }
     // 判斷棧是否空isEmpty()
     Stack.prototype.isEmpty = function(){
         if(this.items.length == 0){
             return true;
         }else {
             return false;
         }
     }
     // 返回棧裡的元素個數size()
     Stack.prototype.size = function(){
         return this.items.length;
     }
     // 將棧結構的內容以字符形式返回toString()
     Stack.prototype.toString = function(){
         var str = '';
         for(var i =0;i<this.items.length;i++){
             str += this.items[i] + ' ';
         }
         return str;
     }
 }

註意：這裡為什麼要通過原型的方式添加呢？是因為通過該方法添加的方法是添加在類上的，而如果直接通過this來添加，是添加到具體的實例對象上的，會造成浪費內存的情況。

最後進行驗證。代碼如下：

var stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
console.log(stack);
console.log('移除的棧頂元素是：'+stack.pop());
console.log('棧頂元素為：'+stack.peek());
console.log('棧是否為空：'+stack.isEmpty());
console.log('棧裡的元素個數是：'+stack.size());
console.log('棧結構的內容是：');
console.log(stack.toString());

輸出結果為：

在這裡插入圖片描述

構建成功。
接下來來看一個實例！

三、十進制轉化為二進制

如何實現十進制轉化為二進制呢？

要把十進制轉化成二進制，我們可以將該十進制數字和2整除，將得到的餘數壓入棧中，直到結果是0為止，最後在將得到的棧中元素依次出棧，得到最終結果，

如下圖所示：

在這裡插入圖片描述

具體代碼為：

 function Stack(){
     this.items = [];
     //入棧
     Stack.prototype.push = function(element){
         this.items.push(element);
     }
     //出棧
     Stack.prototype.pop = function(){
         return this.items.pop();
     }
     //判斷棧是否為空
     Stack.prototype.isEmpty = function(){
         if(this.items.length == 0){
             return true;
         }else{
             return false;
         }
     }
 }
 function decToBin(decNumber){
      var stack = new Stack;
      while(decNumber>0){
          //獲取餘數，放入棧中
          stack.push(decNumber%2);
          //獲取新的除數
          decNumber = Math.floor(decNumber/2);
      }
      //獲取棧頂元素
      var str = '';
      while(!stack.isEmpty()){
          str += stack.pop();
      }
      return str;
  }
 console.log('100轉化成二進制是：'+decToBin(100));
 console.log('50轉化成二進制是：'+decToBin(50));
 console.log('20轉化成二進制是：'+decToBin(20));
 console.log('34轉化成二進制是：'+decToBin(34));

輸出結果為：

在這裡插入圖片描述

到此這篇關於JavaScript實現棧結構詳細過程的文章就介紹到這瞭,更多相關JavaScript實現棧結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：