JavaScript實現棧結構詳細過程

一、認識棧結構

我們知道數組是一種常見的數據結構,並且可以在數組的任意位置插入和刪除數據,但是有時候,我們為瞭實現某些功能,必須對這種任意性加以限制,而棧和隊列就是比較常見的受限的數據結構,我們先來看看棧。
棧(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!

推薦閱讀: