小撒是一只好學(xué)的小鴨子，這天妖碉，小撒在學(xué)習(xí)算法
今天我們就來(lái)介紹幾個(gè)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)吧涌庭。
棧（stash）
棧是一種先進(jìn)后出（FILO，first-in-last-out）的數(shù)據(jù)結(jié)構(gòu)欧宜，提供了壓棧（push）坐榆、出棧（pop）的操作。在js中可以使用數(shù)組以及pop和push方法來(lái)實(shí)現(xiàn)冗茸。
相應(yīng)的席镀，隊(duì)列（Queue）則是一種先進(jìn)先出（FIFO，first-in-first-out）的數(shù)據(jù)結(jié)構(gòu)夏漱，提供了入隊(duì)（enqueue）與出隊(duì)（dequeue）的操作豪诲。在js中可以使用數(shù)組以及push和shift方法來(lái)實(shí)現(xiàn)。
最小棧
今天我們進(jìn)來(lái)實(shí)現(xiàn)一段小程序：我們將觀察一個(gè)棧的出棧以及入棧行為挂绰，并且在任一時(shí)刻獲得這個(gè)棧中最小元素的值屎篱。
一個(gè)最直觀的想法是，在需要獲取最小元素時(shí)，掃描棧并記錄最小的元素交播，這樣的話(huà)時(shí)間復(fù)雜度是O(n)专肪。
而我們則要來(lái)實(shí)現(xiàn)O(1)的算法。也許有些同學(xué)會(huì)提出這樣的想法：使用一個(gè)變量記錄當(dāng)前棧內(nèi)最小的元素堪侯。這個(gè)做法的問(wèn)題在于嚎尤，如果當(dāng)前最小的元素出棧了，我們?cè)趺传@取到接下來(lái)的最小的元素呢伍宦？
當(dāng)然我們實(shí)現(xiàn)最小棧的算法也是基于這個(gè)思想的芽死，只是我們將不止記錄一個(gè)最小元素，而是一系列最小元素次洼。為此我們將建立一個(gè)額外的棧（最小棧）：
- 當(dāng)元素入棧時(shí)关贵，如果新元素不大于最小棧的棧頂元素，則同樣將該元素入棧最小棧
- 當(dāng)元素出棧時(shí)卖毁，如果出棧元素的值與最小棧棧頂元素相同揖曾，則最小棧棧頂元素出棧
- 在任意時(shí)刻，最小棧棧頂?shù)脑丶词菞Ｖ凶钚〉脑亍?/li>
class MinStack {
constructor() {
this.stack = [];
this.minStack = [Math.min()];
}
push(item) {
this.stack.push(item);
if (item <= this.min()) this.minStack.push(item);
}
pop() {
const item = this.stack.pop();
if (item === this.min()) this.minStack.pop();
return item;
}
min() {
return this.minStack[this.minStack.length - 1];
}
}
const data = [11, 7, 9, 5, 5, 2, 3, 1];
const minStack = new MinStack();
while (data.length) {
const item = data.shift();
minStack.push(item);
console.log('push', item, minStack.min(), minStack.stack.join(','));
}
while (minStack.stack.length) {
const item = minStack.pop();
console.log('pop', item, minStack.min(), minStack.stack.join(','));
}
在這里小撒在minStack中提前放入了Math.min()這一最大值亥啦，這樣的手段稱(chēng)為『哨兵』炭剪，是一種簡(jiǎn)化邊際處理的技巧。
鏈表（linked list）
鏈表是一種類(lèi)似數(shù)組的數(shù)據(jù)結(jié)構(gòu)翔脱，鏈表分為單向鏈表和雙向鏈表奴拦，其中的每一項(xiàng)不僅包含值還包含指向相鄰元素的指針。鏈表的優(yōu)勢(shì)在于插入或刪除元素時(shí)届吁，只要修改相鄰元素的指針指向错妖、而不必移動(dòng)元素，因此具有更好的插入與刪除性能疚沐。不過(guò)相應(yīng)的如獲得鏈表第n項(xiàng)的值這樣的操作將沒(méi)有那么直觀了暂氯。
這里我們將進(jìn)行的小練習(xí)是，反轉(zhuǎn)一個(gè)單向鏈表亮蛔。
我們通過(guò)圖示來(lái)了解一下這個(gè)過(guò)程：
即我們只要按次序?qū)⒁粋€(gè)個(gè)元素放到新鏈表的頭部就可以了痴施。
const arr2list = function (arr) {
const head = {
val: arr[0],
};
let current = head;
for (let i = 1; i < arr.length; i++) {
const next = {
val: arr[i],
};
current.next = next;
current = next;
}
return head;
};
const list = arr2list([1, 2, 3, 4, 5, 6]);
const logList = function (list) {
const arr = [];
let head = list;
while (head.next) {
arr.push(head.val);
head = head.next;
}
arr.push(head.val);
console.log(arr);
}
const reverse = function (list) {
let head = list;
let next = list.next;
let nextNext = list.next.next;
head.next = null;
let newHead = next;
newHead.next = head;
while (true) {
next = nextNext;
if (!next) break;
nextNext = next.next;
const oldHead = newHead;
newHead = next;
newHead.next = oldHead;
}
return newHead;
}
logList(list);
logList(reverse(list));
