快捷導(dǎo)航

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Stack）

更新時間：2019年04月16日 09:59:49 作者：pingan8787

這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法（Stack），文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

最近公司內(nèi)部在開始做前端技術(shù)的技術(shù)分享，每周一個主題的每周一練，以基礎(chǔ)知識為主，感覺挺棒的，跟著團(tuán)隊的大佬們學(xué)習(xí)和復(fù)習(xí)一些知識，新人也可以多學(xué)習(xí)一些知識，也把團(tuán)隊內(nèi)部學(xué)習(xí)氛圍營造起來。

我接下來會開始把每周一練的題目和知識整理一下，便于思考和鞏固，就像今天這篇開始。

學(xué)習(xí)的道路，很漫長，要堅持，希望大家都能掌握自己喜歡的技術(shù)，和自己需要的技術(shù)。

本周練習(xí)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法 —— Stack

這些都是數(shù)據(jù)結(jié)構(gòu)與算法，一部分方法是團(tuán)隊其他成員實現(xiàn)的，一部分我自己做的，有什么其他實現(xiàn)方法或錯誤，歡迎各位大佬指點，感謝。

一、棧有什么特點，生活中有什么例子?

棧( stack )又稱堆棧，是一種后進(jìn)先出的有序集合，其中一端為棧頂，另一端為棧底，添加元素（稱為壓棧/入?；蜻M(jìn)棧）時，將新元素壓入棧頂，刪除元素（稱為出棧或退棧）時，將棧底元素刪除并返回被刪除元素。
特點：先進(jìn)后出，后進(jìn)先出。
例子：一疊書、一疊盤子。

二、實現(xiàn)一個棧，并實現(xiàn)下面方法

push(element)：添加一個新元素到棧頂。
pop()：移除棧頂?shù)脑?，同時返回被移除的元素。
peek()：返回棧頂?shù)脑兀粚Ｗ鋈魏涡薷?(這個方法不會移除棧頂?shù)脑?，僅僅返回它)。
isEmpty()：如果棧沒有任何元素就返回 true，否則返回 false。
clear()：移除棧里面的所有元素。
size()：返回棧里的元素個數(shù)。這個方法與數(shù)組的 length 屬性類似。

方法1：ES6實現(xiàn)

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
  }
}

上面實現(xiàn)的方式雖然簡單，但是內(nèi)部 items 屬性是公共的，為了滿足面向?qū)ο笞兂伤接行缘脑瓌t，我們應(yīng)該讓 items 作為私有屬性，因此我們可以使用 ES6 中 Symbol 或 WeakMap 來實現(xiàn)：

方法2：使用 ES6 的 Symbol 基本數(shù)據(jù)類型實現(xiàn)
知識點復(fù)習(xí)：ES6 中的 Symbol 介紹

const _items = Symbol()
class Stack {
  constructor (){
    this[_items] = []
  }
  push (element){
    this[_items].push(element)
  }
  // 剩下方法和第一種實現(xiàn)的差不多，這里省略
  // 只要把前面方法中的 this.items 更改為 this[_items]
}

方法3：使用 ES6 的 WeakMap 實現(xiàn)

知識點復(fù)習(xí)：ES6 中的 WeakMap 介紹

const items = new WeakMap()
class Stack {
  constructor (){
    items.set(this, [])
  }
  push (element){
    let item = items.get(this)
    item.push(element)
  }
  // 剩下方法和第一種實現(xiàn)的差不多，這里省略
  // 只要把前面方法中的獲取 this.items 的方式，更改為 items.get(this) 獲取
}

三、編寫一個函數(shù)，實現(xiàn)十進(jìn)制轉(zhuǎn)二進(jìn)制

題目意思很簡單，就是十進(jìn)制轉(zhuǎn)二進(jìn)制，但是在實際工作開發(fā)中，我們更愿意實現(xiàn)的是任意進(jìn)制轉(zhuǎn)任意進(jìn)制，不過呢，我們還是以解決問題為首要目標(biāo)呀。

當(dāng)然，業(yè)務(wù)需求可以直接使用 toString(2) 方法，但是為了練習(xí)，咱還是不這么用咯。

方法1：使用前面定義的 Stack 類

這里使用前面題目中定義的 Stack 類。

/**
 * 十進(jìn)制轉(zhuǎn)換為二進(jìn)制
 * @param {Number} bit 
 */
function bitset (bit){
  if(bit == 0) return '0'
  if(!/^[0-9]+.?[0-9]*$/.test(bit)){
    return new Error('請輸入正確的數(shù)值！')
  }

  let stack = new Stack(), result = ''
  while (bit > 0){
    stack.push(bit % 2)
    bit = Math.floor(bit / 2)
  }
  while (!stack.isEmpty()){
    result += stack.pop().toString()
  }
  return result

}

方法2：簡單實現(xiàn)

下面這個方法，其實不太好，因為沒有怎么用到這次要練習(xí)的棧方法，哈哈。

/**
 * 十進(jìn)制轉(zhuǎn)換為二進(jìn)制
 * @param {Number} bit 
 */
function bitset (bit){
  if(bit == 0) return '0'
  if(!/^[0-9]+.?[0-9]*$/.test(bit)){
    return new Error('請輸入正確的數(shù)值！')
  }

  let arr = []
  while(bit > 0){
    arr.push(bit % 2)
    bit = Math.floor(bit / 2)
  }
  return arr.reverse().join('')
}

另外可以參考：wikiHow - 從十進(jìn)制轉(zhuǎn)換為二進(jìn)制。

四、編寫一個函數(shù)，實現(xiàn)檢驗圓括號順序的有效性

主要目的就是：該函數(shù)接收一個圓括號字符串，判斷里面的括號順序是否有效，如果有效則返回 true 反之 false。
如：

( -> false
() -> true
(() -> false
()) -> false
()) -> false
(((()()))()) -> true

這個題目實現(xiàn)的主要方法是：遍歷字符串，先排除錯誤情況，然后將 ( 入棧保存，將 ) 入棧匹配前一個元素是否是 ( ，如果是，則 pop() 前一個元素 (，如果不是，則 push() 這個 ) 入棧，最終查看棧是否為空，若是則檢驗成功，否則失敗。

方法1：使用前面定義的 Stack 類

這里使用前面題目中定義的 Stack 類。

/**
 * 檢驗圓括號順序的有效性
 * @param {String} str 
 */
function validParentheses (str){
  if(!str || str.length === 0 || str[0] === ')') return false

  let stack = new Stack()
  str.split('').forEach(char => {
    let status = stack.peek() === '(' && char === ')'
    status ? stack.pop() : stack.push(char)
  })
  return stack.isEmpty()
}

方法2：出入棧操作

/**
 * 檢驗圓括號順序的有效性
 * @param {String} str 
 */
function validParentheses (str){
  if(!str || str.length === 0 || str[0] === ')') return false

  let arr = []
  for(let i = 0; i < str.length ; i++){
    str[i] === '(' ? arr.push(str[i]) : arr.pop()
  }
  return arr.length === 0
}

五、改造題二，添加一個 min 函數(shù)來獲得棧中最小元素

步驟	數(shù)據(jù)棧	輔助棧	最小值
1.push 3	3	0	3
2.push 4	3, 4	0, 0	3
3.push 2	3, 4, 2	0, 0, 2	2
4.push 1	3, 4, 2 ,1	0, 0, 2, 3	1
5.pop	3, 4, 2	0, 0, 2	2
6.pop	3, 4	0, 0	3
7.push	3, 4 ,0	0, 0, 2	0

使用示例如下：

let stack = new Stack();
stack.push(3);
console.log('After push 3, Min item is', stack.min());
stack.push(4);
console.log('After push 4, Min item is', stack.min());
stack.push(2);
console.log('After push 2, Min item is', stack.min());
stack.push(1);
console.log('After push 1, Min item is', stack.min());
stack.pop();
console.log('After pop, Min item is', stack.min());
stack.pop();
console.log('After pop, Min item is', stack.min());
stack.push(0);
console.log('After push 0, Min item is', stack.min());

提示：利用輔助棧（Web 端可利用數(shù)組），每次對棧 push/pop 元素時，也同時更新輔助棧（存儲最小元素的位置）

方法1：小操作

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

 push(element) {
  this.items.push(element);
  let minLen = this.minIndexStack.length;
  let minItemIndex = this.minIndexStack[minLen - 1];
  if(minLen === 0 || this.items[minItemIndex] > item) {
   this.minIndexStack.push(this.items.length - 1);
  } else {
   this.minIndexStack.push(minItemIndex);
  }
 }

 pop() {
  this.minIndexStack.pop();
  return this.items.pop();
 }
 
 min() {
  let len = this.minIndexStack.length;
  return (len > 0 && this.items[this.minIndexStack[len - 1]]) || 0;
 }

 peek() {
  return this.items[this.items.length - 1];
 }
 
 // 省略其它方法
}

方法2：與方法1中push實現(xiàn)的差異

class Stack {
  constructor (){
    this.items = [] // 數(shù)據(jù)棧
    this.arr = []  // 輔助棧
  }
  push( element ){
    this.items.push(element)
    let min = Math.min(...this.items)
    this.arr.push( min === element ? this.size() - 1 : 0)
  }
  pop(){
    this.arr.pop()
    return this.items.pop()
  }
  peek(){
    return this.items[this.items.length - 1]
  }
  isEmpty(){
    return this.items.length === 1
  }
  clear(){
    this.items = []
  }
  size(){
    return this.items.length
  }
  min (){
    let last = this.arr[this.arr.length - 1]
    return this.items[last]
  }
}

以上所述是小編給大家介紹的數(shù)據(jù)結(jié)構(gòu)與算法（Stack）詳解整合，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！

您可能感興趣的文章: