思路
瀏覽器的前進(jìn)和后退拘领，我們?nèi)粘Ｉ钪袘?yīng)該接觸到很多。今天就來一起思考一下樱调，他是如何實(shí)現(xiàn)的约素。如果我是一個(gè)瀏覽器開發(fā)者，那我要如何來實(shí)現(xiàn)這個(gè)功能笆凌？
如果是我的話圣猎，我可能會(huì)用兩個(gè)數(shù)組來存儲(chǔ)歷史記錄，把訪問鏈接存到一個(gè)數(shù)組里面乞而，在點(diǎn)擊后退的時(shí)候送悔，把后退回去的記錄放到另外一個(gè)數(shù)組里來存儲(chǔ)。這樣一來爪模，就有2個(gè)數(shù)組了欠啤，一個(gè)數(shù)組存從哪里來arr1，一個(gè)數(shù)組存從哪里回來 arr2屋灌。
再把兩個(gè)數(shù)組里面的數(shù)據(jù)洁段，隨著“前進(jìn)，后退”的行為交換數(shù)據(jù)共郭，一旦出現(xiàn)這arr1祠丝，arr2 里面都不包含的item 疾呻，就直接把a(bǔ)rr2清空，沒法后退了纽疟。
其實(shí)這里涉及到一個(gè)“椆藓”的概念憾赁。
如何理解“椢坌啵”？
我很認(rèn)同老師舉的那個(gè)??龙考，棧的行為蟆肆，就有點(diǎn)像是往一個(gè)箱子里疊盤子，先放進(jìn)去的盤子晦款，在最下面炎功，后放進(jìn)去的盤子，在最上面缓溅。
這就是所謂的先進(jìn)先出蛇损，后進(jìn)后出 的原則。
應(yīng)該是比較好理解的坛怪。
棧 有一個(gè)特點(diǎn)：他是一種操作受限的線性表淤齐，只允許從其中一段插入和刪除數(shù)據(jù)。
如何實(shí)現(xiàn)一個(gè)“椡嗄洌”更啄？
在前端的眼里，實(shí)現(xiàn)棧居灯，第一個(gè)想到的就是用數(shù)組來實(shí)現(xiàn)祭务。他一共就有2個(gè)方法：push 和pop.
那我就來試著實(shí)現(xiàn)以下下呢。嘻嘻??
class ArraryStack {
// 申請(qǐng)一個(gè)長(zhǎng)度為count 的數(shù)據(jù)空間
constructor(count) {
this.count = count;
this.list = [];
this.length = 0;
}
push(item) {
if (this.count === this.length) return false; // 這個(gè)時(shí)候怪嫌，已經(jīng)沒有內(nèi)存存儲(chǔ)了义锥，入棧失敗
this.list.push(item);
this.length++;
}
pop() {
if (!this.length) return null; // 這個(gè)時(shí)候，棧里面已經(jīng)沒有記錄了岩灭，出棧失敗
const lastItem = this.list.pop();
--this.length;
return lastItem;
}
}
上面我聲明了一個(gè)長(zhǎng)度為n的一個(gè)數(shù)組拌倍，來存儲(chǔ)訪問過的數(shù)組。帶有pop 和push兩個(gè)方法川背，是一個(gè)比較簡(jiǎn)易的棧的實(shí)現(xiàn)贰拿。
來分析哈這個(gè)過程的時(shí)間和空間復(fù)雜度吧
在入棧和出棧的過程中，只用了幾個(gè)臨時(shí)變量熄云，所以空間復(fù)雜度為O（1）膨更。時(shí)間復(fù)雜度其實(shí)也還好，由于棧只操作第一個(gè)和最后一個(gè)數(shù)據(jù)缴允，所以不管你操作多少次荚守，他的時(shí)間復(fù)雜度都是O（1）珍德。算是比較簡(jiǎn)單的吧
