閑聊
之前筆試的時(shí)候遇到了一個(gè)面試題捐祠,題目如下:有一個(gè)棧眶熬,往里面一次壓入1,2,3,4,5這幾個(gè)元素,得到的結(jié)果為[1,2,3,4,5]勃黍,現(xiàn)在只能用遞歸的方法宵统,將棧里面的元素顛倒,得到的結(jié)果為[5,4,3,2,1]覆获。要是沒有題目要求的話马澈,這個(gè)就比較簡單了,直接arr.reverse()就可以解決問題弄息,不過只能用遞歸就有意思了痊班,菜鳥一般的我就得好好研究一番了。
動(dòng)手分析
我們把棧[1, 2, 3, 4, 5]看成由兩部分組成:棧頂元素1和剩下的部分[2, 3, 4, 5]摹量。
如果我們能把[2, 3, 4, 5]顛倒過來涤伐,變成[5, 4, 3, 2],然后在把原來的棧頂元素1放到底部缨称,那么就整個(gè)棧就顛倒過來了凝果,變成[5, 4, 3, 2, 1]。
接下來我們需要考慮兩件事情:一是如何把[2, 3, 4, 5]顛倒過來變成[5, 4, 3, 2]具钥。我們只要把[2, 3, 4, 5]看成由兩部分組成:棧頂元素2和剩下的部分[3, 4, 5]豆村。
我們只要把[3, 4, 5]先顛倒過來變成[5, 4, 3],然后再把之前的棧頂元素2放到最底部骂删,也就變成了[5, 4, 3, 2]。
至于怎么把[3, 4, 5]顛倒過來……很多讀者可能都想到這就是遞歸四啰。也就是每一次試圖顛倒一個(gè)棧的時(shí)候宁玫,現(xiàn)在棧頂元素pop出來, 再顛倒剩下的元素組成的棧柑晒,最后把之前的棧頂元素放到剩下元素組成的棧的底部欧瘪。遞歸結(jié)束的條件是剩下的棧已經(jīng)空了
秀一波代碼
//這個(gè)函數(shù)的作用是把棧中的元素展開
function reverseStack(arr){
if(arr.length != 0 ){
var topItem = arr.pop()
reverseStack(arr)
pushStack(arr, topItem)
}
return arr
}
//這個(gè)函數(shù)的作用是把函數(shù)進(jìn)行顛倒
function pushStack(arr, item){
console.log(arr)
if(arr.length == 0){
arr.push(item)
}else{
var topItem1 = arr.pop()
pushStack(arr, item)
arr.push(topItem1)
return arr
}
}
var arr = new Array(1,2,3,4,5,6,7,8,9,10)
console.log( reverseStack(arr) )
討論
代碼還有需要的改進(jìn)的地方,歡迎交流學(xué)習(xí)匙赞!