假設(shè)理解 big o 表示法。 javascript 中有示例。資料參考 gayle laakmann mcdowell 的《cracking the coding interview》
今天，我們將探討兩種基本的數(shù)據(jù)結(jié)構(gòu)：堆棧和隊列。我們將深入研究它們的概念、用例，并使用經(jīng)典和基于原型的方法在 javascript 中實現(xiàn)它們。
堆棧：后進先出 (lifo)
想象一下一堆煎餅——你最后放在上面的一個是你第一個吃的。這正是堆棧數(shù)據(jù)結(jié)構(gòu)的工作原理。它遵循后進先出（lifo）原則.
關(guān)鍵操作
push(item): 將一個項目添加到堆棧頂部
pop()：從堆棧中刪除頂部項目
peek()：返回頂部項目而不刪除它
isempty()：檢查棧是否為空
使用案例
堆棧在涉及以下場景時特別有用：
遞歸算法
文本編輯器中的撤消機制
javascript 實現(xiàn)
經(jīng)典面向?qū)ο缶幊?br />
class stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isempty()) {
return "stack is empty";
}
return this.items.pop();
}
peek() {
if (this.isempty()) {
return "stack is empty";
}
return this.items[this.items.length - 1];
}
isempty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}
登錄后復(fù)制
基于原型
function stack() {
this.items = [];
}
stack.prototype.push = function(element) {
this.items.push(element);
};
stack.prototype.pop = function() {
if (this.isempty()) {
return "stack is empty";
}
return this.items.pop();
};
stack.prototype.peek = function() {
if (this.isempty()) {
return "stack is empty";
}
return this.items[this.items.length - 1];
};
stack.prototype.isempty = function() {
return this.items.length === 0;
};
stack.prototype.size = function() {
return this.items.length;
};
stack.prototype.clear = function() {
this.items = [];
};
登錄后復(fù)制
隊列：先進先出 (fifo)
現(xiàn)在，讓我們將注意力轉(zhuǎn)移到隊列上。與堆棧不同，隊列遵循先進先出（fifo）原則。想象一下音樂會場地的排隊——第一個到達的人就是第一個進入的人。
關(guān)鍵操作
enqueue(item): 將一個項目添加到隊列末尾
dequeue()：從隊列中刪除第一個項目
peek()：返回第一項而不刪除它
isempty()：檢查隊列是否為空
使用案例
隊列常用于：
廣度優(yōu)先搜索算法
任務(wù)調(diào)度
javascript 實現(xiàn)
經(jīng)典面向?qū)ο缶幊?br />
class node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class queue {
constructor() {
this.start = null;
this.end = null;
this.size = 0;
}
enqueue(element) {
const newnode = new node(element);
if (this.isempty()) {
this.start = newnode;
this.end = newnode;
} else {
this.end.next = newnode;
this.end = newnode;
}
this.size++;
}
dequeue() {
if (this.isempty()) {
return "queue is empty";
}
const removeddata = this.start.data;
this.start = this.start.next;
this.size--;
if (this.isempty()) {
this.end = null;
}
return removeddata;
}
peek() {
if (this.isempty()) {
return "queue is empty";
}
return this.start.data;
}
isempty() {
return this.size === 0;
}
getsize() {
return this.size;
}
clear() {
this.start = null;
this.end = null;
this.size = 0;
}
}
登錄后復(fù)制
基于原型
function Node(data) {
this.data = data;
this.next = null;
}
function Queue() {
this.start = null;
this.end = null;
this.size = 0;
}
Queue.prototype.enqueue = function(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.start = newNode;
this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.size++;
};
Queue.prototype.dequeue = function() {
if (this.isEmpty()) {
return "Queue is empty";
}
const removedData = this.start.data;
this.start = this.start.next;
this.size--;
if (this.isEmpty()) {
this.end = null;
}
return removedData;
};
Queue.prototype.peek = function() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.start.data;
};
Queue.prototype.isEmpty = function() {
return this.size === 0;
};
Queue.prototype.getSize = function() {
return this.size;
};
Queue.prototype.clear = function() {
this.start = null;
this.end = null;
this.size = 0;
};
登錄后復(fù)制
績效分析
堆棧和隊列都提供css”>
o(1)o(1)o(1)
有效實現(xiàn)時，其核心操作（堆棧的壓入/彈出、隊列的入隊/出隊）的時間復(fù)雜度。這使得它們在特定用例中具有高性能。
它們都為許多常見的編程問題提供了優(yōu)雅的解決方案，并構(gòu)成了更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)。通過在 javascript 中理解和實現(xiàn)這些結(jié)構(gòu)，您就可以很好地解決各種 leetcode/算法問題 ?.
