假设理解 big o 表示法。 javascript 中有示例。资料参考 gayle laakmann mcdowell 的《cracking the coding interview》
今天，我们将探讨两种基本的数据结构：堆栈和队列。我们将深入研究它们的概念、用例，并使用经典和基于原型的方法在 javascript 中实现它们。
堆栈：后进先出 (lifo)
想象一下一堆煎饼——你最后放在上面的一个是你第一个吃的。这正是堆栈数据结构的工作原理。它遵循后进先出（lifo）原则.
关键操作
- push(item): 将一个项目添加到堆栈顶部
- pop()：从堆栈中删除顶部项目
- peek()：返回顶部项目而不删除它
- isempty()：检查栈是否为空
使用案例
堆栈在涉及以下场景时特别有用：
- 递归算法
- 文本编辑器中的撤消机制
javascript 实现
经典面向对象编程
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 = [];
}
}
基于原型
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 = [];
};
队列：先进先出 (fifo)
现在，让我们将注意力转移到队列上。与堆栈不同，队列遵循先进先出（fifo）原则。想象一下音乐会场地的排队——第一个到达的人就是第一个进入的人。
关键操作
- enqueue(item): 将一个项目添加到队列末尾
- dequeue()：从队列中删除第一个项目
- peek()：返回第一项而不删除它
- isempty()：检查队列是否为空
使用案例
队列常用于：
- 广度优先搜索算法
- 任务调度
javascript 实现
经典面向对象编程
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;
}
}
基于原型
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;
};
绩效分析
堆栈和队列都提供o(1) 有效实现时，其核心操作（堆栈的压入/弹出、队列的入队/出队）的时间复杂度。这使得它们在特定用例中具有高性能。
它们都为许多常见的编程问题提供了优雅的解决方案，并构成了更复杂的数据结构和算法的基础。通过在 javascript 中理解和实现这些结构，您就可以很好地解决各种 leetcode/算法问题 ?.
