假設(shè)理解 big o 表示法。 javascript 中有示例。資料參考 gayle laakmann mcdowell 的《cracking the coding interview》
今天,我們將探討兩種基本的數(shù)據(jù)結(jié)構(gòu):堆棧和隊(duì)列。我們將深入研究它們的概念、用例,并使用經(jīng)典和基于原型的方法在 javascript 中實(shí)現(xiàn)它們。
堆棧:后進(jìn)先出 (lifo)
想象一下一堆煎餅——你最后放在上面的一個(gè)是你第一個(gè)吃的。這正是堆棧數(shù)據(jù)結(jié)構(gòu)的工作原理。它遵循后進(jìn)先出(lifo)原則.
關(guān)鍵操作
push(item): 將一個(gè)項(xiàng)目添加到堆棧頂部
pop():從堆棧中刪除頂部項(xiàng)目
peek():返回頂部項(xiàng)目而不刪除它
isempty():檢查棧是否為空
使用案例
堆棧在涉及以下場(chǎng)景時(shí)特別有用:
遞歸算法
文本編輯器中的撤消機(jī)制
javascript 實(shí)現(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ù)制
隊(duì)列:先進(jìn)先出 (fifo)
現(xiàn)在,讓我們將注意力轉(zhuǎn)移到隊(duì)列上。與堆棧不同,隊(duì)列遵循先進(jìn)先出(fifo)原則。想象一下音樂(lè)會(huì)場(chǎng)地的排隊(duì)——第一個(gè)到達(dá)的人就是第一個(gè)進(jìn)入的人。
關(guān)鍵操作
enqueue(item): 將一個(gè)項(xiàng)目添加到隊(duì)列末尾
dequeue():從隊(duì)列中刪除第一個(gè)項(xiàng)目
peek():返回第一項(xiàng)而不刪除它
isempty():檢查隊(duì)列是否為空
使用案例
隊(duì)列常用于:
廣度優(yōu)先搜索算法
任務(wù)調(diào)度
javascript 實(shí)現(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ù)制
績(jī)效分析
堆棧和隊(duì)列都提供css”>
o(1)o(1)o(1)
有效實(shí)現(xiàn)時(shí),其核心操作(堆棧的壓入/彈出、隊(duì)列的入隊(duì)/出隊(duì))的時(shí)間復(fù)雜度。這使得它們?cè)谔囟ㄓ美芯哂懈咝阅堋?/p>
它們都為許多常見(jiàn)的編程問(wèn)題提供了優(yōu)雅的解決方案,并構(gòu)成了更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)。通過(guò)在 javascript 中理解和實(shí)現(xiàn)這些結(jié)構(gòu),您就可以很好地解決各種 leetcode/算法問(wèn)題 ?.