Javascript数据结构与算法——栈与队列
1. 用栈实现队列
题目描述：使用两个栈实现一个队列，支持基本的队列操作：enqueue（入队）和dequeue（出队）。
代码解释：使用两个栈，一个用于入队操作，另一个用于出队操作。当需要出队时，如果出队栈为空，则将入队栈中的所有元素依次弹出并压入出队栈，这样栈顶元素即为队列的第一个元素。
代码示例：
javascript复制代码
class MyQueue { | |
constructor() { | |
this.stackIn = []; | |
this.stackOut = []; | |
} | |
push(x) { | |
this.stackIn.push(x); | |
} | |
pop() { | |
if (this.stackOut.length === 0) { | |
while (this.stackIn.length > 0) { | |
this.stackOut.push(this.stackIn.pop()); | |
} | |
} | |
return this.stackOut.pop(); | |
} | |
peek() { | |
if (this.stackOut.length === 0) { | |
while (this.stackIn.length > 0) { | |
this.stackOut.push(this.stackIn.pop()); | |
} | |
} | |
return this.stackOut[this.stackOut.length - 1]; | |
} | |
empty() { | |
return this.stackIn.length === 0 && this.stackOut.length === 0; | |
} | |
} |
2. 用队列实现栈
题目描述：使用两个队列实现一个栈，支持基本的栈操作：push（入栈）和pop（出栈）。
代码解释：使用两个队列，一个用于正常操作，另一个作为辅助。当需要出栈时，将主队列中的元素（除了最后一个）依次移动到辅助队列，然后弹出主队列的最后一个元素，再将辅助队列中的元素移回主队列。
代码示例：
javascript复制代码
class MyStack { | |
constructor() { | |
this.queue1 = []; | |
this.queue2 = []; | |
} | |
push(x) { | |
this.queue1.push(x); | |
} | |
pop() { | |
while (this.queue1.length > 1) { | |
this.queue2.push(this.queue1.shift()); | |
} | |
const result = this.queue1.shift(); | |
[this.queue1, this.queue2] = [this.queue2, this.queue1]; // Swap queues | |
return result; | |
} | |
top() { | |
while (this.queue1.length > 1) { | |
this.queue2.push(this.queue1.shift()); | |
} | |
const result = this.queue1[0]; | |
this.queue2.push(this.queue1.shift()); | |
[this.queue1, this.queue2] = [this.queue2, this.queue1]; // Swap queues | |
return result; | |
} | |
empty() { | |
return this.queue1.length === 0; | |
} | |
} |
3. 栈的压入、弹出序列
题目描述：输入两个序列，一个为栈的压入序列，另一个为栈的弹出序列，判断该弹出序列是否由该压入序列经过栈操作得到。
代码解释：使用辅助栈模拟压入和弹出操作，比较模拟结果和给定的弹出序列是否一致。
代码示例：
javascript复制代码
function validateStackSequences(pushed, popped) { | |
const stack = []; | |
let index = 0; | |
for (const num of pushed) { | |
stack.push(num); | |
while (stack.length > 0 && stack[stack.length - 1] === popped[index]) { | |
stack.pop(); | |
index++; | |
} | |
} | |
return stack.length === 0; | |
} |
4. 用两个栈实现括号匹配
题目描述：给定一个只包含括号（小括号、中括号、大括号）的字符串，判断字符串是否有效。
代码解释：使用栈来存储左括号，遇到右括号时检查栈顶元素是否匹配。
代码示例：
javascript复制代码
function isValid(s) { | |
const stack = []; | |
const map = { ")": "(", "]": "[", "}": "{" }; | |
for (const char of s) { | |
if (["(", "[", "{"].includes(char)) { | |
stack.push(char); | |
} else if (map[char] && stack[stack.length - 1] === map[char]) { | |
stack.pop(); | |
} else { | |
return false; | |
} | |
} | |
return stack.length === 0; | |
} |
5. 最小栈
题目描述：设计一个支持push、pop和getMin操作的栈，其中getMin操作返回栈中的最小元素。
代码解释：使用辅助栈存储当前栈中的最小值。
代码示例：
javascript复制代码
class MinStack { | |
constructor() { | |
this.stack = []; | |
this.minStack = []; | |
} | |
push(x) { | |
this.stack.push(x); | |
if (this.minStack.length === 0 || x <= this.getMin()) { | |
this.minStack.push(x); | |
} | |
} | |
pop() { | |
if (this.stack.pop() === this.getMin()) { | |
this.minStack.pop(); | |
} | |
} | |
top() { | |
return this.stack[this.stack.length - 1]; | |
} | |
getMin() { | |
return this.minStack[this.minStack.length - 1]; | |
} | |
} |
6. 滑动窗口最大值
题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口中的最大值。
代码解释：使用双端队列（deque）来存储当前窗口中的元素索引，队列中的元素从队头到队尾递减。
代码示例：
javascript复制代码
function maxSlidingWindow(nums, k) { | |
const deque = []; | |
const result = []; | |
for (let i = 0; i < nums.length; i++) { | |
// Remove elements out of the current window | |
if (deque.length > 0 && deque[0] === i - k) { | |
deque.shift(); | |
} | |
// Remove elements smaller than the current one from the deque | |
while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) { | |
deque.pop(); | |
} | |
deque.push(i); | |
if (i >= k - 1) { | |
result.push(nums[deque[0]]); | |
} | |
} | |
return result; | |
} |
7. 栈的排序
题目描述：对栈进行排序，要求只能使用另一个栈作为辅助。
代码解释：使用递归或迭代的方法，将栈中的元素逐个取出，插入到辅助栈中合适的位置，以保持排序顺序。
代码示例（迭代）：
javascript复制代码
function sortStack(stack) { | |
const tempStack = []; | |
let sorted = false; | |
while (!sorted) { | |
sorted = true; | |
for (let i = 0; i < stack.length - 1; i++) { | |
if (stack[i] > stack[i + 1]) { | |
// Swap elements | |
[stack[i], stack[i + 1]] = [stack[i + 1], stack[i]]; | |
// Move the larger element to tempStack | |
tempStack.push(stack.pop()); | |
sorted = false; | |
break; | |
} | |
} | |
// Move sorted elements back to stack | |
while (tempStack.length > 0) { | |
stack.push(tempStack.pop()); | |
} | |
} | |
return stack; | |
} |