在平時的工作中,操作數據用的最多的可能就是數組了,有了數組,我們可以做很多事情,比如在數組的任意位置上刪除或添加元素。但是有些時候,單純的數組并不能滿足我們的需求,這時候就需要新的數據結構。有這么兩種類似于數組的數據結構在添加和刪除元素時更為可控,它們就是棧和隊列。

棧數據結構

棧是一種遵循后進先出(LIFO)原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端,稱作棧頂,另一端就叫棧底。在棧里,新元素都靠近棧頂,舊元素都接近棧底。我們可以把棧看成是一個乒乓球桶,來加深對棧的理解。

乒乓球盒子與棧類比

這里引用大佬的一張圖片來理解棧的數據結構

創建一個基于數組的棧

我們需要對棧實現以下幾個功能:

push(element):添加一個或幾個新元素到棧頂
pop:移除棧頂的元素,并返回被移除的元素
peek:返回棧頂的元素,不對棧進行任何修改
isEmpty:如果棧里沒有任何元素,就返回true,否則返回false
clear:清空棧里的所有元素
size:返回棧里的元素個數

由于數組可以在任意地方添加元素,這并不符合LIFO原則,所以我們需要對插入和刪除的功能做一些限制。添加、刪除以及棧的長度的功能,我們可以利用數組現有的方法(push、pop、和length)實現。

peek方法,我們只需要返回數組的最后一項(棧頂),利用數組下標length – 1(數組下標是從0開始的)。isEmpty方法,我們可以根據數組長度是否為0來實現。clear方法只需要讓棧賦值一個空數組就能實現。下面是利用數組實現的棧:

class Stack {
 constructor() {
  this.items = []
 }
 push(element) {
  this.items.push(element)
 }
 pop() {
  return this.items.pop()
 }
 peek() {
  return this.items[this.items.length - 1]
 }
 isEmpty() {
  return this.items.length === 0
 }
 clear() {
  this.items = []
 }
 size() {
  return this.items.length
 }
}

接著我們來驗證一下剛剛實現的幾個功能:

// 聲明一個類的實例
const stack = new Stack()
// 驗證棧是否為空
console.log(stack.isEmpty()) // true

//添加一些元素
stack.push(5)
stack.push(8)

//調用peek方法
console.log(stack.peek()) // 8

//再添加一個元素
stack.push(11)
console.log(stack.size()) // 3
console.log(stack.isEmpty()) // false
stack.push(15)

下圖描繪了目前為止我們對棧的操作,以及棧的當前狀態。

我們再接著進行一些操作:

//再進行一些操作
stack.pop()
stack.pop()
console.log(stack.size()) // 2

調用兩次pop后的過程如下:

基于數組實現棧的思考

創建一個 Stack 類最簡單的方式是使用一個數組來存儲其元素。在處理大量數據的時候(這在現實生活中的項目里很常見),我們同樣需要評估如何操作數據是最高效的。在使用數組時,大部分方法的時間復雜度是 O(n)?!綩(n)的意思是,我們需要迭代整個數組直到找到要找的那個元素,在最壞的情況下需要迭代數組的所有位置,其中的 n 代表數組的長度?!?/p>

另外,數組是元素的一個有序集合,為了保證元素排列有序,它會占用更多的內存空間。那有沒有更好的方式來實現棧呢?既能直接獲取元素,又能占用較少的內存空間,并且仍然能按照我們的需要排列元素。想到這里,是不是想到了JavaScript中另外一種數據類型——對象。

創建一個基于JavaScript對象的棧

說干就干,既然想到了用對象實現棧,那么就試試看看吧。由于對象是以key-value的形式存儲數據,那么我們就用一個變量來實現“下標”,并用它來記錄數據的數量。

既然有了記錄數據的變量,那么isEmpty和size方法就簡單的多了,只需要判斷count變量,并進行返回操作就可以了。添加元素時,我們將count變量當做items的key,插入的元素是它的value,在插入元素之后,我們遞增count變量,用來記錄下一次插入值的位置。移除元素時,我們先判斷當前棧是否為空,然后將count值遞減,接著用變量result存儲最后一個元素,并使用object自帶的delete方法刪除最后一個元素,最后返回result。

peek方法和clear方法就簡單多了,這里不再贅述。

class Stack {
 constructor() {
  this.count = 0
  this.items = {}
 }
 push(element) {
  this.items[this.count] = element
  this.count++
 }
 pop() {
  if(this.isEmpty()){
   return undefined
  }
  this.count--
  const result = this.items[this.count]
  delete this.items[this.count]
  return result
 }
 peek() {
  if(this.isEmpty()){
   return undefined
  }
  return this.items[this.count - 1]
 }
 isEmpty() {
  return this.count === 0
 }
 clear() {
  this.count = 0
  this.items = {}
 }
 size() {
  return this.count
 }
}

在以數組為基數實現的棧中,我們不用關心toString()方法的實現,可以直接使用。但是對于以對象為基礎實現的棧中,我們需要實現一個toString方法,來打印出棧的內容。
下面是toString的實現過程:先判斷棧是否為空,為空返回空字符串。否則我們將棧底的元素當做初始值,然后迭代整個棧的鍵,并將下一個元素進行拼接。這樣做的好處是,當棧只有一個元素時,不會迭代整個棧。

toString() {
 if(this.isEmpty()){
  return ''
 }
 let objString = `${this.items[0]}`
 for(let i = 0; i < this.count; i++){
  objString = `${objString}, ${this.items[i]}`
 }
 return objString
}

用棧解決問題

棧的實際應用非常廣泛。在回溯問題中,它可以存儲訪問過的任務或路徑、撤銷的操作。既然我們已經學習棧數據結構,那么就用它來實現一個任意進制轉換的算法吧。現實生活中,我們主要內容都是使用十進制,把十進制轉換為其他進制,實際上就是一個取余數的過程。把十進制的數10轉換為二進制為例,過程大概是下面這樣:

我們以棧為基礎,來實現十進制轉換為二進制:

function baseConverter(decNumber){
 const remStack = new Stack()
 let number = decNumber
 let rem
 let baseString = ''

 while(number > 0){
  rem = Math.floor(number % 2)
    remStack.push(rem)
    number = Math.floor(number % 2)
 }

 while(!remStack.isEmpty()){
  baseString += remStack.pop().toString()
 }
 return baseString
}

在這段代碼里,當除法的結果不為 0 時,我們會獲得一個余數,并放到棧里。然后讓結果繼續除以 2。因為在JavaScript的數值類型并不會區分整數和浮點數。所以,要使用 Math.floor 函數僅返回除法運算結果的整數部分。最后,用 pop 方法把棧中的元素都移除,把出棧的元素連接成字符串。

用剛才寫的算法做一些測試,使用以下代碼把結果輸出到控制臺里。

console.log(baseConverter(233)); // 11101001 
console.log(baseConverter(10)); // 1010 
console.log(baseConverter(1000)); // 1111101000

我們繼續改造上面的算法,讓它能夠把十進制轉換為基數為2~36的任意進制。

function baseConverter(decNumber, base){ 
 const remStack = new Stack(); 
 const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
 let number = decNumber; 
 let rem; 
 let baseString = ''; 

 if (!(base >= 2 && base <= 36)){ 
  return ''; 
 } 

 while (number > 0) { 
  rem = Math.floor(number % base); 
  remStack.push(rem); 
  number = Math.floor(number / base); 
 }

 while (!remStack.isEmpty()){ 
  baseString += digits[remStack.pop()];
 } 
 return baseString; 
}

我們只需要改變一個地方。在將十進制轉成二進制時,余數是 0 或 1;在將十進制轉成八進制時,余數是 0~7;但是將十進制轉成十六進制時,余數是 0~9 加上 A、B、C、D、E 和 F(對應 10、11、12、13、14 和 15)。因此,我們需要對棧中的數字做個轉化才可以。因此,從十一進制開始,字母表中的每個字母將表示相應的基數。字母 A 代表基數 11,B 代表基數 12,以此類推。

測試一下我們改造后的算法:

console.log(baseConverter(100345, 2)); // 11000011111111001 
console.log(baseConverter(100345, 8)); // 303771 
console.log(baseConverter(100345, 16)); // 187F9 
console.log(baseConverter(100345, 35)); // 2BW0

總結

通過學習了棧這一數據結構的相關知識。我們使用數組和一個 JavaScript 對象自己實現了棧,并實現了 push 和 pop 往棧里添加和移除元素。通過兩種實現棧的方法,了解了不同實現的優缺點。并且利用棧數據結構實現了進制轉換的算法。

參考書籍《學習JavaScript數據結構與算法》